3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ it can be done eg if the tape ends are separated with multiple blanks whereas internal tape blanks are always single. the TM basically has to figure out at every blank whether it is double or single. the question does get to the idea/ dynamics/ specifics of "valid encodings" for TM inputs which is not always so simple given that "blank" is a symbol & has special status as far as existing on all squares outside of the input. $\endgroup$
    – vzn
    Dec 11, 2014 at 19:36
  • $\begingroup$ Yes, I assume the tape except for the input is full of "blanks" (at least this is how I am used to call that squares symbolizing "empty"). The thing that scares me away is the number of states necessary. However, it appears to be finite still, and so I thought it is possible to build such a Turing machine. $\endgroup$
    – 3yakuya
    Dec 11, 2014 at 20:08

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I can't agree: I can't use 010 because I can't write 0 at all (only 1 or a blank). What's more, I can't go from left to right and copy to the empty piece of tape, because I can't pass over any symbol without destroying it, unless it's 1 or a blank. The only way would be to copy to the left of the original code, but then again I would not know how far to the left should I start encoding the first input character. The option I described uses a number of states dependent on the size of input alphabet, which is constant for a machine and does not depend on an input. $\endgroup$
    – 3yakuya
    Dec 11, 2014 at 20:48
  • 1
    $\begingroup$ Sorry about the notation. I used 0 to indicate a blank cell. Regarding erasing, your question is not explicit about the brand of TM you are using. In my country, the also carry a model that can move over the tape, reading it, but not writing on it. I was wondering why yu saw a problem. $\endgroup$
    – babou
    Dec 11, 2014 at 21:02
  • $\begingroup$ Now it is clear - I forgot to mention that my model did not allow TM to pass without overwriting a cell. Thank you very much. $\endgroup$
    – 3yakuya
    Dec 11, 2014 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.