Incompleteness and the Halting Problem

Studia Logica 109 (5):1159-1169 (2021)
  Copy   BIBTEX

Abstract

We present an abstract framework in which we give simple proofs for Gödel’s First and Second Incompleteness Theorems and obtain, as consequences, Davis’, Chaitin’s and Kritchman-Raz’s Theorems.

Categories

Keywords

Reprint years

DOI

10.1007/s11225-021-09945-2

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,202

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Defining a Halting Decidability Decider.Pete Olcott - manuscript
The Halting Problem Is Decidable on a Set of Asymptotic Probability One.Joel David Hamkins & Alexei Miasnikov - 2006 - Notre Dame Journal of Formal Logic 47 (4):515-524.
A mechanical proof of the unsolvability of the halting problem.Robert Boyer - unknown
Algorithmic information theory and undecidability.Panu Raatikainen - 2000 - Synthese 123 (2):217-225.
Halting Problem Proof from Finite Strings to Final States.Pete Olcott - manuscript
Fictionalism and the incompleteness problem.Lukas Skiba - 2017 - Synthese 194 (4):1349-1362.
Incompleteness, complexity, randomness and beyond.Cristian S. Calude - 2002 - Minds and Machines 12 (4):503-517.
Equivalence of the Frame and Halting Problems.Eric Dietrich & Chris Fields - 2020 - Algorithms 13 (175):1-9.
Gödel's incompleteness theorems and computer science.Roman Murawski - 1997 - Foundations of Science 2 (1):123-135.
A brief critique of pure hypercomputation.Paolo Cotogno - 2009 - Minds and Machines 19 (3):391-405.
What is Mathematics: Gödel's Theorem and Around (Edition 2015).Karlis Podnieks - manuscript
Busy beaver competition and Collatz-like problems.Pascal Michel - 1993 - Archive for Mathematical Logic 32 (5):351-367.
Dilemmas of Ambiguity and Vagueness.Leon Felkins - 1996
Effective inseparability in a topological setting.Dieter Spreen - 1996 - Annals of Pure and Applied Logic 80 (3):257-275.
Kolmogorov complexity for possibly infinite computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.

Analytics

Added to PP
2021-04-16

Downloads
42 (#359,513)

6 months
15 (#143,114)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Cristian S. Calude
University of Auckland

Citations of this work

No citations found.

Add more citations

References found in this work

Introduction to metamathematics.Stephen Cole Kleene - 1952 - Groningen: P. Noordhoff N.V..
Computability & unsolvability.Martin Davis - 1958 - New York: Dover Publications.
An Introduction to Gödel's Theorems.Peter Smith - 2009 - Bulletin of Symbolic Logic 15 (2):218-222.
Introduction to a general theory of elementary propositions.Emil L. Post - 1921 - American Journal of Mathematics 43 (3):163--185.
Computational complexity and Godel's incompleteness theorem.Gregory J. Chaitin - 1970 - [Rio de Janeiro,: Centro Técnico Científico, Pontifícia Universidade Católica do Rio de Janeiro. Edited by Gregory J. Chaitin.

View all 7 references / Add more references