The Busy Beaver Problem

You're viewing a comment by dasuxullebt and its responses.

October 30, 2009, 01:27

Very nice idea to plot this as graphics. Very interesting (even in general).

Using linear-speedup and dynamic recompilation, one could write a quite fast Turing-Machine-Emulator. Would be nice if someone would do that - but well, not very useful, even for TCS meanwhile. Still, this problem is not bound to Turing-Machines. In fact, something similar can be defined for any turing-complete Programming Language. And even for weaker (or stronger) machine models this type of problem (namely giving some upper bound of the time a program runs) can be formulated - thats basically what the ackermann-function is for loop-machines or typed lambda-closures. Basically, it is equivalent to the Halting Problem.

@Casey: The Tape of the Turing Machine can content 0 and 1. Initially, infinitely many 0's, but the algorithm can write 1's on it. Should be clear then.

Oh, and well ... who ever hosts this blog: Please add some possibility to subscribe to comments.

Reply to this comment

Reply To This Comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Comment Help

Type first 3 letters of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.