[FOM] Uniformly Reflexive Structures (URS)

Kevin Watkins kevin.watkins at gmail.com
Mon Apr 22 10:11:15 EDT 2013

I wonder whether there is a relationship to partial combinatory algebra


The axiom for alpha in URS seems similar to the axiom for s in PCA.

On Sun, Apr 21, 2013 at 9:42 AM, David Leduc
<david.leduc6 at googlemail.com> wrote:
> Thank you very much for the reference. I have no doubt it is a great work
> since you recommended it. However it is not what I expected.
> In the introduction of the first paper by Wagner on URS it is written: "we
> want to develop our axiomatic structure on a sufficiently abstract level so
> that [...] it does not depend [...] on special specific functions." But then
> two of the three axioms are stating the existence of special specific
> functions alpha and psi! Well, it looks to me like yet another
> Turing-complete programming language although this time it is disguised as
> an axiomatic system.
> D.
> On Tue, Apr 16, 2013 at 8:39 PM, Harvey Friedman <hmflogic at gmail.com> wrote:
>> 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
>> _______________________________________________
>> FOM mailing list
>> FOM at cs.nyu.edu
>> http://www.cs.nyu.edu/mailman/listinfo/fom
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom

More information about the FOM mailing list