Suppose that the tape of a Turing Machine (TM) initially contained 0 at the far

Question

Suppose that the tape of a Turing Machine (TM) initially contained 0 at the far left, followed by the binary representation of the integer n. Assume that the start state was state 1. What would be the action of the following TM?

Hint: you can type in the TM program in the Turing Machine Simulator and experiment with it by varying the contents of the input tape.

What is the (binary) encoding of this TM?

Input State Input Symbol Output State Output Symbol Move 1
2
2
3
3
4 0
0
1
0
1
0 2
3
2
5
4
2 0
0
1
blank
0
1 R
R
R
L
L
R

Explanation / Answer

Answer:

The five fields in your Turing instructions are probably:

1) current state
2) read symbol
3) next state
4) written symbol
5) move table

You look through the table for the first two values (current state and read symbol), and then follow the other three instructions (write symbol, move table, go to next state).

You start at state 1, with the reading point on top of the 0 at the far left (I assume). Since we start in state 1 and the current spot in the tape contains 0. This (1/0) matches (1/0/2/0/R), so we write a 0, move the tape to the right one place, and go to state 2.

Now you are in state 2, and the tape is one spot to the right, on the leftmost bit in your binary number. Now you will match either (2/0) or (2/1). In the case of 2/1, we run (2/1/2/1/R) -- write a 1 over top of the 1 that we were at, move the tape one spot to the right, and return to state 2. In the case of 2/0, we run 2/0/3/0/R -- write a 0 over top of the 0 that we were at, move the tape one spot to the right, and go to state 3.

When you eventually get to state 3, the tape is one slot to the right of the leftmost 0 in your binary number (e.g., if it is 1111000, it's on the middle "0"). If that is a 1, (3/1/4/0/L) changes it to 0, moves to state 4 and moves the tape back to the left. If it is a 0 (3/0/5/ /L), I'm less clear on, since this directs the next state to be #5... and your list doesn't have a state 5.
So, if we take a tape with the number 0101 on it, we will go through the following states:
Input: 0 1 0 1 0 1
State: 1->2->2->3->4->2->2
Output: 0 1 0 0 1 1

For a tape with number 011, we will get:
Input: 0 1 1
State: 1->2->2->2
Output: 0 1 1

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.