0
$\begingroup$

The following is from Arora and Barak's "Computational Complexity." I think one does not have to read the second paragraph of the proof to answer this question.

Theorem 1.10 There exists a function $\operatorname{UC}:\{0,1\}^*\to\{0,1\}$ that is not computable by any TM (turing machine).

Proof: The function $\operatorname{UC}$ is defined as follows: For every $\alpha\in\{0,1\}^*$, if $M_\alpha(\alpha)=1$, then $\operatorname{UC}(\alpha)=0$; otherwise (if $M_\alpha(\alpha)$ outputs a different value or enters an infinite loop), $\operatorname{UC}(\alpha)=1$.

Suppose for the sake of contradiction that $\operatorname{UC}$ is computable and hence there exists a TM $M$ such that $M(\alpha)=\operatorname{UC}(\alpha)$ for every $\alpha\in\{0,1\}^*$. Then, in particular, $M(\lfloor M\rfloor) = \operatorname{UC}(\lfloor M\rfloor)$. But this is impossible: By the definition of $\operatorname{UC}$, \begin{equation} \operatorname{UC}(\lfloor M\rfloor)=1 \Leftrightarrow M(\lfloor M\rfloor)\neq 1 \end{equation}

My question is, how can one be sure that $\operatorname{UC}$ is well-defined? What if the result of $M_\alpha(\alpha)$ is mathematically undetermined (i.e., Both $M_\alpha(\alpha)=1$ and its negation are not provable from the axioms)?


Notations. $\{0,1\}^*$ is the set of all strings composed of $0$ and $1$. $M_\alpha$ is the turing machine represented by the string $\alpha$. $\lfloor M\rfloor$ is a string representing the turing machine $M$.

$\endgroup$
12
  • 4
    $\begingroup$ The assumption here is that even if something is unprovable, it can still be either true or false. $\endgroup$ Apr 12 at 10:54
  • 1
    $\begingroup$ $\mathsf{UC}$ is well-defined by excluded middle: either $M_\alpha(\alpha) = 1$ or not. The whole thing has nothing to do with provability, nor is the assumption "even if something is unprovable it can still be true or false" present anywhere (and it's a really strange "assumption" to make in the first place). $\endgroup$ Apr 12 at 15:08
  • $\begingroup$ @PeterShor: it is not an assumption that statements are either true or false, even when unprovable. That's just the law of excluded middle. Or are you talking about intuitionistic mathematics? $\endgroup$ Apr 12 at 23:27
  • 2
    $\begingroup$ @Andrej Bauer: The law of the excluded middle is an assumption. $\endgroup$ Apr 13 at 0:06
  • $\begingroup$ @PeterShor: Thank you for making your position clear. It is of course a valid possibility, namely making every mathematical statement you ever utter contingent on all the laws of logic. I am not sure this is the best way to explain the current question, however. $\endgroup$ Apr 13 at 5:34

1 Answer 1

1
$\begingroup$

The question is not research-level but since some of the comments following it may be confusing, allow me to explain precisely how functions are defined by cases.

Suppose we would like to define a function $f : A \to B$ by cases, like this: $$ f(x) = \begin{cases} e_1(x) & \text{if $\phi(x)$},\\ e_2(x) & \text{if $\psi(x)$}, \end{cases} $$ where expressions $e_1(x)$ and $e_2(x)$may depend on $x$. When is this a valid definition? In set theory (and many other kinds of foundations) a function is the same thing as a functional relation, so let us recall what that means.

Definition: A relation $R \subseteq A \times B$ is functional when for every $x \in A$ there exists exactly one $y \in B$ such that $(x, y) \in R$. The function $f_R : A \to B$ determined by such a functional relation maps $x \in A$ to the (unique) $y \in B$ for which $(x,y) \in R$.

The above definition by cases can be written in terms of functional relations, as follows. Define $R \subseteq A \times B$ by $$R = \{(x,y) \in A \times B \mid (\phi(x) \Rightarrow y = e_1) \land (\psi(x) \Rightarrow y = e_2) \}. $$ The $f$ defined by cases is then precisely $f_R$. But the question is, what condition must $\phi(x)$ and $\psi(x)$ satisfy in order for $R$ to be functional? A little exercise in logic shows that two conditions must be met:

  1. Overlap: for all $x \in A$, if $\phi(x)$ and $\psi(x)$ then $e_1 = e_2$.

  2. Cover: for all $x \in A$, $\phi(x)$ or $\psi(x)$.

Indeed, agreement on overlap guarantees that $R$ is single-valued, and the cover condition that it is total.

Now we look at the definition given by the OP:

$$ \mathrm{UC}(\alpha) = \begin{cases} 0 & \text{if $M_\alpha(\alpha)$ is defined and $M_\alpha(\alpha) = 1$}\\ 1 & \text{if $M_\alpha(\alpha)$ is not defined or $M_\alpha(\alpha) \neq 1$} \end{cases} $$ So in this case $\phi(x)$ is “$M_\alpha(\alpha)$ is defined and $M_\alpha(\alpha) = 1$” and $\psi(x)$ is $\neg \phi(x)$. Clearly, the overlap condition is satisfied because there is no $\alpha$ satisfying both $\phi(\alpha)$ and $\neg \phi(\alpha)$. The cover condition holds because $\phi(\alpha) \lor \neg \phi(\alpha)$ is true by the law of excluded middle (this would be problematic if we worked in intuitionistic logic, where excluded middle is not accepted). In conclusion, $\mathrm{UC}$ is well defined.

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