What is a computation?

MaRDI QIDQ5448298zbMATH OpenFDO

Authors Martin Davis

Publication date 20 March 2008

zbMATH Keywords

computation theoryhalting problemHilbert's tenth problemPost logicTuring machines

Mathematics Subject Classification ID

History of mathematical logic and foundations (03-03) Philosophical and critical aspects of logic and foundations (03A05) Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10) Higher degree equations; Fermat's equation (11D41) Polynomials (11S05) Free semigroups, generators and relations, word problems (20M05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Introduction to computability
• A Mechanical Proof of the Unsolvability of the Halting Problem
• The problem of termination of programs
• Conceptual Confluence in 1936: Post and Turing
• On the Church-Turing thesis and relative recursion

Cited in

(3)

• Incompleteness and the halting problem
• Turing's vision. The birth of computer science
• The problem of termination of programs

This page was built for publication: What is a computation?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5448298)