Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is almost certainly a silly question, but:

I am currently reading Moschovakis' article "Kleene's amazing second recursion theorem" (http://www.math.ucla.edu/~ynm/papers/1602-002-1.pdf) and there is a footnote in it which confuses me.

In footnote 10, on page 195, Moschovakis writes:

. . . [T]he operation $$\Phi(p)=\begin{cases} 1, & \text{if $p(0)\downarrow$ or $p(1)\downarrow$,}\\ \perp, & \text{otherwise}\\ \end{cases}$$ is effective but not computable by a deterministic Turing machine.

Here "operations" are functions on indices of programs which take the same value on indices representing the same partial computable function (bottom of pg. 194): so in more conventional terminology, $\Phi(e)=1$ if $\varphi_e(0)\downarrow$ or $\varphi_e(1)\downarrow$, and is undefined otherwise.

The problem I'm having is that this seems completely false. Deterministic Turing machines compute exactly the same functions as nondeterministic Turing machines.

But of course Moschovakis knows this, so my question is:

What is Moschovakis actually saying?

I am sure the answer is quite simple, but I don't see it.

share|improve this question
2  
By "computable" he means can be computed "by value". See the last paragraph on the previous page. –  Michal R. Przybylek Oct 18 '13 at 22:47
    
Oh, I see! Somehow I missed that. If you post your comment as an answer, I'll accept it. –  Noah S Oct 19 '13 at 1:06

1 Answer 1

up vote 6 down vote accepted

Moschovakis by "computable" means: can be computed "by values" (see the last paragraph on the previous page). Where "computed by values" refers to the fact that we do not have access to the definition of a function, but can only ask for values of the function on its arguments.

There is, however, much deeper context of the footnote. The operation: $$\Phi(p)=\begin{cases} 1, & \text{if $p(0)\downarrow$ or $p(1)\downarrow$,}\\ \perp, & \text{otherwise}\\ \end{cases}$$ is a variant of "parallel or" function: \begin{array} \\ 1 &\mathit{or}& {-} &=& 1 \\ {-} &\mathit{or}& 1 &=& 1 \\ 0 &\mathit{or}& 0 &=& 0 \\ \end{array} highly studied in computer science in the context of denotational semantics. The undefinability of "parallel or" in "sequential" calculi was the main obstacle to have a fully abstract continuous (domain-theoretic) semantics. This crucial observation led to some famous works (mostly by Plotkin and Milner) on the full abstraction theorem for PCF (a typed lambda calculus with a fixed-point operation).

share|improve this answer
    
Excellent answer - thank you very much! –  Noah S Oct 19 '13 at 19:35
    
So in fact this is a sort of precursor to parallel or? –  Andrej Bauer Oct 19 '13 at 20:40
    
Andrej, I'm simply not old enough to be good at history :-), but the way Moschovakis presents these results looks pretty modern (and not necessary natural) to me. –  Michal R. Przybylek Oct 20 '13 at 17:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.