This is a repost from https://stackoverflow.com/questions/56990710/encoding-any-turing-machine-to-one-with-2-symbols since it was brought to my attention that the question would be better suited to this SE than SO.
I am interested in understanding how a Universal Turing Machine would work on a practical level.
I read Rogozhin’s paper Small universal Turing machines to understand how a UTM works and how to encode a 2-tag system to act as its input. Next I read Cocke and Minsky’s Universality of tag systems with p=2 on how to convert a 2-symbol TM to a 2-tag system.
My literature search is now stuck at the point where I need to convert an arbitrary TM to a 2-symbol TM. 2-symbol means that the TM has an alphabet of 0 and 1 with 0 also acting as a blank, so I strictly have only two symbols at my disposal.
This question https://stackoverflow.com/questions/4820488/can-a-turing-machine-be-constructed-having-only-two-tape-symbols has a well-written answer that gives the necessary pointers to understand the conversion generally, but it is not explicit enough to know that a possible solution would be a good one.
Can anyone direct me to a paper that shows the state-of-the-art conversion process? I am sure that Cocke and Minsky based their work on proof that any TM can be emulated by a 2-symbol TM.
If there is no literature reference to be had, could anyone help me analyse whether my solution is close enough to optimal? From the post above, it seems like I need to encode the original TM’s tape to a fixed-length binary representation. My solution looks like the following, and I would be happy if someone could comment on whether I am way off the mark:
Let’s assume that the original TM has 5 states and 8 symbols, so I can use a 3-bit encoding. After reading a word, we would have to encode writing and moving the head like this: 6 states are needed to get back to the beginning of the word that was just read (moving the head once without writing is the equivalent to read 0/write 0 and read 1+write 1, which takes 2 states – repeat 3 times to get to our goal position). Add another 3 states for writing the new word. 6 more states are needed to move back to the beginning of the word and another 6 states to move the head left or right.
The reading operation itself takes 8 states for a 3-bit word (ending up in one of 8 states depending on the result). From here the transition described above is started, so from a given state I can encode all transitions including the read operation in
read + possible_reads*(move+write+move+move) = 8 + 8*(6+3+6+6) = 176 states.
This encodes all transitions of a single state from the original TM. Since we have 5 original states in total, the complete new TM would need 5*176 = 880 states.
In general terms I would need s*(1+(7*b))*q states, where s is the alphabet size and q the number states of the original TM, and b is the encoding bit depth ceil(log(s)).
This sounds about fair to me, is there something I overlooked? I think writing intermediate state information on the tape is out of the question with only 2 symbols so encoding everything in states seemed the only reasonable option to me.
PS: I also need some pointers in how to get the 2-symbol TM to encode the monadic input to binary. The link above does not give much useful input to this question.
Edit: In order to show that I already tried to get an answer to my second question, here is my specific problem: I have to convert multiple monadic inputs to their binary counterparts using a 2-symbol TM. So the input separation between monadic words would be achieved with a single zero and the end of the tape with two zeros. Now when I start the conversion process, I will have to go back and forth between the monadic inputs and the binary outputs. The binary outputs may naturally contain multiple zeros which would prevent me from finding the end of the tape in the conversion process. I could switch to a different end-of-tape word that cannot occur in the binary numbers, but I am not sure that this is really the most efficient option.