2
$\begingroup$

In the fifth edition of Boolos et al's Computability and Logic, Exercise 4.5 asks the following:

A universal Turing machine is a Turing machine $U$ such that for any other Turing machine $M_n$ and any $x$, the value of the two-place function computed by $U$ for arguments $n$ and $x$ is the same as the value of the one-place function computed by $M_n$ for argument $x$.

Show that if Turing's thesis is correct, then a universal Turing machine must exist.

Intuitively, the set of Turing machines is enumerable, then for any finite $n$ we can proceed to enumerate the machines as finite strings. Once we get to the required $n$, we run the Turing machine $M_n$ on the argument $x$. If $M_n$ halts in a standard position with some output, then we have found $u(n,x)$. If $M_n$ does not halt or halts in a nonstandard position, then that is the desired "value" (presumably, $u(n,x)$ is then undefined, but that should be all right since by "function" Boolos et al mean a total or partial function, unless otherwise specified). This is an informal list of instructions to compute $u(n,x)$, so $u$ is effectively computable, and so by Turing's thesis is also Turing-computable, whence $U$ must exist.

That seems trivial. But the exercise is the final one in a block of exercises, and the instructor's manual hints at using the Turing-uncomputable diagonal function, whose relevance I am not seeing. This is evidence towards me missing something. What am I missing?

$\endgroup$
  • $\begingroup$ It's a strange question - in particular, there really isn't a rigorous definition of the Turing thesis, implicitly, while the above is a rigorous statement of fact, which seems independent of the thesis. The theorem, together with the thesis, says that the universal machine can compute all human-computable functions, but that's a separate issue. $\endgroup$ – Thomas Andrews Aug 25 '15 at 4:12
  • $\begingroup$ @ThomasAndrews I'm just going off the definition of the thesis Boolos et al give: "Any effectively computable function is Turing computable," together with their "A function $f$ is effectively computable if a list of instructions exists to compute $f(n)$ for any $n$." $\endgroup$ – Jukka Aug 25 '15 at 4:19
  • $\begingroup$ But the second sentence is, mathematically, nonsense. Not because it has no purpose, it just has no rigorous statement. The Turing thesis has no bearing on the existence of a universal machine. If the Turing thesis is false, the above statement is still true. Only if you made the definition of Universal machine be about effectively computable functions could you invoke the Turing thesis. $\endgroup$ – Thomas Andrews Aug 25 '15 at 4:23
2
$\begingroup$

Turing's thesis asserts that every "effectively computable" function is computable by a Turing machine. It is not necessary to sharply define "effective computability" to get the converse implication. This amounts to showing that there is a partial enumeration $F$ (possibly nonterminating) of the effectively computable functions such that the value of $F$ on input $x$ for any arbitrary index $e \in \mathbb N$ is computably enumerable by an arbitrary machine $U$.

More precisely, $U(e,x) \iff F_e(x)$, when $F$ is partial computable and $U \iff F$ is shorthand for $U$ is defined $\iff$ $F$ is also defined, taking into account their respective inputs.

To show that $U$ exists then one has to construct a diagonal function $\psi$ which enumerates the domain of $F_e(x)$ in strictly increasing order. The reason that the existence of such a $U$ follows from Turing thesis is that this universal machine is a "well-defined" intuitive algorithm by constructing a fixed point $F_e(x) = F_{\psi(x)}(x)$ when $\psi(e)$ is a total function (so it is defined for every input).

Thus, no matter what partial enumeration of the "effectively computable" functions is used, there will surely exist a partial function $U$ such that any arbitrary index $e$ in the enumeration will witness some total function $\psi$, taking $F_e(x)$ to $F_{\psi(e)}(x)$ on all its domain as a fixed-point, given input $x$.

$\endgroup$
4
$\begingroup$

The argument alluded to in the question is sound. Specifically: Turing's thesis says that, if a human computer can perform a given algorithm, then there is a Turing machine to do it. A human computer can certainly simulate the computation of a Turing machine, given the code for the machine. Therefore, by Turing's thesis, there must be a universal Turing machine that can do the same thing.

I don't think that the instructor's hint is germane to the question as stated. Perhaps a different question was intended?

$\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.