Polygon: Added Category:Zoology

2026-02-20T13:58:41Z

Added Category:Zoology

← Older revision		Revision as of 13:58, 20 February 2026
Line 13:		Line 13:
	== References ==		== References ==
	<references />		<references />

			[[Category:Zoology]]

Sligocki: Created page with "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 h..."

2025-08-19T20:35:46Z

Created page with "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 h..."

New page

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".<ref>Turlough Neary and Damien Woods. "The complexity of small universal Turing machines: a survey". 2011. https://doi.org/10.48550/arXiv.1110.2230</ref> 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)

== References ==
<references />

Universal Turing Machine - Revision history

Polygon: Added Category:Zoology