Problem Detail: 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?
Answered By : babou
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/35146
Related
