A very small Turing machine, some very big numbers, and an oracle!
A few weeks ago, Wolfram Research announced that Alex Smith had won the $25000 prize (first offered some months earlier) for a proof that a particular 2 state, 3 colour (symbol) Turing machine was universal. (He could also have won the prize for proving it was not universal.) If this proof holds up, then this 2,3 machine is as "small" as any universal Turing machine can be, as smaller machines are already known to not be capable of being universal.
Note though that there were some slightly unusual and fuzzy areas in the competition description: for one thing the prize machine has no explicit halt state and so doesn't really qualify as a "classical" Turing machine, and also the definition of "universal" was left a bit open ended.
And then, it also turns out that Alex Smith's proof pushed the boundaries of what has been previously generally accepted as "the rules" for Turing machines. In particular his proof relies on the construction of an infinite non-periodic initial configuration. Classical Turing machine descriptions require the equivalent of infinite "blank" cells either side of a finite region (where the real input data is "written"), although periodic patterns have also been explored more recently and may be considered acceptable by some. So, one issue with Alex's proof that has caused some ongoing debate is whether or not his infinite and non-periodic initial tape configuration isn't "cheating" in some way - if you're not extremely careful, an initial tape configuration like this can actually be helping the machine act as if it was universal even though it really isn't.
But putting that aside, another thing that really bothered me about Alex's proof (and the particular style of infinite initial configuration it requires) was that it claimed to show us a "universal Turing machine", yet this machine had no way to emulate a copy of itself! That apparently didn't matter to the judges, but how could I ever hope to calculate an eigenratio if there wasn't a way to construct a self-interpreter to start with?! :-)
All the controversy about Alex's proof has been concerned with the infinite non-periodic nature of his initial tape configuration, and exactly how it is "constructed". But there's an important first step in Alex's proof (before it goes anywhere near the construction of the infinite initial configuration), and that is where he shows how to construct a finite initial configuration for this machine. Each such finite initial configuration will emulate a given cyclic tag system for any particular finite number of "cycles". So, if you only need to run that cyclic tag system for, say, a billion cycles then Alex's proof can show you how to set up the appropriate finite initial configuration. You might have a more difficult system to emulate though - perhaps you need a googol of cycles to be sure there's enough juice in the tank to do the required computations. No problem again. And we can keep on going, there is no finite upper limit. Emulating a googleplex of cycles of your cyclic tag system is really just about as easy. Just plug "googolplex" into Alex's program for generating finite initial configurations and you'll have your answer "shortly". :-)
Now all of this might make you think that Alex has already shown in the first part of the proof how this machine can emulate "any number" of cycles (with finite non-blank initial tape content) and so is already "good enough" to be called universal. The trouble is that we don't (in general) know in advance exactly how many cycles the cyclic tag system will execute to do what it needs to do. That's the whole thing with these types of systems - knowing how many steps they'll need to finish, or even if they'll ever stop running at all is undecidable!
But maybe there's another way to look at this. It turns out that Turing machines (and other similar computational models such as cyclic tag systems) have their own version of what is known as the Busy Beaver Problem. You can follow the link for more details but basically there is a maximum number of steps or cycles for each "size" of one of these machines, such that if a particular "run" ever goes past that number of steps or cycles then we also know it will never halt. (It's stuck in some kind of infinite loop for example.) So if we get to that point and the machine hasn't stopped, then we can be absolutely confident that it will never stop by itself, and just "pull the plug" instead (to "save some time" as it were)! Now, these Busy Beaver type problems produce very very very very big numbers in general. And that's still an understatement! In fact, trying to imagine them makes me feel a little bit queasy! Worse, they aren't computable (not even in a theoretical sense - unless the Church-Turing thesis turns out to be false and some form of effective computing system more powerful than Turing machines is discoved), but we do know they exist. (Actually, some of the Busy Beaver values are known, but these are only for the very smallest sizes of a few machines.) In any case, my main point is that these Busy Beaver values exist!
When thinking about this yesterday I realised it also means that for any particular cyclic tag system, we know there is always some number of cycles that we can run it for (including via emulation by the 2,3 machine), and we can be sure it will have produced a "usable result" by the end, if not earlier. Either the cyclic tag system will have terminated by that stage, in which case we can read off the result, or if it hasn't terminated by then we know it also never will. And we also know that the initial configuration of the tape for this massive emulation is also guaranteed to be finite. The only catch is that we don't know how to work out this Busy Beaver number for any non-trivial cyclic tag system, and so we also can't actually produce the finite initial configuration!
But just knowing it exists is enough for me - there is a finite configuration out there somewhere, generated directly from a very large (and non-computable) number, and any higher value will do as well for that matter. If we could find an oracle to tell us that magic number, then we could actually construct the initial configuration "simply" by just plugging it into Alex's Perl script, although we might need to add some more RAM to our machine first!
Anyway, now that we know a suitable finite initial pattern always exists, we can (in a hypothetical sense) build a self-interpreter for this machine. As for determining its eigenratio, I'm leaving that as "an exercise for the reader". But be warned, I suspect it could be rather large! To get you started, working backward, I think you'll have to do something like (a) find a classical universal Turing machine and set it up to emulate the prize 2,3 machine and it's (finite) data tape (which could be emulating some arbitrary cyclic tag system for example, but not necessarily), then (b) construct a tag system to emulate that Turing machine and matching input, (c) construct a cyclic tag system to emulate the tag system, and finally use Alex Smith's proof (and your pet oracle again) to show how to set-up the finite initial configuration that allows the prize 2,3 machine to emulate the whole circular contraption for "enough" cycles...
PS: if you want to read more about big numbers, then you may want to read Scott Aaronson's "Who Can Name the Bigger Number?".
Note though that there were some slightly unusual and fuzzy areas in the competition description: for one thing the prize machine has no explicit halt state and so doesn't really qualify as a "classical" Turing machine, and also the definition of "universal" was left a bit open ended.
And then, it also turns out that Alex Smith's proof pushed the boundaries of what has been previously generally accepted as "the rules" for Turing machines. In particular his proof relies on the construction of an infinite non-periodic initial configuration. Classical Turing machine descriptions require the equivalent of infinite "blank" cells either side of a finite region (where the real input data is "written"), although periodic patterns have also been explored more recently and may be considered acceptable by some. So, one issue with Alex's proof that has caused some ongoing debate is whether or not his infinite and non-periodic initial tape configuration isn't "cheating" in some way - if you're not extremely careful, an initial tape configuration like this can actually be helping the machine act as if it was universal even though it really isn't.
But putting that aside, another thing that really bothered me about Alex's proof (and the particular style of infinite initial configuration it requires) was that it claimed to show us a "universal Turing machine", yet this machine had no way to emulate a copy of itself! That apparently didn't matter to the judges, but how could I ever hope to calculate an eigenratio if there wasn't a way to construct a self-interpreter to start with?! :-)
All the controversy about Alex's proof has been concerned with the infinite non-periodic nature of his initial tape configuration, and exactly how it is "constructed". But there's an important first step in Alex's proof (before it goes anywhere near the construction of the infinite initial configuration), and that is where he shows how to construct a finite initial configuration for this machine. Each such finite initial configuration will emulate a given cyclic tag system for any particular finite number of "cycles". So, if you only need to run that cyclic tag system for, say, a billion cycles then Alex's proof can show you how to set up the appropriate finite initial configuration. You might have a more difficult system to emulate though - perhaps you need a googol of cycles to be sure there's enough juice in the tank to do the required computations. No problem again. And we can keep on going, there is no finite upper limit. Emulating a googleplex of cycles of your cyclic tag system is really just about as easy. Just plug "googolplex" into Alex's program for generating finite initial configurations and you'll have your answer "shortly". :-)
Now all of this might make you think that Alex has already shown in the first part of the proof how this machine can emulate "any number" of cycles (with finite non-blank initial tape content) and so is already "good enough" to be called universal. The trouble is that we don't (in general) know in advance exactly how many cycles the cyclic tag system will execute to do what it needs to do. That's the whole thing with these types of systems - knowing how many steps they'll need to finish, or even if they'll ever stop running at all is undecidable!
But maybe there's another way to look at this. It turns out that Turing machines (and other similar computational models such as cyclic tag systems) have their own version of what is known as the Busy Beaver Problem. You can follow the link for more details but basically there is a maximum number of steps or cycles for each "size" of one of these machines, such that if a particular "run" ever goes past that number of steps or cycles then we also know it will never halt. (It's stuck in some kind of infinite loop for example.) So if we get to that point and the machine hasn't stopped, then we can be absolutely confident that it will never stop by itself, and just "pull the plug" instead (to "save some time" as it were)! Now, these Busy Beaver type problems produce very very very very big numbers in general. And that's still an understatement! In fact, trying to imagine them makes me feel a little bit queasy! Worse, they aren't computable (not even in a theoretical sense - unless the Church-Turing thesis turns out to be false and some form of effective computing system more powerful than Turing machines is discoved), but we do know they exist. (Actually, some of the Busy Beaver values are known, but these are only for the very smallest sizes of a few machines.) In any case, my main point is that these Busy Beaver values exist!
When thinking about this yesterday I realised it also means that for any particular cyclic tag system, we know there is always some number of cycles that we can run it for (including via emulation by the 2,3 machine), and we can be sure it will have produced a "usable result" by the end, if not earlier. Either the cyclic tag system will have terminated by that stage, in which case we can read off the result, or if it hasn't terminated by then we know it also never will. And we also know that the initial configuration of the tape for this massive emulation is also guaranteed to be finite. The only catch is that we don't know how to work out this Busy Beaver number for any non-trivial cyclic tag system, and so we also can't actually produce the finite initial configuration!
But just knowing it exists is enough for me - there is a finite configuration out there somewhere, generated directly from a very large (and non-computable) number, and any higher value will do as well for that matter. If we could find an oracle to tell us that magic number, then we could actually construct the initial configuration "simply" by just plugging it into Alex's Perl script, although we might need to add some more RAM to our machine first!
Anyway, now that we know a suitable finite initial pattern always exists, we can (in a hypothetical sense) build a self-interpreter for this machine. As for determining its eigenratio, I'm leaving that as "an exercise for the reader". But be warned, I suspect it could be rather large! To get you started, working backward, I think you'll have to do something like (a) find a classical universal Turing machine and set it up to emulate the prize 2,3 machine and it's (finite) data tape (which could be emulating some arbitrary cyclic tag system for example, but not necessarily), then (b) construct a tag system to emulate that Turing machine and matching input, (c) construct a cyclic tag system to emulate the tag system, and finally use Alex Smith's proof (and your pet oracle again) to show how to set-up the finite initial configuration that allows the prize 2,3 machine to emulate the whole circular contraption for "enough" cycles...
PS: if you want to read more about big numbers, then you may want to read Scott Aaronson's "Who Can Name the Bigger Number?".
posted by Clive at 10:35 am
0 Comments:
Post a Comment
<< Home