[FOM] universal machine as a primitive instruction

[T.Forster at dpmms.cam.ac.uk]

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:

>Hello,
>
>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!!
>
>D.
>_______________________________________________
>FOM mailing list
>FOM at cs.nyu.edu
>http://www.cs.nyu.edu/mailman/listinfo/fom
>