[FOM] universal machine as a primitive instruction

T.Forster at dpmms.cam.ac.uk T.Forster at dpmms.cam.ac.uk
Fri Apr 12 06:51:29 EDT 2013

Have i missed answers to this? It seems like a sensible question if i 
understand it correctly. There obviously can be no universal FDA and (less 
obviously) no universal PDA. What about linear bounded automata? Is 
Turing-computable the only notion of computability that supports a 
universal machine?

  If true, it looks like the kind of fact one would like to prove in a 
course like my fourth-year computability-and-logic course here...

On Apr 10 2013, David Leduc wrote:

>I have a question about computability. I am sure it is well known but
>I cannot find the answer in my textbooks.
>For any system that is Turing complete, one can define a universal
>machine in this system.
>But I want to do thing the other way round. Assume a system that has a
>universal machine as one of its primitive instructions. What are the
>other primitives needed to make this system Turing-complete?
>Thanks for any suggestion!!
>FOM mailing list
>FOM at cs.nyu.edu

More information about the FOM mailing list