Nondeterministic Turing machines and the recursion theorem

Question

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.

Answer 1

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