[FOM] Uniformly Reflexive Structures (URS)
Harvey Friedman
hmflogic at gmail.com
Tue Apr 16 16:39:43 EDT 2013
>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
More information about the FOM
mailing list