Following the usual monthly linkfest on SSC, I stumbled upon an interesting paper by Scott Aaronson. Basically, he and Adam Yedidia created a Turing machine which, from ZFC, cannot be proved to stop or run forever (it will run forever assuming a superset of said theory). It is already known from Chaitin incompleteness theorem that every formal system has a limit complexity length, over which it cannot prove or disprove certain assertions. The interesting, perhaps surprising, part of the result is that said Turing machine has ‘only’ 7918 states, that is a registry less than two bytes long. This small complexity is already sufficient to evade the grasp of ZFC. You can easily slogan-ize this result by saying that BB(7918) (the 7918th Busy Beaver number) is uncomputable (whispering immediately after ”… by ZFC”).
‘only’ 7918 states, that is a registry less than two bytes long
this remark sounds weird. What is the meaning of the bit-size of the list of states? Are you suggesting to run the TM on a 16-bit computer? Then, good luck addressing the memory (the tape), because I guess the length of the tape used is probably also “uncomputable”, or at least so large that even the pointers to the tape would not fit into any realistic computer’s memory.
It was merely a remark to notice that 7918 states fits in a state registry that is less than two bytes long. And since said TM only has two symbols, it will also need no more than 15836 instructions. Notice how compact the machine is: 13 bits for the state registry, 29 bits for each instructions, 15836 of said instructions = 459257 bits. less than half a megabyte. You could emulate that on basically everything that has a chip, nowadays. Alas, the tape size is infinite, as with every TM… But! Turing machines do not need memory pointers: they observe only the symbol where the reading head is.
Turing machines do not need memory pointers: they observe only the symbol where the reading head is.
Sure, but any system that emulates the TM and the tape would need it. (In other words, it feels like cheating to say that memory is a part of the usual computer, but tape is not a part of the TM.)
I still don’t see where the difficulty is. You need a memory registry only if you need random access to said memory, but the TM does not need it. Sure, if you want to emulate a TM on a system that already uses random access memories, like most modern systems do, than of course you need a sufficiently long pointer for a sufficiently wide memory. But that is an accident of how systems work today, not an inherent complexity: you could easily emulate the TM in an old mainframe with a magnetic tape without ever seeing a memory pointer.
Following the usual monthly linkfest on SSC, I stumbled upon an interesting paper by Scott Aaronson.
Basically, he and Adam Yedidia created a Turing machine which, from ZFC, cannot be proved to stop or run forever (it will run forever assuming a superset of said theory).
It is already known from Chaitin incompleteness theorem that every formal system has a limit complexity length, over which it cannot prove or disprove certain assertions. The interesting, perhaps surprising, part of the result is that said Turing machine has ‘only’ 7918 states, that is a registry less than two bytes long.
This small complexity is already sufficient to evade the grasp of ZFC.
You can easily slogan-ize this result by saying that BB(7918) (the 7918th Busy Beaver number) is uncomputable (whispering immediately after ”… by ZFC”).
This is an upper bound. There could be many smaller indeterminate machines. Many suspect that even very simple TMs can indeterminate. E.g. collatz.
Huh. I expected the smallest number of states of a TM of indeterminate halting to be, like, about 30. Consider how quickly BB diverges, after all.
I agree with most of what you said, but
this remark sounds weird. What is the meaning of the bit-size of the list of states? Are you suggesting to run the TM on a 16-bit computer? Then, good luck addressing the memory (the tape), because I guess the length of the tape used is probably also “uncomputable”, or at least so large that even the pointers to the tape would not fit into any realistic computer’s memory.
It was merely a remark to notice that 7918 states fits in a state registry that is less than two bytes long. And since said TM only has two symbols, it will also need no more than 15836 instructions.
Notice how compact the machine is: 13 bits for the state registry, 29 bits for each instructions, 15836 of said instructions = 459257 bits. less than half a megabyte. You could emulate that on basically everything that has a chip, nowadays.
Alas, the tape size is infinite, as with every TM… But! Turing machines do not need memory pointers: they observe only the symbol where the reading head is.
Sure, but any system that emulates the TM and the tape would need it. (In other words, it feels like cheating to say that memory is a part of the usual computer, but tape is not a part of the TM.)
I still don’t see where the difficulty is. You need a memory registry only if you need random access to said memory, but the TM does not need it.
Sure, if you want to emulate a TM on a system that already uses random access memories, like most modern systems do, than of course you need a sufficiently long pointer for a sufficiently wide memory. But that is an accident of how systems work today, not an inherent complexity: you could easily emulate the TM in an old mainframe with a magnetic tape without ever seeing a memory pointer.