Document (#41176)

Author

Chaitin, G.J.

Title

Algorithmic information theory

Imprint

Cambridge : Cambridge University Press

Year

1987

Pages

X, 175 S

Isbn

0-521-34306-2

Series

Cambridge tracts in theoretical computer science ; 1

Abstract

Chaitin, the inventor of algorithmic information theory, presents in this book the strongest possible version of Gödel's incompleteness theorem, using an information theoretic approach based on the size of computer programs. One half of the book is concerned with studying the halting probability of a universal computer if its program is chosen by tossing a coin. The other half is concerned with encoding the halting probability as an algebraic equation in integers, a so-called exponential diophantine equation.

Theme

Information

Field

Informatik

LCSH

Machine theory
Computational complexity
LISP (Computer program language)

RSWK

Algorithmus / Informatik
Gödelscher Unvollständigkeitssatz
Metamathematik / LISP

BK

54.10 (Theoretische Informatik)
31.02 (Philosophie und Wissenschaftstheorie der Mathematik)

DDC

006.31

SBB

Mat T 1068 / Informationstheorie

GHBS

TVB (E)
TVI (HA)

LCC

QA267

RVK

SK 130

Similar documents (author)

1. Chaitin, G.J.: Gödel's theorem and information (1982) 6.01

   6.0137663 = sum of:
     6.0137663 = weight(author_txt:chaitin in 2447) [ClassicSimilarity], result of:
       6.0137663 = fieldWeight in 2447, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.622026 = idf(docFreq=7, maxDocs=44421)
         0.625 = fieldNorm(doc=2447)
   

2. Chaitin, G.: ¬Die Grenzen der Gewissheit (2006) 6.01

   6.0137663 = sum of:
     6.0137663 = weight(author_txt:chaitin in 4478) [ClassicSimilarity], result of:
       6.0137663 = fieldWeight in 4478, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.622026 = idf(docFreq=7, maxDocs=44421)
         0.625 = fieldNorm(doc=4478)
   

3. Chaitin, G.J.: ¬The limits of mathematics (1997) 6.01

   6.0137663 = sum of:
     6.0137663 = weight(author_txt:chaitin in 974) [ClassicSimilarity], result of:
       6.0137663 = fieldWeight in 974, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.622026 = idf(docFreq=7, maxDocs=44421)
         0.625 = fieldNorm(doc=974)
   

4. Chaitin, G.J.: Conversations with a mathematician : Math, art, science and the limits of reason (2002) 6.01

   6.0137663 = sum of:
     6.0137663 = weight(author_txt:chaitin in 3212) [ClassicSimilarity], result of:
       6.0137663 = fieldWeight in 3212, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.622026 = idf(docFreq=7, maxDocs=44421)
         0.625 = fieldNorm(doc=3212)
   

5. Chaitin, G.J.: Grenzen der Berechenbarkeit (2004) 6.01

   6.0137663 = sum of:
     6.0137663 = weight(author_txt:chaitin in 3422) [ClassicSimilarity], result of:
       6.0137663 = fieldWeight in 3422, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.622026 = idf(docFreq=7, maxDocs=44421)
         0.625 = fieldNorm(doc=3422)
   

Similar documents (content)

1. Chaitin, G.J.: Algorithmic information theory (1977) 0.37

   0.36504492 = sum of:
     0.36504492 = product of:
       1.1407654 = sum of:
         0.06985523 = weight(abstract_txt:chosen in 1602) [ClassicSimilarity], result of:
           0.06985523 = score(doc=1602,freq=1.0), product of:
             0.11506401 = queryWeight, product of:
               1.0198613 = boost
               6.475721 = idf(docFreq=185, maxDocs=44421)
               0.017422492 = queryNorm
             0.6070988 = fieldWeight in 1602, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.475721 = idf(docFreq=185, maxDocs=44421)
               0.09375 = fieldNorm(doc=1602)
         0.021844357 = weight(abstract_txt:information in 1602) [ClassicSimilarity], result of:
           0.021844357 = score(doc=1602,freq=4.0), product of:
             0.048163734 = queryWeight, product of:
               1.1428574 = boost
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.017422492 = queryNorm
             0.45354366 = fieldWeight in 1602, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.09375 = fieldNorm(doc=1602)
         0.12657815 = weight(abstract_txt:theoretic in 1602) [ClassicSimilarity], result of:
           0.12657815 = score(doc=1602,freq=1.0), product of:
             0.17101967 = queryWeight, product of:
               1.2433529 = boost
               7.894805 = idf(docFreq=44, maxDocs=44421)
               0.017422492 = queryNorm
             0.74013793 = fieldWeight in 1602, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.894805 = idf(docFreq=44, maxDocs=44421)
               0.09375 = fieldNorm(doc=1602)
         0.22915755 = weight(abstract_txt:coin in 1602) [ClassicSimilarity], result of:
           0.22915755 = score(doc=1602,freq=1.0), product of:
             0.25403664 = queryWeight, product of:
               1.515373 = boost
               9.622026 = idf(docFreq=7, maxDocs=44421)
               0.017422492 = queryNorm
             0.902065 = fieldWeight in 1602, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.622026 = idf(docFreq=7, maxDocs=44421)
               0.09375 = fieldNorm(doc=1602)
         0.094909355 = weight(abstract_txt:program in 1602) [ClassicSimilarity], result of:
           0.094909355 = score(doc=1602,freq=1.0), product of:
             0.17783731 = queryWeight, product of:
               1.7930723 = boost
               5.6926546 = idf(docFreq=406, maxDocs=44421)
               0.017422492 = queryNorm
             0.5336864 = fieldWeight in 1602, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6926546 = idf(docFreq=406, maxDocs=44421)
               0.09375 = fieldNorm(doc=1602)
         0.124238625 = weight(abstract_txt:theory in 1602) [ClassicSimilarity], result of:
           0.124238625 = score(doc=1602,freq=3.0), product of:
             0.16890585 = queryWeight, product of:
               2.1402 = boost
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.017422492 = queryNorm
             0.73554957 = fieldWeight in 1602, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.09375 = fieldNorm(doc=1602)
         0.16763104 = weight(abstract_txt:probability in 1602) [ClassicSimilarity], result of:
           0.16763104 = score(doc=1602,freq=1.0), product of:
             0.2598483 = queryWeight, product of:
               2.1674361 = boost
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.017422492 = queryNorm
             0.6451112 = fieldWeight in 1602, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.09375 = fieldNorm(doc=1602)
         0.3065512 = weight(abstract_txt:algorithmic in 1602) [ClassicSimilarity], result of:
           0.3065512 = score(doc=1602,freq=2.0), product of:
             0.3084198 = queryWeight, product of:
               2.3613343 = boost
               7.496775 = idf(docFreq=66, maxDocs=44421)
               0.017422492 = queryNorm
             0.99394137 = fieldWeight in 1602, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.496775 = idf(docFreq=66, maxDocs=44421)
               0.09375 = fieldNorm(doc=1602)
       0.32 = coord(8/25)
   

2. Klir, G.I.; Wierman, M.J.: Uncertainty-based information : Elements of generalized information theory (1998) 0.08

   0.08488105 = sum of:
     0.08488105 = product of:
       0.5305066 = sum of:
         0.014562904 = weight(abstract_txt:information in 969) [ClassicSimilarity], result of:
           0.014562904 = score(doc=969,freq=1.0), product of:
             0.048163734 = queryWeight, product of:
               1.1428574 = boost
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.017422492 = queryNorm
             0.30236244 = fieldWeight in 969, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.125 = fieldNorm(doc=969)
         0.07858042 = weight(abstract_txt:book in 969) [ClassicSimilarity], result of:
           0.07858042 = score(doc=969,freq=1.0), product of:
             0.12943964 = queryWeight, product of:
               1.5297483 = boost
               4.8566523 = idf(docFreq=938, maxDocs=44421)
               0.017422492 = queryNorm
             0.60708153 = fieldWeight in 969, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.8566523 = idf(docFreq=938, maxDocs=44421)
               0.125 = fieldNorm(doc=969)
         0.21385519 = weight(abstract_txt:theory in 969) [ClassicSimilarity], result of:
           0.21385519 = score(doc=969,freq=5.0), product of:
             0.16890585 = queryWeight, product of:
               2.1402 = boost
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.017422492 = queryNorm
             1.2661207 = fieldWeight in 969, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.125 = fieldNorm(doc=969)
         0.22350806 = weight(abstract_txt:probability in 969) [ClassicSimilarity], result of:
           0.22350806 = score(doc=969,freq=1.0), product of:
             0.2598483 = queryWeight, product of:
               2.1674361 = boost
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.017422492 = queryNorm
             0.86014825 = fieldWeight in 969, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.881186 = idf(docFreq=123, maxDocs=44421)
               0.125 = fieldNorm(doc=969)
       0.16 = coord(4/25)
   

3. Bremer, M.; Cohnitz, D.: Information and information flow : an introduction (2004) 0.08

   0.07692496 = sum of:
     0.07692496 = product of:
       0.480781 = sum of:
         0.03783553 = weight(abstract_txt:information in 217) [ClassicSimilarity], result of:
           0.03783553 = score(doc=217,freq=12.0), product of:
             0.048163734 = queryWeight, product of:
               1.1428574 = boost
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.017422492 = queryNorm
             0.7855606 = fieldWeight in 217, product of:
               3.4641016 = tf(freq=12.0), with freq of:
                 12.0 = termFreq=12.0
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.09375 = fieldNorm(doc=217)
         0.05893531 = weight(abstract_txt:book in 217) [ClassicSimilarity], result of:
           0.05893531 = score(doc=217,freq=1.0), product of:
             0.12943964 = queryWeight, product of:
               1.5297483 = boost
               4.8566523 = idf(docFreq=938, maxDocs=44421)
               0.017422492 = queryNorm
             0.45531115 = fieldWeight in 217, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.8566523 = idf(docFreq=938, maxDocs=44421)
               0.09375 = fieldNorm(doc=217)
         0.20831017 = weight(abstract_txt:concerned in 217) [ClassicSimilarity], result of:
           0.20831017 = score(doc=217,freq=3.0), product of:
             0.20824926 = queryWeight, product of:
               1.9403411 = boost
               6.160204 = idf(docFreq=254, maxDocs=44421)
               0.017422492 = queryNorm
             1.0002925 = fieldWeight in 217, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               6.160204 = idf(docFreq=254, maxDocs=44421)
               0.09375 = fieldNorm(doc=217)
         0.17569998 = weight(abstract_txt:theory in 217) [ClassicSimilarity], result of:
           0.17569998 = score(doc=217,freq=6.0), product of:
             0.16890585 = queryWeight, product of:
               2.1402 = boost
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.017422492 = queryNorm
             1.0402243 = fieldWeight in 217, product of:
               2.4494898 = tf(freq=6.0), with freq of:
                 6.0 = termFreq=6.0
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.09375 = fieldNorm(doc=217)
       0.16 = coord(4/25)
   

4. Chaitin, G.J.: ¬The limits of mathematics (1997) 0.07

   0.0732828 = sum of:
     0.0732828 = product of:
       0.4580175 = sum of:
         0.018020675 = weight(abstract_txt:information in 974) [ClassicSimilarity], result of:
           0.018020675 = score(doc=974,freq=2.0), product of:
             0.048163734 = queryWeight, product of:
               1.1428574 = boost
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.017422492 = queryNorm
             0.37415442 = fieldWeight in 974, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.109375 = fieldNorm(doc=974)
         0.06875786 = weight(abstract_txt:book in 974) [ClassicSimilarity], result of:
           0.06875786 = score(doc=974,freq=1.0), product of:
             0.12943964 = queryWeight, product of:
               1.5297483 = boost
               4.8566523 = idf(docFreq=938, maxDocs=44421)
               0.017422492 = queryNorm
             0.53119636 = fieldWeight in 974, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.8566523 = idf(docFreq=938, maxDocs=44421)
               0.109375 = fieldNorm(doc=974)
         0.11834715 = weight(abstract_txt:theory in 974) [ClassicSimilarity], result of:
           0.11834715 = score(doc=974,freq=2.0), product of:
             0.16890585 = queryWeight, product of:
               2.1402 = boost
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.017422492 = queryNorm
             0.70066935 = fieldWeight in 974, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.529811 = idf(docFreq=1301, maxDocs=44421)
               0.109375 = fieldNorm(doc=974)
         0.2528918 = weight(abstract_txt:algorithmic in 974) [ClassicSimilarity], result of:
           0.2528918 = score(doc=974,freq=1.0), product of:
             0.3084198 = queryWeight, product of:
               2.3613343 = boost
               7.496775 = idf(docFreq=66, maxDocs=44421)
               0.017422492 = queryNorm
             0.81995976 = fieldWeight in 974, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.496775 = idf(docFreq=66, maxDocs=44421)
               0.109375 = fieldNorm(doc=974)
       0.16 = coord(4/25)
   

5. Buckland, M.: ¬The landscape of information science : the American Society for Information Science at 62 (1999) 0.07

   0.06795675 = sum of:
     0.06795675 = product of:
       0.4247297 = sum of:
         0.065853 = weight(abstract_txt:computational in 5344) [ClassicSimilarity], result of:
           0.065853 = score(doc=5344,freq=1.0), product of:
             0.11062602 = queryWeight, product of:
               6.3496094 = idf(docFreq=210, maxDocs=44421)
               0.017422492 = queryNorm
             0.5952759 = fieldWeight in 5344, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.3496094 = idf(docFreq=210, maxDocs=44421)
               0.09375 = fieldNorm(doc=5344)
         0.021844357 = weight(abstract_txt:information in 5344) [ClassicSimilarity], result of:
           0.021844357 = score(doc=5344,freq=4.0), product of:
             0.048163734 = queryWeight, product of:
               1.1428574 = boost
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.017422492 = queryNorm
             0.45354366 = fieldWeight in 5344, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               2.4188995 = idf(docFreq=10748, maxDocs=44421)
               0.09375 = fieldNorm(doc=5344)
         0.12026793 = weight(abstract_txt:concerned in 5344) [ClassicSimilarity], result of:
           0.12026793 = score(doc=5344,freq=1.0), product of:
             0.20824926 = queryWeight, product of:
               1.9403411 = boost
               6.160204 = idf(docFreq=254, maxDocs=44421)
               0.017422492 = queryNorm
             0.5775191 = fieldWeight in 5344, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.160204 = idf(docFreq=254, maxDocs=44421)
               0.09375 = fieldNorm(doc=5344)
         0.21676442 = weight(abstract_txt:algorithmic in 5344) [ClassicSimilarity], result of:
           0.21676442 = score(doc=5344,freq=1.0), product of:
             0.3084198 = queryWeight, product of:
               2.3613343 = boost
               7.496775 = idf(docFreq=66, maxDocs=44421)
               0.017422492 = queryNorm
             0.7028227 = fieldWeight in 5344, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.496775 = idf(docFreq=66, maxDocs=44421)
               0.09375 = fieldNorm(doc=5344)
       0.16 = coord(4/25)