- #1

- 1,036

- 1

## Main Question or Discussion Point

This one is from "A Programming Approach to Computability" , by A.J. Kfoury, Robert Moll, & Michael Arbib (1982), on page 77.

[This section continues as follows:

Are these guys kidding, or what?

In every previous instance that I have found in this book, they used [itex]\leq[/itex] to represent "less than or equal to". Here, I guess maybe they are using it to signify "is a subset of". But even if that's the case, how do they conclude (in the second paragraph), that "if [itex]\sigma(y)[/itex] is defined, it equals [itex]\mu(y)[/itex]"?

I can't say that I like this stuff, but I'm determined to understand it if I can, so any suggestions will be appreciated.

How do they get all that out of [itex]\sigma \leq \mu [/itex] ???3 ExampleLet [itex]\sigma:N \rightarrow N [/itex] and [itex] \mu:N \rightarrow N[/itex] be two computable functions such that [itex]\sigma \leq \mu [/itex]. This means that whenever [itex]\sigma (y) [/itex] is defined, so is [itex] \mu (y) [/itex], and in this case we must have [itex]\sigma (y) = \mu (y) [/itex]. Thus [itex]\sigma [/itex] is a subset of [itex]\mu[/itex] when considered as a set of ordered pairs of natural numbers.

[This section continues as follows:

Now define [itex]\psi_3[/itex] by the specification:

[tex]\psi_3(x,y) = \left \{ \begin{array} {cc} \mu(y), &\text{if} \;\phi_x(x)\downarrow \\

\sigma (y), &otherwise \end{array}\right[/tex]

At first glance, the second line asks us to return a value [itex]\sigma(y)[/itex] based on the assumption that computationP_{x}on x runs on forever. But on closer inspection, we realize that [itex]\sigma \leq \mu [/itex] tells us that if [itex]\sigma(y)[/itex] is defined it equals [itex]\mu(y)[/itex]. Thus we can compute [itex]\psi_3(x,y)[/itex] as follows: Start the computations of [itex]\sigma(y)[/itex] and ofP_{x}at the same time. If a result [itex]\sigma(y)[/itex] is returned, halt--for then [itex]\sigma (y) = \mu (y) [/itex] is the desired answer, no matter whether or notP_{x}halts on x. But ifP_{x}halts on x before a result [itex]\sigma(y)[/itex] is returned, stop computing [itex]\sigma(y)[/itex] and start computing [itex]\mu(y)[/itex]. If and when this computation halts, the [itex]\mu(y)[/itex] then returned is the desired answer.

Are these guys kidding, or what?

In every previous instance that I have found in this book, they used [itex]\leq[/itex] to represent "less than or equal to". Here, I guess maybe they are using it to signify "is a subset of". But even if that's the case, how do they conclude (in the second paragraph), that "if [itex]\sigma(y)[/itex] is defined, it equals [itex]\mu(y)[/itex]"?

I can't say that I like this stuff, but I'm determined to understand it if I can, so any suggestions will be appreciated.