[FOM] Computability theory axiomatically

Dominic Mulligan dominic.p.mulligan at googlemail.com
Thu Sep 1 04:20:42 EDT 2016


Dear George,

It is not entirely clear what you are asking, but: are you aware of
Andrej Bauer's recent work [1] on synthetic computability theory?
That paper's introduction also gives pointers to other previous
axiomatic treatments of computability theory, of various flavours.
Perhaps also tangentially relevant is Andrea Asperti's recent work on
"reverse complexity theory" [2], and his recent publications on the
formalisation of several major results in Computational Complexity
Theory in the Calculus of Constructions (see, e.g. [3] and [4]).

Thanks,
Dominic

[1] http://math.andrej.com/data/synthetic.pdf
[2] http://link.springer.com/article/10.1007/s10817-015-9349-x
[3] http://www.cs.unibo.it/~asperti/PAPERS/gap.pdf
[4] http://dl.acm.org/citation.cfm?id=2693178

On 27 August 2016 at 21:55, George Cherevichenko
<george.cherevichenko at gmail.com> wrote:
> Several simple results (3 pages)
>
> http://www.mediafire.com/download/2u66ou5kg65rlp3/intuitionism.pdf
>
> Does anybody have more results of this sort?
>
> George
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>


More information about the FOM mailing list