How do I convert a Turing Machine Number into a Turing Machine?
The question above could also be rephrased as:
How do I convert a number in Binary Notation to Machine State Notation?
If you had already viewed the web page that answered the question How do I figure out the Turing Machine Number?, then you already know that there are six steps in converting a Turing Machine to a Turing Machine Number. So here, we just reverse that entire procedure.
That reverse procedure is described below; however, for the sake of clarity, I decided to describe it in nine steps.
Along with the explanation of these steps, it would be good to work with an example. So, let's pick a number that's in binary notation, and use it.
Step 1: Write down the number (in binary notation) that you would like to convert into a Turing Machine.
Example:
101011010111101010
Step 2: Write down the three binary digits "110" at the end of your number.
Example:
101011010111101010110
Step 3: Separate the string of 1's and 0's into several shorter strings of 1's and 0's by placing a blank after every bit-pattern "110".
Example:
1010110 1011110 1010110
Step 4: Replace every bit-pattern "11110" with "STOP".
Example:
1010110 10STOP 1010110
Step 5: Replace every bit-pattern "1110" with "L".
Example: There is no bit-pattern "1110" in this example, so nothing changes.
1010110 10STOP 1010110
Step 6: Replace every bit-pattern "110" with "R".
Example:
1010R 10STOP 1010R
Step 7: Replace every bit-pattern "10" with "1".
Example:
11R 1STOP 11R
Step 8: If you had already viewed the web page that answered the question How can I interpret instructions in the Penrose Turing Machine? then you know that every instruction must be of the form mnD, where m is a binary number, n is a binary digit, and D is R, L, or STOP. That means that every instruction must have at least two binary digits before the R, L, or STOP. If that's not the case, then we have to put in one or two leading zeros to make sure we have at least two binary digits in each instruction.
Example:
11R 01STOP 11R
Step 9: Every Penrose Turing Machine starts with the instuction 00R. That's the instruction for state 0 when the Read/Write Head sees 0 on the paper tape. So, just insert 00R at the beginning of the list of your instructions.
Example:
00R 11R 01STOP 11R
Ok! There you have it! There's your Turing Machine!
The only thing you have to realize is that the first two instructions are for state 0, the next two instructions are for state 1, the next two instrucions are for state 10, the next two instructions are for state 11, and so on.
Also, for each pair of instructions for any particular state, the first one is used when the Read/Write Head sees "0" on the tape, and the second one is used when the Read/Write Head sees "1" on the tape.
Those of you who had already run the Turing Machine using the built-in example UN+1 may recognize these instructions. Perhaps you remember seeing a screen that looked something like this:
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.
These are exactly the same instructions that we got by starting with the binary number 101011010111101010 and going through the nine steps above.
Version 1.0 -- April 23, 2017