Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
Thanks for the explanation of functionality condition in classical logic. As you guess, I am a little unaccustomed to functions of this form. In the last paragraph, you mentioned that we could still talk about the undecidability of the Halting Problem by simply skipping the things about function. I have no idea about how to achieve this without reduction from $UC$ function or something just like that. Could you explain it a bit more? Thank you. –  hengxin Jan 5 '13 at 13:36
    
I changed the answer to maek it more accurate. Is this better? –  Andrej Bauer Jan 5 '13 at 14:34
    
As a greenhand, I have to think over it. I will accept it as answer in a few of days, just waiting for some other possible perspectives on the problem. By the way, are there some well-known functions defined in the way like that of $UC$ (I mean ``not constructive'') besides the field of Computability Theory or even Computer Science? –  hengxin Jan 6 '13 at 13:11
    
Sure, for example the sign function $\mathrm{sgn} : \mathbb{R} \to \lbrace -1, 0, 1 \rbrace$ which returns the sign of a real number. It is non-computable and not definable constructively. Similarly for $\mathrm{floor}$ and $\mathrm{ceil}$ (as functions on the reals, but not as functions on floating points). –  Andrej Bauer Jan 6 '13 at 17:03
    
A Google search guides me to the notions of definable and computable. Are they relevant to the problem and discussion here? –  hengxin Jan 7 '13 at 8:29
show 1 more comment

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

share|improve this answer
    
Thanks. I now have a better understanding (and acceptance) of the $UC$ function. In the last paragraph, two other functions not expressed by algorithms are given for further illustration. From the abbreviation (i.e., $BB(\alpha), KOL(\alpha)$, it seems that they own their importance. If so, could you give some relevant references (I can not find them). In addition, are there some well-known functions outside of Turing Machine and even Computer Science, of course not expressed by algorithms either? –  hengxin Jan 6 '13 at 1:47
1  
    
@usul Thank you for references. Maybe you can add it into the post directly, for other people's convenience. –  hengxin Jan 7 '13 at 7:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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