# What are different definitions of Universal Turing-machine?

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).

## 1 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.

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.