How do I figure out the Turing Machine Number?
The question above could also be rephrased as:
How do I convert a number in Machine State Notation to Binary Notation?
On pages 67-69 of his book The Emperor's New Mind (Oxford University Press, 1989), Sir Roger Penrose explains how to figure out the Turing Machine Number of any Turing Machine.
The steps of that procedure will be listed below. It would be good, however, to work through an example while explaining the steps. Let's take a look at the Turing Machine UN+1 as we go through the steps.
Below is a portion of the Excel file as you would see it as you're ready to start running the UN+1 Turing Machine.
Notice that rows 5 and 6 of the Excel file have the "instructions" of the UN+1 Turing Machine. (In the terminology of the Formal Definition of a Turing Machine, these are called Transition Functions. In the two Excel files that you can download from the Home page of this website, I call these Machine State Notation.) It is these "instructions" that will be translated into the Turing Machine Number as explained below.
Step 1: List all of the "instructions" in a single row, making sure that they are in order according to the state they belong to. (I.e., first list the two instructions for state 0, then list the two instructions for state 1, then list the two instructions for state 10, then list the two instructions for state 11, etc.)
Also, when listing the two instructions in any one state, make sure that you first write down the instruction "When tape has 0" and to the right of it write down the instruction "When tape has 1."
UN+1 Example:
00R 11R 01STOP 11R
Step 2: Every Penrose Turing Machine has 00R as its first instruction. Therefore, there's no need to keep it when figuring out our Turing Machine Number. Let's just remove it from the list.
UN+1 Example:
11R 01STOP 11R
Step 3: Replace each of the remaining instructions with a string of 1's and 0's according to the following rules: replace each "0" with "0", replace each "1" with "10", replace each "R" with "110", replace each "L" with "1110", and replace each "STOP" with "11110".
UN+1 Example:
1010110 01011110 1010110
Step 4: Remove any leading zeros from the strings of numbers.
This is really an optional step, but it's good to do because it will result in a smaller Turing Machine Number. (If you skip this step, you'll still get a Turing Machine Number that validly represents the same Turing Machine, but it'll just be a bigger number.)
UN+1 Example:
1010110 1011110 1010110
Step 5: Just string together all the numbers you have into one long string of 1's and 0's.
UN+1 Example:
101011010111101010110
Step 6: The number you have thus far ends in "110". That's always true, because that came from a replacement of "R" by "110", or a replacement of "L" by "1110", or a replacement of "STOP" by "11110". In any case, just remove the "110" that's at the end of the number.
UN+1 Example:
101011010111101010
So there you have it! The Turing Machine Number of the UN+1 Turing Machine is 101011010111101010 when expressed as a binary number.
To check that we haven't made a mistake when going through the six steps above, we can just use the Notation Converter Excel file that's available on this website. It's the second Excel file that you can download from the Home page.
As you use the Notation Converter:
When asked "From which numerical notation will you be converting your number?", select Machine State.
When asked "What Machine States shall we use?", select Example from the book "The Emperor's New Mind".
When asked "Which Machine States Example from "The Emperor's New Mind" would you like to use?", select From page 54, the Turing Machine UN+1.
When you see "So Far So Good!", click OK.
And there you have it! You see the Turing Machine Number of the UN+1 Turing Machine in various numerical notations. Notice that as a binary number, this is 101011010111101010, just as we predicted! Also, as a denary number, it is 177642.
So, the Turing Machine Number of the UN+1 Turing Machine is 177,642. Cool!
Version 1.0 -- April 23, 2017