[FOM] universal machine as a primitive instruction
Samuel E. Moelius III
moelius at cis.udel.edu
Fri Apr 19 08:38:08 EDT 2013
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
More information about the FOM
mailing list