Computational complexity and Godel's incompleteness theorem

Abstract

Given any simply consistent formal theory F of the state complexity L(S) of finite binary sequences S as computed by 3-tape-symbol Turing machines, there exists a natural number L(F ) such that L(S) > n is provable in F only if n L(F ). The proof resembles Berry’s..

Categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,813

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

  • Only published works are available at libraries.

My notes

Similar books and articles

Gödel's Incompleteness Results.Haim Gaifman - unknown
Edgar Morin's paradigm of complexity and gödel's incompleteness theorem.Yi-Zhuang Chen - 2004 - World Futures 60 (5 & 6):421 – 431.
The Surprise Examination Paradox and the Second Incompleteness Theorem.Shira Kritchman & Ran Raz - unknown
On the philosophical relevance of Gödel's incompleteness theorems.Panu Raatikainen - 2005 - Revue Internationale de Philosophie 59 (4):513-534.
Chaitin interview for simply gödel website.Palle Yourgrau - unknown
Fromal statements of Godel's second incompleteness theorem.Harvey Friedman - manuscript
Some upper and lower bounds on decision procedures in logic.Jeanne Ferrante - 1974 - Cambridge: Project MAC, Massachusetts Institute of Technology.
On interpreting Chaitin's incompleteness theorem.Panu Raatikainen - 1998 - Journal of Philosophical Logic 27 (6):569-586.
Existentially closed structures and gödel's second incompleteness theorem.Zofia Adamowicz & Teresa Bigorajska - 2001 - Journal of Symbolic Logic 66 (1):349-356.
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.

Analytics

Added to PP
2009-02-15

Downloads
109 (#165,002)

6 months
1 (#1,507,095)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

No references found.

Add more references