[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