Thread: Very basic turing machines problem

We have Turing machine M with one work tape, which is it's output. The tape heads of input and work tape can move only left and right (basic definition, there is no staying at the current position movement). And we want to execute simple algorithm. We want to duplicate each symbol on the input tape twice and write it to the output tape. So if the input tape reads >ABCDE# in respective alphabet, we want to produce >AABBCCDDEE# on the output tape. How do we do that?

Obviously wrong way to do it: Simulate no movement of the work tape with a pair of forward - back movements.
What will happen? We will read the current symbol on the input tape and write it to the output tape. Then we have to move both tapes. We can move both tapes in the same direction, so the difference between their two positions will be 0. We can move the input tape back and the output tape forward, which will result difference between their positions of 2. There is no way we can move the tape heads so the difference between their positions is odd. So we can't reach situation where the read tape is at position n and the work tape is at position n+1 (For example position 1 for input tape and position 2 for output tape). How we do proceed then with the algorithm?

Hey mrproper.

A question I have for you is what the structure of the Turing model is. You say you have an input and an output tape: in some models you only have one tape which you can read or write to but you have two tapes.

So the question I have is where do you get the actual instructions from (is it on a separate tape), and also what kind of data can you have in working memory (i.e. what is the definition of the entire state-space mathematically of the Turing Machine)?

Originally Posted by chiro

So the question I have is where do you get the actual instructions from (is it on a separate tape), and also what kind of data can you have in working memory (i.e. what is the definition of the entire state-space mathematically of the Turing Machine)?

See Multi-tape Turing machines.

I can't answer this question, I think. I'm complete novice in the matter and not completely sure exactly what You ask. But I can give you context - that is how I got to the question I ask and why I find it so important to stop reading and start thinking / asking questions. So...

I started reading several things at once and got to the point where the idea that computational model doesn't matter is discussed. That is - it doesn't matter which model of a machine we use, if we want to find out if something is computable and to discover in which complexity class it belongs.

So if it doesn't matter what machine we use to do computations, it can have only one input and one output/work tape; it can have one read only input tape and multiple work tapes; it can have different alphabet and even different movement commands for the tape heads. For example the classic texts seems to describe only two tape movements - "left" and "right" (or "back" and "forward" movement), while some texts like these notes (http://web.science.mq.edu.au/~chris/langmach/chap09.pdf) do discuss the possibility of third movement command which makes the tape head stay where it is ("no movement"). The notes mention that adding this third command does not make more powerful machine which can solve a problem that the other can't. (This is discussed within the context of a machine with one tape only though).

So if it really doesn't matter, there must be an algorithm for the described two tape machine (one r/o input tape and one r/w output/work tape that can do the above operation. Only I couldn't find it. So I ask ...

I think I found an approach. You just move one of the tapes to the start symbol and try one more left (backward) movement after that. The difference between the positions of the two heads will be now odd number.
Seems like cheating though.

Originally Posted by mrproper

You just move one of the tapes to the start symbol and try one more left (backward) movement after that. The difference between the positions of the two heads will be now odd number.

This is one possible way.

More generally, the machine may have to remember (in its state) character(s) it read during previous step(s). I.e., there have to be several copies of one state, one per character read during one of the previous steps.

Here is a possible execution trace. There is a loop during which the machine reads two characters and writes four characters; then it starts the next iteration of the loop.

Code:

(1) |ABC  (2) A|BC  (3) |ABC  (4) A|BC  (5) AB|C
    |         A|         AA|      A AB|     AA BB|

I write step numbers in parentheses. What follows is the description of the machine before the corresponding step. The top line shows the input tape and the bottom line shows the work tape. I write "|" before the character that is observed by the head. Since "|" is not an actual character on the tape, ignore the spaces between characters; they are for alignment only.

During step 1 the machine reads A and writes A on the work tape. It also remembers A in a state. Both heads move right. During step 2 the machine writes the character it remembered ("A") and not the one observed on the input tape. It also remembers the character it observes ("B"). The input head moves left and the work head moves right. During steps (3) and (4) the machine writes the latest remembered character ("B"); both heads move right.

That's it!!! Wow.
The needed states will grow with the size of input, but since the input is finite, so the states...

The number of states will grow with the size of the input alphabet but not with the size of input.

Ok, I finally got that.