[FOM] universal machine as a primitive instruction

David Leduc david.leduc6 at googlemail.com
Fri Apr 19 09:53:26 EDT 2013


Of course, that's it, combinatory logic! Thank you very much Wouter. I
guess another answer might simply be lambda-calculus where also the
application can be interpreted as a universal machine.

On Fri, Apr 12, 2013 at 10:51 AM,  <T.Forster at dpmms.cam.ac.uk> wrote:
> Is Turing-computable the only notion of computability
> that supports a universal machine?

I would say no. Because if you take combinatory logic without the
combinator K but with only S and * then you get a notion of computability
that supports a universal machine but is  not Turing-computable...hmmm...
is it right?

D.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130419/2c1a4c43/attachment.html>


More information about the FOM mailing list