Universal Turing Machine

computation

Definition

Universal Turing Machine

A Turing machine $U$ is called universal if for all Turing machines $M$ and all $(n_1,\dots ,n_k)\in {\mathbb{N}}^k$ it holds that:

$$f(U)(⟨M⟩,n_1,\dots ,n_k)=F(M)(n_1,\dots ,n_k)$$

where $⟨M⟩$ is the encoding (code) of a Turing machine $M$.

Existence

Existence of Universal Turing Machine

Universal Turing machines exist (Turing 1936).

Interpreter

A universal Turing machine corresponds to an interpreter.