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: 93,098

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

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.
Supposi t i o n as Quant i f i c a t i o n versus Supposi t i o n as Globa l Quant i f i c a t i o n a l Ef fec t.Terence Parsons - unknown
Existence of Certain Finite Relation Algebras Implies Failure of Omitting Types for L n.Tarek Sayed Ahmed - 2020 - Notre Dame Journal of Formal Logic 61 (4):503-519.
Thephilosophyofautomatedtheoremproving.Francis Jeffry Pelletier - unknown
Penrose's new argument.Per Lindström - 2001 - Journal of Philosophical Logic 30 (3):241-250.
Jerarquías de ciudadanía en el nuevo orden global.Stephen Castles - 2003 - Anales de la Cátedra Francisco Suárez 37:9-33.
Guillermo de ockham Y el nacimiento Del laicismo moderno.Nicolás López Calera - 2012 - Anales de la Cátedra Francisco Suárez 46:263-280.
Can a many-valued language functionally represent its own semantics?Jeffrey Ketland - 2003 - Analysis 63 (4):292–297.
Neocons Y teocons: Fundamentalismo versus democracia.Elías Díaz Cintas - 2010 - Anales de la Cátedra Francisco Suárez 44:61-79.
Policentrismo versus soberanía. Los nuevos órdenes normativos.José Eduardo Faria - 2010 - Anales de la Cátedra Francisco Suárez 44:295-309.

Analytics

Added to PP
2009-02-15

Downloads
109 (#166,382)

6 months
1 (#1,516,603)

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