On Tue, Jul 23, 2013 at 7:18 PM, Levi Pearson <levipear...@gmail.com> wrote: > I guess that the starting state of the tape is generally not > considered to be part of the Turing machine itself; so the set of > Turing machines of n-states is still computable. Although, if your > Turing machine is a universal Turing machine, the way you get it to > emulate another Turing machine is to pass it in via an encoding on the > tape, so the idea of pre-writing the tape is certainly valid, it's > just not part of a particular Turing machine's definition.
Right, we wouldn't be running the Turing machines as part of the program, just defining all possible combinations of n states. Afterward you'd probably want to run each of them in turn for X "ticks" (where X is a number that's maybe five times higher than the known minimum for any BB number - iirc it's 4,096 or so for BB(5)) and then see which are still running, then examine each of those individually to determine whether they will ever halt. This still runs into problems at BB(6) and above because the possible combinations of states and the known minimum number of ticks is astronomical (economical, even) but at least you should be able to shrink the set. -Dan /* PLUG: http://plug.org, #utah on irc.freenode.net Unsubscribe: http://plug.org/mailman/options/plug Don't fear the penguin. */
