Algorithmic specifications

  • Thread starter gnome
  • Start date
  • #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.
3 Example Let [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.
How do they get all that out of [itex]\sigma \leq \mu [/itex] ???


[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 computation Px 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 of Px 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 not Px halts on x. But if Px 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.
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
It means "less than or equal to" here too. And it is synonymous with the subset relation!

It is common to partially order sets by inclusion, so the subset relation is the order on sets.


Are you familiar with the definition of a function as a set of ordered pairs?
 
  • #3
1,036
1
[itex](a,b) \in f \mbox{ and }(a,c) \in f \mbox{ implies } b=c.[/itex]

here, that becomes

[itex](y,\sigma(y)) \in \sigma \mbox{ and } (y,\mu(y)) \in \mu[/itex]?

and if [itex]\sigma \subseteq \mu[/itex], then:

[itex](y,\sigma(y)) \in \mu \mbox{ and } (y,\mu(y)) \in \mu \mbox{ so } \sigma(y)=\mu(y) [/itex]?
 
  • #4
1,036
1
That was 5 months ago. And this:
>>It is common to partially order sets by inclusion, so the subset relation is the order on sets.
was 2 years ago.

How'm I supposed to remember that? :yuck: :yuck:

Well, now it all falls into place. Thanks Hurkyl.
 
Last edited:

Related Threads on Algorithmic specifications

  • Last Post
Replies
1
Views
632
  • Last Post
Replies
1
Views
438
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
868
  • Last Post
Replies
4
Views
773
  • Last Post
Replies
2
Views
2K
  • Last Post
2
Replies
26
Views
18K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
0
Views
1K
Top