‘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.
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.