Re: [Algorithms] Turing machine question

[Danny K. <dr...@we...>]

> In practice, you can encode any finite or countably infinite digital
> system state in one number (that's where names like Godel start to
> fuse).  So, on a turing-ish tape, that means two bits are enough.
> Converting the program to run on the 1-bit limited version is the hard
> part though.  I have no idea whether it's actually possible.

That's exactly where I was heading with the question, yes - thanks for 
reassuring me that I'm not being completely crazy. I envision a system where 
the distance between the first two boxes represents the simulated TM itself, 
the next distance represents its current state, the next represents the 
state of the tape, and the last represents the current position on the tape. 
(as you say you could further compress this into a single number, but that 
has the disadvantage that you have to do a lot more processing to work out 
what it's actually doing). Then any further calculations would be done with 
other boxes that come after these initial five. It seems to me that this 
ought to be doable with a finite number of boxes and a finite number of 
states, but I'm not sure.

I know it's a totally pointless and academic question, but it intrigues me 
strangely.

Danny