MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is almost certainly a silly question, but:

I am currently reading Moschovakis' article "Kleene's amazing second recursion theorem" ( 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|cite|improve this question
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 Schweber Oct 19 '13 at 1:06
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|cite|improve this answer
Excellent answer - thank you very much! – Noah Schweber 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


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.