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.

  • 2
    $\begingroup$ By "computable" he means can be computed "by value". See the last paragraph on the previous page. $\endgroup$ Oct 18 '13 at 22:47
  • $\begingroup$ Oh, I see! Somehow I missed that. If you post your comment as an answer, I'll accept it. $\endgroup$ Oct 19 '13 at 1:06

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

  • $\begingroup$ Excellent answer - thank you very much! $\endgroup$ Oct 19 '13 at 19:35
  • $\begingroup$ So in fact this is a sort of precursor to parallel or? $\endgroup$ Oct 19 '13 at 20:40
  • $\begingroup$ 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. $\endgroup$ Oct 20 '13 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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