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.010904 = sum of:
     6.010904 = weight(author_txt:chaitin in 2448) [ClassicSimilarity], result of:
       6.010904 = fieldWeight in 2448, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.617446 = idf(docFreq=7, maxDocs=44218)
         0.625 = fieldNorm(doc=2448)
   

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

   6.010904 = sum of:
     6.010904 = weight(author_txt:chaitin in 4479) [ClassicSimilarity], result of:
       6.010904 = fieldWeight in 4479, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.617446 = idf(docFreq=7, maxDocs=44218)
         0.625 = fieldNorm(doc=4479)
   

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

   6.010904 = sum of:
     6.010904 = weight(author_txt:chaitin in 974) [ClassicSimilarity], result of:
       6.010904 = fieldWeight in 974, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.617446 = idf(docFreq=7, maxDocs=44218)
         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.010904 = sum of:
     6.010904 = weight(author_txt:chaitin in 2212) [ClassicSimilarity], result of:
       6.010904 = fieldWeight in 2212, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.617446 = idf(docFreq=7, maxDocs=44218)
         0.625 = fieldNorm(doc=2212)
   

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

   6.010904 = sum of:
     6.010904 = weight(author_txt:chaitin in 2422) [ClassicSimilarity], result of:
       6.010904 = fieldWeight in 2422, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         9.617446 = idf(docFreq=7, maxDocs=44218)
         0.625 = fieldNorm(doc=2422)
   

Similar documents (content)

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

   0.37112904 = sum of:
     0.37112904 = product of:
       1.1597782 = sum of:
         0.06934337 = weight(abstract_txt:chosen in 601) [ClassicSimilarity], result of:
           0.06934337 = score(doc=601,freq=1.0), product of:
             0.11430174 = queryWeight, product of:
               1.0175791 = boost
               6.4711404 = idf(docFreq=185, maxDocs=44218)
               0.017358167 = queryNorm
             0.6066694 = fieldWeight in 601, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.4711404 = idf(docFreq=185, maxDocs=44218)
               0.09375 = fieldNorm(doc=601)
         0.021785583 = weight(abstract_txt:information in 601) [ClassicSimilarity], result of:
           0.021785583 = score(doc=601,freq=4.0), product of:
             0.047993537 = queryWeight, product of:
               1.1420727 = boost
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.017358167 = queryNorm
             0.45392746 = fieldWeight in 601, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.09375 = fieldNorm(doc=601)
         0.12569866 = weight(abstract_txt:theoretic in 601) [ClassicSimilarity], result of:
           0.12569866 = score(doc=601,freq=1.0), product of:
             0.16992997 = queryWeight, product of:
               1.2407284 = boost
               7.890225 = idf(docFreq=44, maxDocs=44218)
               0.017358167 = queryNorm
             0.7397086 = fieldWeight in 601, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.890225 = idf(docFreq=44, maxDocs=44218)
               0.09375 = fieldNorm(doc=601)
         0.23725042 = weight(abstract_txt:coin in 601) [ClassicSimilarity], result of:
           0.23725042 = score(doc=601,freq=1.0), product of:
             0.25952998 = queryWeight, product of:
               1.5333295 = boost
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.017358167 = queryNorm
             0.9141542 = fieldWeight in 601, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.09375 = fieldNorm(doc=601)
         0.094431326 = weight(abstract_txt:program in 601) [ClassicSimilarity], result of:
           0.094431326 = score(doc=601,freq=1.0), product of:
             0.17693087 = queryWeight, product of:
               1.7904348 = boost
               5.6930003 = idf(docFreq=404, maxDocs=44218)
               0.017358167 = queryNorm
             0.53371876 = fieldWeight in 601, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6930003 = idf(docFreq=404, maxDocs=44218)
               0.09375 = fieldNorm(doc=601)
         0.12410101 = weight(abstract_txt:theory in 601) [ClassicSimilarity], result of:
           0.12410101 = score(doc=601,freq=3.0), product of:
             0.16848701 = queryWeight, product of:
               2.139861 = boost
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.017358167 = queryNorm
             0.7365613 = fieldWeight in 601, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.09375 = fieldNorm(doc=601)
         0.16701216 = weight(abstract_txt:probability in 601) [ClassicSimilarity], result of:
           0.16701216 = score(doc=601,freq=1.0), product of:
             0.2587567 = queryWeight, product of:
               2.1652224 = boost
               6.8847027 = idf(docFreq=122, maxDocs=44218)
               0.017358167 = queryNorm
             0.6454409 = fieldWeight in 601, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.8847027 = idf(docFreq=122, maxDocs=44218)
               0.09375 = fieldNorm(doc=601)
         0.32015568 = weight(abstract_txt:algorithmic in 601) [ClassicSimilarity], result of:
           0.32015568 = score(doc=601,freq=2.0), product of:
             0.31692538 = queryWeight, product of:
               2.3962672 = boost
               7.61935 = idf(docFreq=58, maxDocs=44218)
               0.017358167 = queryNorm
             1.0101926 = fieldWeight in 601, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.61935 = idf(docFreq=58, maxDocs=44218)
               0.09375 = fieldNorm(doc=601)
       0.32 = coord(8/25)
   

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

   0.08463684 = sum of:
     0.08463684 = product of:
       0.52898026 = sum of:
         0.014523722 = weight(abstract_txt:information in 969) [ClassicSimilarity], result of:
           0.014523722 = score(doc=969,freq=1.0), product of:
             0.047993537 = queryWeight, product of:
               1.1420727 = boost
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.017358167 = queryNorm
             0.3026183 = fieldWeight in 969, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.125 = fieldNorm(doc=969)
         0.07815534 = weight(abstract_txt:book in 969) [ClassicSimilarity], result of:
           0.07815534 = score(doc=969,freq=1.0), product of:
             0.1287477 = queryWeight, product of:
               1.5273075 = boost
               4.856341 = idf(docFreq=934, maxDocs=44218)
               0.017358167 = queryNorm
             0.6070426 = fieldWeight in 969, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.856341 = idf(docFreq=934, maxDocs=44218)
               0.125 = fieldNorm(doc=969)
         0.2136183 = weight(abstract_txt:theory in 969) [ClassicSimilarity], result of:
           0.2136183 = score(doc=969,freq=5.0), product of:
             0.16848701 = queryWeight, product of:
               2.139861 = boost
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.017358167 = queryNorm
             1.2678621 = fieldWeight in 969, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.125 = fieldNorm(doc=969)
         0.22268286 = weight(abstract_txt:probability in 969) [ClassicSimilarity], result of:
           0.22268286 = score(doc=969,freq=1.0), product of:
             0.2587567 = queryWeight, product of:
               2.1652224 = boost
               6.8847027 = idf(docFreq=122, maxDocs=44218)
               0.017358167 = queryNorm
             0.86058784 = fieldWeight in 969, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.8847027 = idf(docFreq=122, maxDocs=44218)
               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.07670583 = sum of:
     0.07670583 = product of:
       0.47941142 = sum of:
         0.037733737 = weight(abstract_txt:information in 5217) [ClassicSimilarity], result of:
           0.037733737 = score(doc=5217,freq=12.0), product of:
             0.047993537 = queryWeight, product of:
               1.1420727 = boost
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.017358167 = queryNorm
             0.7862254 = fieldWeight in 5217, product of:
               3.4641016 = tf(freq=12.0), with freq of:
                 12.0 = termFreq=12.0
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.09375 = fieldNorm(doc=5217)
         0.058616508 = weight(abstract_txt:book in 5217) [ClassicSimilarity], result of:
           0.058616508 = score(doc=5217,freq=1.0), product of:
             0.1287477 = queryWeight, product of:
               1.5273075 = boost
               4.856341 = idf(docFreq=934, maxDocs=44218)
               0.017358167 = queryNorm
             0.45528197 = fieldWeight in 5217, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.856341 = idf(docFreq=934, maxDocs=44218)
               0.09375 = fieldNorm(doc=5217)
         0.2075558 = weight(abstract_txt:concerned in 5217) [ClassicSimilarity], result of:
           0.2075558 = score(doc=5217,freq=3.0), product of:
             0.20738423 = queryWeight, product of:
               1.9384053 = boost
               6.163498 = idf(docFreq=252, maxDocs=44218)
               0.017358167 = queryNorm
             1.0008273 = fieldWeight in 5217, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               6.163498 = idf(docFreq=252, maxDocs=44218)
               0.09375 = fieldNorm(doc=5217)
         0.17550536 = weight(abstract_txt:theory in 5217) [ClassicSimilarity], result of:
           0.17550536 = score(doc=5217,freq=6.0), product of:
             0.16848701 = queryWeight, product of:
               2.139861 = boost
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.017358167 = queryNorm
             1.0416551 = fieldWeight in 5217, product of:
               2.4494898 = tf(freq=6.0), with freq of:
                 6.0 = termFreq=6.0
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.09375 = fieldNorm(doc=5217)
       0.16 = coord(4/25)
   

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

   0.07499026 = sum of:
     0.07499026 = product of:
       0.4686891 = sum of:
         0.01797219 = weight(abstract_txt:information in 974) [ClassicSimilarity], result of:
           0.01797219 = score(doc=974,freq=2.0), product of:
             0.047993537 = queryWeight, product of:
               1.1420727 = boost
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.017358167 = queryNorm
             0.37447104 = fieldWeight in 974, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.109375 = fieldNorm(doc=974)
         0.06838592 = weight(abstract_txt:book in 974) [ClassicSimilarity], result of:
           0.06838592 = score(doc=974,freq=1.0), product of:
             0.1287477 = queryWeight, product of:
               1.5273075 = boost
               4.856341 = idf(docFreq=934, maxDocs=44218)
               0.017358167 = queryNorm
             0.53116226 = fieldWeight in 974, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.856341 = idf(docFreq=934, maxDocs=44218)
               0.109375 = fieldNorm(doc=974)
         0.11821605 = weight(abstract_txt:theory in 974) [ClassicSimilarity], result of:
           0.11821605 = score(doc=974,freq=2.0), product of:
             0.16848701 = queryWeight, product of:
               2.139861 = boost
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.017358167 = queryNorm
             0.70163304 = fieldWeight in 974, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.109375 = fieldNorm(doc=974)
         0.26411495 = weight(abstract_txt:algorithmic in 974) [ClassicSimilarity], result of:
           0.26411495 = score(doc=974,freq=1.0), product of:
             0.31692538 = queryWeight, product of:
               2.3962672 = boost
               7.61935 = idf(docFreq=58, maxDocs=44218)
               0.017358167 = queryNorm
             0.8333664 = fieldWeight in 974, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.61935 = idf(docFreq=58, maxDocs=44218)
               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.06941017 = sum of:
     0.06941017 = product of:
       0.43381354 = sum of:
         0.065811306 = weight(abstract_txt:computational in 4344) [ClassicSimilarity], result of:
           0.065811306 = score(doc=4344,freq=1.0), product of:
             0.11038665 = queryWeight, product of:
               6.3593493 = idf(docFreq=207, maxDocs=44218)
               0.017358167 = queryNorm
             0.596189 = fieldWeight in 4344, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.3593493 = idf(docFreq=207, maxDocs=44218)
               0.09375 = fieldNorm(doc=4344)
         0.021785583 = weight(abstract_txt:information in 4344) [ClassicSimilarity], result of:
           0.021785583 = score(doc=4344,freq=4.0), product of:
             0.047993537 = queryWeight, product of:
               1.1420727 = boost
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.017358167 = queryNorm
             0.45392746 = fieldWeight in 4344, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.09375 = fieldNorm(doc=4344)
         0.1198324 = weight(abstract_txt:concerned in 4344) [ClassicSimilarity], result of:
           0.1198324 = score(doc=4344,freq=1.0), product of:
             0.20738423 = queryWeight, product of:
               1.9384053 = boost
               6.163498 = idf(docFreq=252, maxDocs=44218)
               0.017358167 = queryNorm
             0.57782793 = fieldWeight in 4344, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.163498 = idf(docFreq=252, maxDocs=44218)
               0.09375 = fieldNorm(doc=4344)
         0.22638425 = weight(abstract_txt:algorithmic in 4344) [ClassicSimilarity], result of:
           0.22638425 = score(doc=4344,freq=1.0), product of:
             0.31692538 = queryWeight, product of:
               2.3962672 = boost
               7.61935 = idf(docFreq=58, maxDocs=44218)
               0.017358167 = queryNorm
             0.71431404 = fieldWeight in 4344, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.61935 = idf(docFreq=58, maxDocs=44218)
               0.09375 = fieldNorm(doc=4344)
       0.16 = coord(4/25)