A universal Turing machine is a Turing machine that can simulate all Turing machines.
More formally, for any Turing machine
- accepts
if accepts - rejects
if rejects - does not halt on
if does not halt on Note: rejects input strings not of the form
The language of
Why This Matters
The discovery of the universal Turing machine means that a general-purpose, programmable computing machine exists and we don’t need specialized machines for all computations.
The universal Turing machine is also a stepping stone to find unsolvable problems.
See Also
- Church-Turing thesis: the univesal machine is a justification for the Church-Turing thesis in the sense that powerful models of computation can simulate one another