# Nondeterministic Turing machines and the recursion theorem

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.

• 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

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).