[FOM] Uniformly Reflexive Structures (URS)

[Harvey Friedman]

>From http://www.cs.nyu.edu/pipermail/fom/2013-April/017210.html

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

You may want to look at the URS. These are the uniformly reflexive
structures of Wagner and Strong,and also Strong's BRFT. This stuff is
not sufficiently studied in recent years.

http://www.ams.org/journals/tran/1969-144-00/S0002-9947-1969-0249297-9/
http://domino.research.ibm.com/tchjr/journalindex.nsf/4ac37cf0bdc4dd6a85256547004d47e1/efac077da47cb91685256bfa00683ffe!OpenDocument

Harvey Friedman