[FOM] universal machine as a primitive instruction

[Wouter Stekelenburg]

Dear David,


I think combinatory logic and partial combinatory algebras answer your
question.

I assume that the universal-partial-function operation is some partial
binary function *:A×A->A, where the first variable is the program and the
second is the input. The set of *partial combinatory functions* for this
function is the least set of arbitrary-ary functions which contains all
projections (x :-> x_i) and which is closed under pointwise application of
*, i.e. if f and g are combinatory and (f*g)(x)=f(x)*g(x) when defined,
then f*g is partial combinatory. I assume that all of partial combinatroy
functions are also computable and that by universality, there is an c in A
for each partial combinatory f: A^n -> A such that (c*x_1)...)*x_n = f(x)
for all x in the domain of f. This is *conditional partial combinatory
algebra* and that implies that there is an embedding E of the natural
numbers A such that each partial recursive function has a code, i.e. for
each arbitrary ary partial recursive f, there is a d in A such that
((d*x_1)...)*x_n = f(x) for all x in the domain of f.

Assuming that universality means that arbitrary-ary partial combinatory
functions have a code is a stretch. If you want to stick with universality
for unary functions, then you need to assume a computable surjection A->A×A
and an equivalent of the S_n_m-theorem to go along with that. I don't know
such a fix if not all partial combinatory arrows are computable.

Sincerely,


Wouter Stekelenburg
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130416/d31f4980/attachment.html>