[Solved]: Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?

Problem Detail: I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem.

Halting function: The Halt function takes an input a pair $<alpha, x>$ and outputs 1 if and only if the TM $M_{alpha}$ represented by $alpha$ halts on input $x$ within a finite number of steps.

The undecidability of Halting function is proved by reduction from another undecidable function $UC$, which is defined as follows Book by Arora and Barak.

$UC$: For every $alpha in lbrace 0,1 rbrace^{ast}$, if $M_{alpha}(alpha) = 1$, then $UC(alpha) = 0$; otherwise (if $M_{alpha}(alpha)$ outputs a different value or enters an infinite loop), $UC(alpha) = 1$.

The undecidability of $UC$ is proved by the also well-known “diagonalization” technique. I can understand the technique. However, I am puzzling over a more basic problem involving the definition of $UC$.

My Problem: The definition of $UC$ is based on the value of $M_{alpha}(alpha)$. Especially, it seem to be based on whether a Turing Machine halts on an input. However, the latter is undecidable (Worse still, it is undecidable due to the undecidability of $UC$!). In this sense, is the $UC$ function well-defined?

What is wrong with my opinion? How should I understand the definition of $UC$ and the relation between $UC$ and Halting Problem? Thank for your help.

Asked By : hengxin

Answered By : Andrej Bauer

In classical logic it is possible to define a function which is not computable, and $UC$ is such a function. What probably confuses you is that you think that a function must always be given in a symbolic form, or as a set of instructions on how to compute it, or some such. But this is not necessary. Officially a function $f : A to B$ is the same thing as a subset $F subseteq A times B$ satisfying the functionality condition:

For every $x in A$ there is exactly one $y in B$ such that $(x,y) in F$.

We may apply this to our situation to define $UC$ as the set of pairs $$UC = lbrace ((alpha, x), d) mid (text{$M_alpha$ halts on $x$ and $d = 1$}) lor (text{$M_alpha$ does not halt on $x$ and $d = 0$}) rbrace.$$ Even though nobody told us how to discover the output $d$ for a given input $(a, x)$, it is still the case that for every $(a,x)$ there is exactly one $d$. Indeed, if there were more than one then we would have a machine $M_alpha$ which both halts and does not halt on input $x$. And if there were no such $d$, that would mean we have a machine $M_alpha$ which neither halts nor not halts on input $x$. In constructive logic one cannot define a non-computable function. And neither can one show that all functions are computable. So there $UC$ would not satisfy the functionality condition, and it would only define a partial function. But we could still talk about the fact that the Hlating problem is not decidable because the same classical argument still applies (we just avoid talking about $UC$). Assume there is a Turing machine $H$ such that:

$H$ halts on every input.
If $M_alpha$ halts on $x$ then $H$ on input $(alpha, x)$ outputs $1$.
If $M_alpha$ does not halt on $x$ then $H$ on input $(alpha, x)$ outputs $0$.

We now proceed with the usual diagonalization argument and construct a machine $B$ with a code $beta$ such that $B(beta)$ halts if, and only if, $H(beta, beta)$ outputs $0$. Everything here is perfectly constructive. I only took care never to assume that every machine either halts or not (such an assumption is implicit in the definition of $UC$). So perhaps you should stick to constructive mathematics, and there will be fewer surprises for you.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7785 Ask a Question Download Related Notes/Documents