2
$\begingroup$

Recursion theorem (paraphrasing Sipser, Introduction to the Theory of Computation):

Let T be a program that computes a function t: N x N --> N. There is a program R that computes a function r: N --> N, where for every w,

        t(<R>, w) = r(w)

The proof is by construction. The program R thus constructed computes the same thing as program T with one input fixed at <R>. But what if the right side does not compute anything? In that event we can reason as follows:

T(<R>, w) halts  <-->  R(w) halts

and by modus tollens

T(<R>, w)  does not halt  <-->  R(w) does not halt

In particular we have

R(w) halts  --> T(<R>, w) halts
T(<R>, w)  does not halt  --> R(w) does not halt

The transposition is based on the table below

T(<R>, w) halts__________________R(w) halts

   T                         T
   F                         F

But what if the value in the right column is unknown and unknowable?

T(<R>, w) halts__________________R(w) halts

   T                         T
   ?                     unknowable 
   F                         F

We know that there is no universal halting decider, so the value in the right column may be unknowable to a given decider. So what if the decider concludes that T(<R>,w) does not halt? Is there anything wrong with the table below?

T(<R>, w) halts__________________R(w) halts

   T                         T
   F                     unknowable
   F                         F

In particular is there any compelling reason that if the value in the left column is F that the value in right column must also be F, i.e. that it cannot remain unknowable? It seems to me that if T(<R>, w) does not halt then it does not imply anything.

Is it possible for a decider to say [for some T] that T(<R>, w) does NOT halt yet remain agnostic about R(w) halting??

$\endgroup$
1
$\begingroup$

The recursion theorem states that for every two-place partially computable function $t$ there is a program $R$ which computes a partial function $r$ satisfying $$ r(w) = t(\langle R \rangle, w) $$ for all $w$. The function $t$ is given by a program that doesn't necessarily halt, and so we can think of it as a function from $\mathbb{N}^2$ to $\mathbb{N} \cup \{ \bot \}$, where $\bot$ means that the program doesn't halt. We call such a function a partial function, since a different way of specifying such a function is as a function from some subset $S \subseteq \mathbb{N}^2$ to $\mathbb{N}$; the function doesn't halt on inputs outside $S$.

The equality $r(w) = t(\langle R \rangle, w)$ is an equality of partial functions: the functions have the same domain (or the same set of inputs on which the output is a natural number rather than $\bot$), and they agree on their domain.

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