5
$\begingroup$

Most proofs of Rice theorem seem to be based on the undecidability of the halting problem. They are "reduction-based".

Are there "direct" elementary proofs, perhaps based on diagonalization?

I think that the answer is "YES there are".

However most textbooks I know (such as [Odifreddi, Moret, Jones, Phillips] present reduction-based proofs.

$\endgroup$
  • 6
    $\begingroup$ Well, the undecidability of the halting problem is proved via diagonalization, so unwinding the standard proof of Rice's theorem will give you a purely diagonalization-based proof. Presumably, though, this isn't what you mean? $\endgroup$ – Noah Schweber Jan 22 '14 at 18:35
6
$\begingroup$

Here is a proof based on the recursion theorem, rather than a reduction of an undecidable problem.

Rice's Theorem. Suppose that $P$ is any set of computable functions, which is not empty and not all computable functions. Then the set $\{ e\mid \varphi_e\in P\}$ is not decidable, where $\varphi_e$ is the function computed by program $e$.

In other words, there is no general procedure to determine from a program whether the function it computes has property $P$ or not.

Proof. Suppose that the set were decidable. Fix a computable function $f$ that is in $P$, and another computable function $g$ that is not in $P$. Now, for any program $e$, let $h(e)$ be the program that on input $n$ first determines whether $\varphi_e\in P$; if so, it outputs $g(n)$, and otherwise $f(n)$. So $\varphi_{h(e)}$ is either $g$ or $f$, depending on whether $\varphi_e\in P$ or not, respectively (but note that we are using the opposite function). In particular, we'll have $$\varphi_e\in P\quad\iff\quad\varphi_{h(e)}\notin P.$$ Meanwhile, by the recursion theorem, there is a program $e$ such that $\varphi_e=\varphi_{h(e)}$, which now gives an immediate contradiction, since $\varphi_e$ and $\varphi_{h(e)}$ are supposed to be opposite with respect to $P$. QED

$\endgroup$
3
$\begingroup$

Here is a proof in a more 'constructive' form that can be directly applied to any real-world programming language. Just to make clear, a property of programs must be a predicate that only depends on the halting and output behaviour, in other words two equivalent programs will have exactly the same properties. I will use $X \equiv Y$ to denote that two programs are equivalent, and so $P$ is a property iff $P$ is a predicate and $P(X)=P(Y)$ for any programs $X \equiv Y$.

For any property $P$ of programs such that $P(T)$ and $\neg P(F)$ for some programs $T$,$F$:

  If $P$ is decidable:

    Let $D$ be a program that decides $P$

    Let $M$ be the following program on input $x$:

      Create $N$ to be the following program on input $y$:

        If $x$ is an invalid program: Return "" [may be unnecessary in some languages]

        Return $x(x)(y)$ [using closures or some interpreter written in the language itself]

      If D(N): Return F

      Return T

    Let $R$ be the program that $M(M)$ creates in the variable $N$

    Clearly $R \equiv M(M)$

    Also $M(M)$ halts because $D$ halts on all inputs

    Thus $M(M) \equiv T \vee M(M) \equiv F$

    $P(M(M)) \Leftrightarrow P(R) \Leftrightarrow D(R) = True \Leftrightarrow M(M) \equiv F \Leftrightarrow \neg P(M(M))$

    Contradiction

  Therefore $P$ is not decidable

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