What is Machine State Notation?

The Machine State Notation is one of the five numerical notations discussed in Chapter 2 of Sir Roger Penrose's book The Emperor's New Mind. The other four notations are Unary, Binary, Denary, and Expanded Binary.

The Machine State Notation is not so much a numerical notation as it is the Transition Function for a Turing Machine, but it can be converted to any one of the other notations, and for that reason it can also be thought of as a numerical notation.

Being the Transition Function, it completely describes the Turing Machine. The Machine State Notation is actually the list of all the instructions executed by the Turing Machine, at each state that the Turing Machine could be in, depending on whether the Turing Machine's Read/Write Head sees a 0 or 1 on the paper tape.

When the Machine State Notation is converted into any one of the other notations (usually Binary or Denary), that number is usually called the Turing Machine Number.

The Binary Notation of the Turing Machine Number is used by the Universal Turing Machine. It reads the Turing Machine Number in Binary as data, and does everthing that that Turing Machine would do.

The Denary Notation of the Turing Machine Number is strictly for human consumption. Although there do exist Turing Machine Numbers that are quite small (such as T₀, T₁, T₂, etc), most Turing Machine Numbers of Turing Machines that actually do interesting computations consist of hundreds or thousands of denary digits. The size of these numbers is truly mind-boggling!

---