Computability & Recursion Theory

A topic within Foundations & Logic, itself one of 13 topics in that field and part of Mathematics.

Reading on Computability & Recursion Theory

2 works

Essay2004

Computability and Complexity (Stanford Encyclopedia of Philosophy)

Neil Immerman

Surveys computability theory and computational complexity as one continuum, from what a Turing machine cannot decide at all to what it can decide only given resources that grow faster than any polynomial.

link checked 17 Sept 2026

Mathematics · Foundations & Logic

FreeIntermediate

Paper1936

An Unsolvable Problem of Elementary Number Theory

Alonzo Church

Uses the newly defined class of lambda-definable functions to prove there is no algorithm for deciding the truth of every well-formed proposition of elementary number theory, giving the first published solution to Hilbert's Entscheidungsproblem.

link checked 17 Sept 2026

Mathematics · Foundations & Logic

FreeAdvanced

Reading on Computability & Recursion Theory

Computability and Complexity (Stanford Encyclopedia of Philosophy)

An Unsolvable Problem of Elementary Number Theory

Other topics in Foundations & Logic