This one is from "A Programming Approach to Computability" , by A.J. Kfoury, Robert Moll, & Michael Arbib (1982), on page 77.(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Algorithmic specifications

Loading...

Similar Threads for Algorithmic specifications |
---|

B Probability of loto hitting a specific place |

I A specific combination problem |

A Pairing algorithm |

B Bellman's and Bellman-Ford algorithm |

I Dijkstra's algorithm spp |

**Physics Forums | Science Articles, Homework Help, Discussion**