[FOM] universal machine as a primitive instruction

T.Forster at dpmms.cam.ac.uk T.Forster at dpmms.cam.ac.uk
Fri Apr 19 10:03:31 EDT 2013


Can someone spell this out please?   It looks paedogically useful.


On Apr 19 2013, David Leduc wrote:

>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.
>


More information about the FOM mailing list