<p>I found some alternate definitions of Universal Turing Machine in papers related to the universality of small Turing machines and other models.</p>

<p>See for example the four definitions (the first 3 are equivalent and are similar to yours except that there there is also an explicit <em>decoding</em> function) in section 2 of <a href="http://www.sciencedirect.com/science/article/pii/S0304397596000771">Yurii Rogozhin, Small universal Turing machines, Theoretical Computer Science, Volume 168, Issue 2, 20 November 1996, Pages 215-240</a>.</p>

<p>For example the Davis's definition in M. D. Davis, A Note on Universal Turing Machines ; Martin Davis, The Definition of Universal Turing Machine . Journal of Symbolic Logic 35 (1970), no. 4, 590; bypasses the encoding phase:</p>

<p>A generic machine (Turing machine, tag-system, ...) is <em>universal</em> if and only if its halting problem is r.e. complete.</p>

<p>Probably you're not interested in them (and you'll probably know them), but there are also  notions of <em>semi-weakly universal</em>  and <em>weakly universal</em> Turing machines (in which the initial tape has an infinite repeated string on the left/right/left+right of the input). For further details see the work of Neary and Woods on small TMs.</p>

CC BY-SA 3.0
2014-11-10T12:34:20.493Z
2014-11-10T12:34:20.493Z
Marzio De Biasi
<p>I am not sure what is the appropriate way for this, but I would like to collect different possible definitions/variants of Universal Turing-machines.
Here are the ones I know, post below if you know other definitions/comments/don't agree.
For simplicity, I assume that we talk about two-tape machines with alphabet {0,1,*}, but let me know if in some definition this might make a difference.
I denote by T(x,..,z) the output of Turing-machine T when the inputs on its tapes are x,..,z, if it halts, and "running forever" otherwise.</p>

<p><strong>Exists.</strong> U is universal if for every T there is a p such that for every x we have U(p,x)=T(x).</p>

<p><strong>Computable.</strong> U is universal if there is a computable encoding E of Turing-machines (labeled directed graphs) into strings such that for every T and x we have U(E(T),x)=T(x).</p>

<p><strong>Fix.</strong> Fix a (computable) encoding E of Turing-machines into strings. U is universal if for every T and x we have U(E(T),x)=T(x).</p>

<p><strong>Strict.</strong> In both the Computable and the Fix definition, we can also demand that for every input that is not of the above format, U does nothing useful (halts without output, outputs the empty string, or runs forever).</p>

<turing-machines><universal-computation><definitions><universal-turing-machines>
What are different definitions of Universal Turing-machine?
domotorp
# What are different definitions of Universal Turing-machine?

(Asked by: username_0 on 2014-11-10)

I am not sure what is the appropriate way for this, but I would like to collect different possible definitions/variants of Universal Turing-machines.
Here are the ones I know, post below if you know other definitions/comments/don't agree.
For simplicity, I assume that we talk about two-tape machines with alphabet {0,1,\*}, but let me know if in some definition this might make a difference.
I denote by T(x,..,z) the output of Turing-machine T when the inputs on its tapes are x,..,z, if it halts, and "running forever" otherwise.

**Exists.** U is universal if for every T there is a p such that for every x we have U(p,x)=T(x).

**Computable.** U is universal if there is a computable encoding E of Turing-machines (labeled directed graphs) into strings such that for every T and x we have U(E(T),x)=T(x).

**Fix.** Fix a (computable) encoding E of Turing-machines into strings. U is universal if for every T and x we have U(E(T),x)=T(x).

**Strict.** In both the Computable and the Fix definition, we can also demand that for every input that is not of the above format, U does nothing useful (halts without output, outputs the empty string, or runs forever).

**Tags:** turing-machines, universal-computation, definitions, universal-turing-machines

---

## 1 answers

### Answer by username_1 on 2014-11-10. Score: 5 | Accepted answer

I found some alternate definitions of Universal Turing Machine in papers related to the universality of small Turing machines and other models.

See for example the four definitions (the first 3 are equivalent and are similar to yours except that there there is also an explicit *decoding* function) in section 2 of [Yurii Rogozhin, Small universal Turing machines, Theoretical Computer Science, Volume 168, Issue 2, 20 November 1996, Pages 215-240](http://www.sciencedirect.com/science/article/pii/S0304397596000771).

For example the Davis's definition in M. D. Davis, A Note on Universal Turing Machines ; Martin Davis, The Definition of Universal Turing Machine . Journal of Symbolic Logic 35 (1970), no. 4, 590; bypasses the encoding phase:

A generic machine (Turing machine, tag-system, ...) is *universal* if and only if its halting problem is r.e. complete.

Probably you're not interested in them (and you'll probably know them), but there are also notions of *semi-weakly universal* and *weakly universal* Turing machines (in which the initial tape has an infinite repeated string on the left/right/left+right of the input). For further details see the work of Neary and Woods on small TMs.


---

