What is a Turing Machine Number?

Every Turing Machine has a number associated with it. This way, instead of inventing a different name for every Turing Machine that you construct, you can just use its Turing Machine Number and everyone will know exactly what Turing Machine you are talking about.

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.

If, for whatever reason, you would still prefer to have specific "names" for Turing Machines rather than just refer to them by numbers, Sir Roger Penrose has a suggestion on how that can be done as well. On page 70 of his book, he proposes using "names" such as T₀, T₁, T₂, T₃, and so on.

T₀ is the Turing Machine whose Turing Machine Number is 0.
T₁ is the Turing Machine whose Turing Machine Number is 1.
T₂ is the Turing Machine whose Turing Machine Number is 2.
T₃ is the Turing Machine whose Turing Machine Number is 3.
And so on.

---

Turing Machine Numbers are particularly useful because they can be used easily by the Universal Turing Machine. In other words, if you want the Universal Turing Machine to do exactly the same thing that your Turing Machine T_n would do, just provide the number n (as a binary number) on the paper tape along with the rest of the data, and the Universal Turing Machine will give you exactly the same answer as if you ran T_n on that data.

---

The Universal Turing Machine also has a Turing Machine Number associated with it. (After all, the Universal Turing Machine is a Turing Machine too.) Sir Roger Penrose provides the Turing Machine Number for the Universal Turing Machine, and he writes out that huge number in binary on pages 93 through 96 in his book. This binary number is 5,495 digits long! He also acknowledges his gratitude to David Deutch for converting this number to denary and lists it on page 74 of his book. This denary number is 1,654 digits long!