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

Question

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.

Answer 1

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:

1. $H$ halts on every input.
2. If $M_\alpha$ halts on $x$ then $H$ on input $(\alpha, x)$ outputs $1$.
3. 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.

Answer 2

The function $UC$ is well-defined. Of course, the definition is not given by some sort of algorithm but by a formal statement. In particular, the value of $UC(\alpha)$ can be either 1, if some condition $X$ is satisfied, or 0 if condition $Y$ is satisfied. But since $X$ ($M_\alpha(\alpha)=1$) is the negation of $Y$ ($M_\alpha(\alpha)\neq 1$) the definition is well-defined. It would not be well-defined if $X$ and $Y$ could both hold, or none of $X$ and $Y$ could hold.

Notice that a definition of a function can be expressed by an algorithm, but this is not necessarily the case. Other not-computable functions with a short definition are $$\begin{align} \text{BB}(\alpha)&:=\text{maximal number of cells a halting Turing machine with $\alpha$ states can print},\\ \text{KOL}(\alpha)&:=\text{minimal size of a Turing machine program that prints $\alpha$ and stops}. \end{align}$$

(These are the busy-beaver function and Kolmogorov complexity.)