3
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.