An effectively universal Turing machine $T$ is a Turing machine for which there exists a recursive reduction $f$ such that $\forall A:U(A)=T(f(A))$, where $A, f(A)$ are finite sequences of symbols (that are given as inputs) and $U$ is a universal Turing machine.

Is there any connection between effectively universal Turing machines and Turing-completeness?

Also, given a Turing machine $T$ that is not effectively universal, is it possible to decide if it halts on a specific input? As far as I am aware, the diagonalization argument would not apply, since the TM used in the construction would be effectively universal.

My attempt so far was to use an argument from contradiction:

If this variant of halting problem is undecidable, then there exists a recursive reduction from the (general) halting problem to it. However, if such a reduction exists, it contradicts the premise that $T$ is not effectively universal.

I am not sure, however, if this is correct or if it misses anything.

  • $\begingroup$ You seem to be missing some "for all $A,B$" somewhere. Please edit the question to clarify the first sentence and place the quantifiers in the correct place. Also, what are $A,B$? Also, what does "$T$ behave on $B$" mean? Can you make the definition more precise? $\endgroup$
    – D.W.
    Commented Feb 16 at 22:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.