Hand-drawn picture of Turing Machine

Are the Turing Machines described by Alan Turing and Sir Roger Penrose the same?



Yes and No, depending on what you mean by the same.



The answer is Yes, because both descriptions, that of Alan Turing and that of Roger Penrose, can be used to construct valid Turing Machines. In other words, both can be used to create something that satisfies the Formal Definition of a Turing Machine.

They both have the same capabilities; whatever one can do, the other can do also; whatever problem one can solve, the other can also.

Both types of Turing Machines are State Machines, and any Turing Machine (of either description) will be in any one of a finite number of States at any given time.

Both types of Turing Machines have the ability to read a symbol on an infinitely long tape, then depending on the State that it's in and the symbol it just read, write a symbol on the tape and then move one position on the tape to the left or right.

Both types of Turing Machines include good Turing Machines and bad Turing Machines--as explained in the table below--although what may be considered as good in Alan Turing's description may be bad in Roger Penrose's description, and vice versa.

Both types of Turing Machines have a Universal Turing Machine.



However, the answer is also No. When you look at the details of both Turing Machine, they look quite different. The table below lists the differences.

Alan Turing Roger Penrose
The paper tape is infinitely long, but only at one end. It actually has a left edge and extends infinitely far to the right.

Well, actually that's not entirely true. The tape can be infinitely long at both ends, and Turing Machines can be designed to go left on the tape without limit. However, the machines that Alan Turing had in mind would read and write symbols on the tape only to the right of the original starting position.
The paper tape is infinitely long at both ends.
The paper tape is divided into infinitely many squares, and each square will hold a symbol that will be read or written by the Turing Machine. These squares are of two different types, and they are called F-squares and E-squares. These squares alternate, i.e., every second square is an F-square, and between each two F-squares is an E-square.

The symbol on the F-squares can be the blank, 0, or 1.

The symbol on the E-squares can be the blank, lower case letter (a, b, c, ..., z), or the special symbol @ or ə (the symbol for schwa).

The intent is that, as the Turing Machine runs, the answer will gradually grow in the F-squares, while the E-squares are used for scratch work and placeholders.

There are exceptions to the above rules (ex., Alan Turing showed an example where the symbol ə is in an F-square).
The paper tape is divided into infinitely many squares, and each square will hold a symbol that will be read or written by the Turing Machine.

In a Penrose-type Turing Machine, there is no distinction among the squares on the tape. The only symbol allowed in any square is 0 or 1.

In the Excel file that you can dowload from the Home Page of this web site, the tape also has blanks in addition to 0's and 1's, but the blanks are treated as if they were 0's.
Any Turing Machine of this type can only have a finite number of states.

Each state has a name, which can be a letter such as 𝖆, 𝖇, 𝖈, 𝖉, 𝖊, 𝖋, 𝖌, 𝖍, 𝖎, 𝖏, 𝖐, 𝖑, 𝖒, 𝖓, 𝖔, 𝖕, 𝖖, 𝖗, 𝖘, 𝖙, 𝖚, 𝖛, 𝖜, 𝖝, 𝖞, or 𝖟, or words formed from these letters. These letters are the lowercase letters from the German Gothic alphabet.

There is also an alternate way to name the states, and these names are q1, q2, q3, etc., and this alternate way is explained in Alan Turing's famous paper as well.
Any Turing Machine of this type can only have a finite number of states.

Each state has an address which is a binary number. So, the addresses of the states are 0, 1, 10, 11, 100, 101, etc.
The initial state, i.e., the state the Turing Machine is in when it starts running, is 𝖇.

When using the alternate way of naming states, the initial state is always q1.
The initial state, i.e., the state the Turing Machine is in when it starts running, is 0.
Instructions in this type of Turing Machine may consist of one or more movements along the tape along with zero or more writings to the tape, followed by a transition to another state.

An example taken directly from Alan Turing's paper might be read as follows:

When in state 𝖇 and the Read/Write Head reads blank, then do Pə,R,Pə,R,P0,R,R,P0,L,L and then go to state 𝖔.

In other words: When in state 𝖇 and the Read/Write Head reads blank, then write ə, move to the right, write ə, move to the right, write 0, move to the right, move to the right, write 0, move to the left, move to the left, and then go to state 𝖔.

This same example also appears on page 87 of the book The Annotated Turing by Charles Petzold (Wiley Publishing, Inc., 2008), which I highly recommend if you seriously want to understand the paper by Alan Turing.
Instructions in this type of Turing Machine consist of writing a 0 or 1 to the tape, one movement to the right or the left or a stop, followed by a transition to another state.

An example might be the following: The instruction for state 100110 when the Read/Write Head reads 1 is 10001R.

In other words: When in state 100110 and the Read/Write Heads reads 1, then write 1, move to the right, and go to state 1000.
This type of Turing Machine requires no data, so that the entire tape is completely blank before the Turing Machine starts running.

Actually, a Turing Machine can be designed to use data as input and provide an answer based on that data. However, it was Alan Turing's intent that his machines work without any input data.

A very important exception to this rule is the Universal Turing Machine which absolutely must have data. This data would be in the form of a standard description (S.D) of the Turing Machine being emulated.
The Penrose Turing Machine must have data.

If the paper tape had no data when this type of Turing Machine started running, then since the first instruction is 00R, the Turing Machine would just keep writing 0's on the tape as its Read/Write Head moved to the right forever, and none of the other instructions would ever be executed.
Every Turing Machine can be converted to its standard description, which is a long string of the letters A, C, D, L, R, N, and the semicolon.

Each Turing Machine also has associated with it a description number (D.N). It is easily constructed from the standard description by simply making the following replacements: "A" by 1, "C" by 2, "D" by 3, "L" by 4, "R" by 5, "N" by 6, and ";" by 7.

It was this association of each Turing Machine with a positive integer that proved one of the main conclusions of Alan Turing's famous paper. By showing that there is a correspondence between Turing Machines and a subset of the positive integers (when written in denary notation), he proved that the set of all Turing Machines, and therefore the set of all computable numbers, must be at most countable.

Notice that the digits 0, 8, and 9 never appear in any description number. Also, since every standard description starts with a semicolon, the most significant digit of every description number is always 7.
Every Penrose Turing Machine can be converted to a Turing Machine Number.
The standard description of a Turing Machine is used as data by the Universal Turing Machine.

To prepare the tape for the Universal Turing Machine, first write the symbol ə in any square on the tape. (This will become an F-square.) Then, immediately to the right of it (in an E-square) write another ə. Then, on as many F-squares as you need to the right of these two ə's, write out the entire standard description (which consists of the letters A, C, D, L, R, N and the semicolon).
The Turing Machine Number of a Turing Machine is used as data by the Universal Turing Machine.

To prepare the tape for the Universal Turing Machine, first write the Turing Machine Number of the Turing Machine you want the Universal Turing Machine to emulate, then immediately to the right of it write five consecutive 1's, then immediately to the right of that write the data that would have been used by the emulated Turing Machine.
Alan Turing's intent was that his Turing Machines don't use any data. Therefore, when the Turing Machine starts running, the tape should be completely blank. Therefore, it doesn't matter where you place the Read/Write Head on the tape before the Turing Machine starts running.

If you happen to ignore Alan Turing's intent and design a Turing Machine that uses data, then just make sure you place the Read/Write Head on the tape in such a way that your Turing Machine will find the data (according to the way you designed your Turing Machine).
Before the Turing Machine starts running, the Read/Write Head should be positioned on the tape so that all of the data is to the right of the Read/Write Head, and there are only 0's in each of the infinitely many squares to the left of the Read/Write Head.
Before the Universal Turing Machine starts running, you should have prepared a tape with two consecutive ə symbols, and all the data to the right of them. Make sure you place the Read/Write Head anywhere to the right of the two consecutive ə symbols. Just like with any other Penrose Turing Machine, before the Universal Turing Machine starts running, the Read/Write Head should be positioned on the tape so that all of the data is to the right of the Read/Write Head, and there are only 0's in each of the infinitely many squares to the left of the Read/Write Head.
A good Turing Machine is one that runs forever and never halts.

Alan Turing did not design his Turing Machines to have a STOP instruction.
A good Turing Machine is one that eventually executes a STOP instruction and halts.
A bad Turing Machine is one that halts. (For example, it might crash because it tries to go to a state that doesn't exist.)

A bad Turing Machine is also one that gets stuck in an infinite loop and just stays there forever without producing an answer.
A bad Turing Machine is one that runs forever and never halts.

A bad Turing Machine is also one that halts, but not because it executed a STOP instruction. (For example, it might crash because it tries to go to a state that doesn't exist.)
As your Turing Machine is running, you can watch your answer grow one digit at a time. The answer will appear on the F-squares going from left to right.

Alan Turing's intent was that an F-square can only be written with a 0 or 1, and once it is written, it can never be erased or overwritten. Furthermore, no F-squares may be skipped, so that the only blank F-squares to the right are those that the Turing Machine hasn't written yet. (Meanwhile, you may observe a lot of activity on the E-squares, which may be erased and overwritten many times.)

Once you have determined that you have enough digits on the F-squares (so that you have enough accuracy for your purposes), you can manually stop the Turing Machine, and you have your answer.
When the Turing Machine stops running, your answer will be to the left of the Read/Write Head.


Version 1.0 -- July 5, 2022
Template Version 1.0 -- May 19, 2017