[FOM] universal machine as a primitive instruction

David Leduc david.leduc6 at googlemail.com
Mon Apr 8 08:04:20 EDT 2013


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


More information about the FOM mailing list