1
$\begingroup$

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.

Edit: I am also limited to a single tape.

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.

$\endgroup$
  • $\begingroup$ It looks like you have answered the most of the question. The problem of encoding the input using two symbols is easy for you to solve on your own. I would encourage you to write your own answer, which could become the reference on how to encode any Turing machine to one with 2 symbols. $\endgroup$ – Apass.Jack Jul 11 at 18:52
  • $\begingroup$ encoding everything in states seemed the only [...] option.. Another idea might be to determine the minimum number of bits k needed to encode the tape symbols in binary. Turn the original TM T into a (k+1)-tape TM T' where tapes 1 through k move in sync. Iff in any computation of T, tape cell c holds symbol s at step t, a matching computation of T' cell c on tape i holds the bit #(i-1) of the binary encoding of s at step t. Tape k+1 at any time contains exactly two 1s marking the position of the first unused cell left or under, and right of the head, resp. $\endgroup$ – collapsar Jul 12 at 0:15
  • $\begingroup$ @Apass.Jack I amended my original question to show my thought process. It does not seem to be easy to solve, unless I am missing something. Any pointers to that easy solution would be appreciated. I think the issue is less trivial than it sounds. $\endgroup$ – Cerno Jul 12 at 10:12
  • $\begingroup$ @collapsar Thanks a lot for your thoughts.I am sorry that I forgot to mention that I am limited to a 1-tape machine. I will amend the original question. $\endgroup$ – Cerno Jul 12 at 10:13
  • $\begingroup$ What exactly is your question? It seems like you already know how to do the encoding, but not sure how to do it efficiently? $\endgroup$ – Dmitri Urbanowicz Jul 12 at 10:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.