[FOM] uniform reflexive structures

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
        http://www.cs.nyu.edu/mailman/listinfo/fom
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)
Message-ID:
        <CAJtrDvrfuGy4OmqfPCGgvspMGZxm3JvPJQa34AS=GMJH1f4MCA at mail.gmail.com>
Content-Type: text/plain; charset=UTF-8

I wonder whether there is a relationship to partial combinatory algebra

http://ncatlab.org/nlab/show/partial%20combinatory%20algebra

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
>

------------------------------

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
Message-ID:
        <
20130422203351.Horde.BOM6Egf4dFipJezHbRzaCw5.jkennedy at webmail.helsinki.fi>

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

Of interest:

http://www.helsinki.fi/recruitment/index.html?id=66423
--
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
http://www.math.helsinki.fi/logic/people/juliette.kennedy/

------------------------------

_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom

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