[FOM] universal machine as a primitive instruction

[Samuel E. Moelius III]

This email considers David Leduc's question [1] in the context of
effective numberings, e.g., as in John Tucker's email on 4/15/2013 [2].

Recall that an effective numbering is a partial computable function
mapping N x N into N.  Intuitively, such an object "numbers" (via its
first argument) a set of partial computable functions mapping N into N.

Within this context, suppose that we interpret having a "universal
machine as one of its primitive instructions" as follows.  Say that an
effective numbering psi has this property iff there exists a pairing
function <.,.> (i.e., <.,.> is a computable bijection from N x N into N)
and an element u of N such that, for each p and x in N,

  psi(u,<p,x>) = psi(p,x).

Then, as a first observation, note that if psi is any constant function,
then psi has this property.  In particular, any u and any <.,.> satisfy
the above equation.  However, a constant function is obviously not
Turing complete.

For additional examples, fix any computably enumerable, proper subset A
of N, and let psi be any effective numbering of the partial computable
functions whose range is a subset of A.  Then, it is not hard to see
that such a psi also satisfies the above equation.  However, because A
is a proper subset of N, there will not exist, e.g., any p such that
psi(p,.) is the identity function.  Therefore, psi is again not Turing
complete.

So, interpreted in this way, having a universal machine as a primitive
instruction is considerably weak.

Furthermore, if it is not already known, then perhaps an interesting
research question is: is there an intuitive characterization of the
effective numberings which contain their own universal machine in the
above sense?

Sam

[1] http://www.cs.nyu.edu/pipermail/fom/2013-April/017210.html

[2] http://www.cs.nyu.edu/pipermail/fom/2013-April/017222.html