HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Turing machine working only with 1's and blanks - how to encode input?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
howblankswithandworkinginputmachineturingencodeonly

Problem

Let's say we have a Turing machine which head can only write 1 or blank to the tape (although it can read all symbols from any input alphabet correctly). Can we operate with it on any input?

My approach was that we can rewrite our input tape with unary coding and symbol-codings separated with blanks. If we had, for example, an input

...[][]0123[][]...


we could try to encode 0 as 1[], 1 as 11[] and so on. We would know when we reached the end of our input word when we read two blanks in a row. However, rewriting the example string from above would cause some problems. When we code a single symbol with multiple ones, we overwrite another symbols and need to remember them in state. In the example above, after encoding 0 our tape would be like

...[][]1[]23[][]...


And in our state we'd remember that we need to encode 1 now. Hovever, writing the encoding would overwrite 2, 3 and a blank, so we would need to remember those ones as well in the state. Such an approach leads to creating a lot of states: for n-letter alphabet and unary encoding I proposed it would be $(n+1)^n$ (all possible combinations of symbols on n+1 positions on the tape) "basic states", and for each of those we'd need a few more so that we could write an adequate number of "1" finished by a blank. I am not sure if this is acceptable at all.

Is my approach correct? What other approaches could I take?

Solution

In the following, I use "0" to denote a blank cell, and I first assume that 1 is not used in the original alphabet. I will deal with this at the end.

A first solution is possible if you assume that the head can go over a cell and read it without writing on it.

If you assume that you can tell the two ends of your input, the answer
to your question is just that you copy/translate the input to unary form on some
other part of the tape, so that you do not run the risk of erasing a
part of the input that has not been copy/translated yet. If you
copy/translate the input from left to right, you start the copying on
some part of the tape that is on the right of the original input.

For that purpose, you need markers, and you can for example use 010 to
mark the place where you copy the translation of the next symbol. You
can erase original symbols as you copy them, and possibly also mark
the last erased symbol with 010 (wich you then do not use as
translation of an original symbol). Part of the control is teh used to
move bertween the two 010 marks during the translation phase.

But you cannot make the number of states dependent on the length of
the input. The TM uses the same finite state control independently of
input size, which implies not changing th number of states.

If you do not allow reading a cell without overwriting it, things are
more complicated. I further assume that the head is initially on the
left side of the input. In ordr to make a copy translation without
destroying the input, one has to start from the left, and make the
copy further on the left.

Since it is impossible to foresee how much space will be needed, the
trick is to copy/translate the input into a mirror image, so that it
grows on the left, and never risk erasing the original input.

Then you can either decide to compute with a mirror image, or you can
just make a second pass on the copy/translated input, so as to reverse
it again and have it in the right order.

Using 1 in the original input.

I think that it is possible to do the same when 1 is used in the original alphabet. But one must be very careful not to confuse its use in the original input, and in the copy part. This can be done with a specific configuration appearing only a fixed number of times in the created copy, the rightmost one dentifying precisely the beginning of the rest of the original input to be copied.

Context

StackExchange Computer Science Q#35146, answer score: 3

Revisions (0)

No revisions yet.