Universal Turing Machine

A Universal Turing Machine (UTM) is a Turing Machine which can simulate any other TM (encoded onto input tape). The precise definition requires defining the encoding function to map simulated TMs and TM inputs into UTM initial tapes. Since a UTM can simulate any TM, the halting problem for any UTM is not computable.

There is a common misconception that the Busy Beaver Functions will become uncomputable once we reach a domain with a UTM (since the general halting problem for UTMs are undecidable). However, while no program can decide if a UTM halts across all possible inputs, it is possible to decide whether it halts when started on a single input (ex: a blank tape).

Minimal UTMs

There is a long history of searching for the smallest UTMs (measured in terms of number of states and symbols). It appears that the the best known results are summarized by Turlough Neary and Damien Woods in "The complexity of small universal Turing machines: a survey". The define 3 types of UTM: standard, semi-weakly universal, and weakly universal. Standard UTMs require the TM encoding to be finite. Semi-weakly UTMs allow TM encodings which are finite with an additional finite sequence repeated indefinitely in one direction on the tape. Weakly UTMs allow such a finite repeat in both directions on the tape.

The set of minimal known UTMs are of size (num states, num symbols):

• Standard UTMs: (15,2), (9,3), (6,4), (5,5), (4,6), (3,9), (2,18)
• Weakly UTMs: (6,2), (3,3), (2,4)