[FOM] uniform reflexive structures

Wouter Stekelenburg w.p.stekelenburg at gmail.com
Wed Apr 24 15:53:32 EDT 2013

Uniform reflexive structures look like decidable PCAs to me.

A PCA cannot always decide its own equality. To do that, it needs a
combinator d which satisfies dwxyz=y if w=x and dwxyz=z if not w=x. PCAs
that have such a d are called decidable. I believe John Longley introduced
this term in "realizability toposes and language semantics".
Op 24 apr. 2013 18:12 schreef <fom-request at cs.nyu.edu> het volgende:

Send FOM mailing list submissions to
        fom at cs.nyu.edu

To subscribe or unsubscribe via the World Wide Web, visit
or, via email, send a message with subject or body 'help' to
        fom-request at cs.nyu.edu

You can reach the person managing the list at
        fom-owner at cs.nyu.edu

When replying, please edit your Subject line so it is more specific
than "Re: Contents of FOM digest..."

Today's Topics:

   1. Re: Uniformly Reflexive Structures (URS) (Kevin Watkins)
   2. job for a logician in helsinki (jkennedy at mappi.helsinki.fi)


Message: 1
Date: Mon, 22 Apr 2013 10:11:15 -0400
From: Kevin Watkins <kevin.watkins at gmail.com>
To: Foundations of Mathematics <fom at cs.nyu.edu>
Subject: Re: [FOM] Uniformly Reflexive Structures (URS)
        <CAJtrDvrfuGy4OmqfPCGgvspMGZxm3JvPJQa34AS=GMJH1f4MCA at mail.gmail.com>
Content-Type: text/plain; charset=UTF-8

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
> that [...] it does not depend [...] on special specific functions." But
> 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>
>> 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/
>> 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


Message: 2
Date: Mon, 22 Apr 2013 20:33:51 +0300
From: jkennedy at mappi.helsinki.fi
To: "fom at cs.nyu.edu" <fom at cs.nyu.edu>
Subject: [FOM] job for a logician in helsinki
20130422203351.Horde.BOM6Egf4dFipJezHbRzaCw5.jkennedy at webmail.helsinki.fi>

Content-Type: text/plain; charset=UTF-8; format=flowed; DelSp=Yes

Of interest:

Department of Mathematics and Statistics
P.O. Box 68 (Gustaf H?llstr?min katu 2b)
FI-00014 University of Helsinki, Finland
tel. (+358-9)-191-51446, fax (+358-9)-191-51400


FOM mailing list
FOM at cs.nyu.edu

End of FOM Digest, Vol 124, Issue 16
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130424/8378cd6a/attachment.html>

More information about the FOM mailing list