[FOM] universal machine as a primitive instruction

[David Leduc]

Dear Wouter,

Thank you very much for your very interesting answer. I do not however
fully understand how it answers my question. Does it mean that if I have a
programming language with its only primitive instructions being the
universal-partial-function and all projections, then it is Turing-complete?
If this is the case, then how would you then define constant functions, the
successor function, the composition, the primitive recursion and the
minimisation?

Thank you very much for your help,

D.


On Tue, Apr 16, 2013 at 8:54 PM, Wouter Stekelenburg <
w.p.stekelenburg at gmail.com> wrote:

> 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
>
>
>
>
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130418/c170b3d5/attachment.html>