0
$\begingroup$

I really need some help with this problem. I'm running into the issue that the input is running out of space to append the 11 or 10. I could really use some help conceptualizing this problem and how to think about Turing machines in general.

Change the original input with a 1  into 11 and 0 into 10. You must also append a 01 to the start of the input once it is finished.  for instance, if the input  was 10110, then the output would be 011110111110.

$\endgroup$
  • 2
    $\begingroup$ Your title is very general. Perhaps you could make it more specific? $\endgroup$ – Yuval Filmus Oct 16 at 22:58
1
$\begingroup$

If you have a single tape Turing machine then your main conceptual problem is separating input from output. You could approach this problem as follows:

Initial configuration:

  • We will assume the tape is filled with spaces apart from a single input string which consists of a non-empty sequence of $0$s and $1$s.
  • We will assume the Turing machine starts at the first character (left hand end) of the input string.

Intermediate configuration:

  • We will construct an output string which is a sequence of $0$s and $1$s.
  • The output string will be to the right of the input string, with a single space between them.
  • We will erase the input string one character at a time from the left, and build the output string by adding two characters at a time to its right hand end.

Final configuration:

  • When the Turing machine stops we will have erased the whole input string, and the tape will contain spaces and the output string.
  • The Turing machine will stop at the first character of the output string.

Outline algorithm:

  1. Read the first character of the input string and "remember" whether it is a $0$ or a $1$ (short term "memory" in a Turing machine consists of defining different states).
  2. Erase the first character of the input string by writing a space.
  3. Move right until you find a space (so you have gone past the end of the input string).
  4. Move right until you find another space (so you have gone past the end of the output string). Write $1$.
  5. Move right. If the first character of the input string was $0$ write $0$; if it was $1$ write $1$.
  6. Move left until you find a space (so you have gone past the beginning of the output string).
  7. Move left until you find another space (so you have gone past the beginning of the input string).
  8. Move right. If there is a $0$ or a $1$ here then there is more input to be processed so go to step 1.
  9. The input string is now empty and you are at the space before the start of the output string. Write $1$.
  10. Move left, write $0$, and stop.

As you will find, designing a Turing machine for even a simple task is very laborious, and it takes practice to break down a task into very small steps. You will need between $15$ and $20$ states for this Turing machine.

$\endgroup$
1
$\begingroup$

I could really use some help conceptualizing this problem and how to think about Turing machines in general.

Turing Machines are formal logical models that can express computation. You can think of them as mechanical machines that perform read and write operations on one or more tapes containing symbols. These operations are not performed randomly but based on a table (called the transition function) which is the true essence of the Turing Machine, without it the machine could not even move from the initial state. This table specifies what the machine must do in each state, based on the 'settings' of the "machine world state", for example:

  1. If the machine is in state $q_1$ and it reads a '$1$' on the input tape, then write a '$0$' on the working tape and move left on the same tape.
  2. If the machine is in state $q_3$ and it reads a '$0$' on the input tape, then go to state $F$ (HALT).

These are some basic description of a TM, if you want to know them better (and I believe it is mandatory to master them if you want to continue with this discipline). Then you need to open a textbook and dig into these concepts. Now going back to your problem, you might find it useful to throw down a high-level description of an algorithm (turing machine) that performs the required transformations on the input string; then you can proceed from here, after you have learned how to formally define a turing machine, and draw your model.

Possible algorithm:

  1. start reading input tape
  2. if input at position $i = 1$, then write a $1$ on the working tape at position $i$ and a $1$ at position $i+1$, then move right on the input tape.
  3. if input at position $i = 0$, then write a $1$ on the working tape at position $i$ and a $0$ at position $i+1$, then move right on the input tape.

To this you need to add the implementation for adding '$01$' at the start of the string.

$\endgroup$

Your Answer

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

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