How can I interpret instructions in the Penrose Turing Machine?

This page also answers the question: What are all of the valid Turing Machine instructions that I can use?

---

---

If you had already watched the Demo Video (at the link at the top of this page), then you saw a simple example of a Turing Machine. It is the Turing Machine UN+1 that Sir Roger Penrose described on page 54 of his book The Emperor's New Mind (Oxford University Press, 1989).

You may have noticed that this Turing Machine had instructions that looked like 00R, 11R, and 01STOP. If you had already downloaded the Turing Machine Excel file, and run it with the built-in example Turing Machine EUC, you may have noticed many more instructions that look like 11L, 10100R, 00STOP, 10001L, and several others.

In the terminology of the Formal Definition of a Turing Machine, these are called Transition Functions.

---

Ok. That's fine. But what do they mean?

---

Every "instruction" (or Transition Function) in a Penrose Turing Machine is of the form mnD where m consists of one or more binary digits (0's and 1's); n is just a single binary digit (0 or 1); and D is one of the following: R, L, or STOP.

For example:

For 00R, m = 0, n = 0, D = R.

For 10001L, m = 1000, n = 1, D = L.

For 01STOP, m = 0, n = 1, and D = STOP.

For 10101R, m = 1010, n = 1, and D = R.

---

Ok. That's fine. But what do they mean?

---

During every single step that the Turing Machine takes, it "looks" at the "instruction" that's appropriate for the state that it's in, and the number that the Read/Write Head "sees" on the tape. This "instruction" is always of the form mnD. Then it does the following in order:

1. The Read/Write Head writes n on the tape. This is a 0 or 1.

2. It performs action D. If D = R then the Read/Write Head moves one square to the right on the tape. If D = L then the Read/Write Head moves one square to the left on the tape. If D = STOP then the Read/Write Head moves one square to the right on the tape and the Turing Machine stops; in this case, the m part of the "instruction" is ignored.

3. The Turing Machine goes to state m. This is a binary number consisting of one or more digits. The names of the states of the Turing Machine are 0, 1, 10, 11, 100, 101, etc.

---

For example:

For 00R, write 0 on the tape, move one square to the right, and go to state 0.

For 10001L, write 1 on the tape, move one square to the left, and go to state 1000.

For 01STOP, write 1 on the tape, move one square to the right, and stop.

For 10101R, write 1 on the tape, move one square to the right, and go to state 1010.