Computational complexity and Gödel's incompleteness theorem

✍ Scribed by Chaitin, G. J.

• Book ID: 125441651
• Publisher: Association for Computing Machinery
• Year: 1971
• Weight: 120 KB
• Volume: 9
• Category: Article
• ISSN: 0163-5700
• DOI: 10.1145/1247066.1247068

✦ Synopsis

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). On the other hand, almost all finite binary sequences S satisfy L(S) < L(F). The proof resembles Berry's paradox, not the Epimenides nor Richard paradoxes.