First Steps in Synthetic Computability Theory | Zendy

Andrej Bauer | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

First Steps in Synthetic Computability Theory

Author(s) -

Andrej Bauer

Publication year - 2006

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2005.11.049

Subject(s) - computability , computability theory , computable function , computable analysis , axiom , constructive set theory , topos theory , simple (philosophy) , axiom of choice , mathematics , turing , constructive , set theory , computer science , turing machine , discrete mathematics , algebra over a field , set (abstract data type) , pure mathematics , epistemology , algorithm , programming language , art , philosophy , geometry , literature , process (computing) , computation

Computability theory, which investigates computable functions and computable sets, lies at the foundation of computer science. Its classical presentations usually involve a fair amount of Gödel encodings which sometime obscure ingenious arguments. Consequently, there have been a number of presentations of computability theory that aimed to present the subject in an abstract and conceptually pleasing way. We build on two such approaches, Hyland's effective topos and Richman's formulation in Bishop-style constructive mathematics, and develop basic computability theory, starting from a few simple axioms. Because we want a theory that resembles ordinary mathematics as much as possible, we never speak of Turing machines and Gödel encodings, but rather use familiar concepts from set theory and topology

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research