Document (#43603)

Author

Chaitin, G.J.

Title

Algorithmic information theory

Source

IBM journal research and development. 21(1977) no.4, S.350-359

Year

1977

Abstract

This paper reviews algorithmic information theory, which is an attempt to apply information-theoretic and probabilistic ideas to recursive function theory. Typical concerns in this approach are, for example, the number of bits of information required to specify an algorithm, or the probability that a program whose bits are chosen by coin flipping produces a given output. During the past few years the definitions of algorithmic information theory have been reformulated. The basic features of the new formalism are presented here and certain results of R. M. Solovay are reported.

Content

DOI: 10.1147/rd.214.0350.

Footnote

Vgl.: https://ieeexplore.ieee.org/document/5390997.

Theme

Information

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 (1987) 0.42

   0.42380318 = sum of:
     0.42380318 = product of:
       1.3243849 = sum of:
         0.059082065 = weight(abstract_txt:program in 4175) [ClassicSimilarity], result of:
           0.059082065 = score(doc=4175,freq=1.0), product of:
             0.094884746 = queryWeight, product of:
               1.0151855 = boost
               5.6930003 = idf(docFreq=404, maxDocs=44218)
               0.016417604 = queryNorm
             0.6226719 = fieldWeight in 4175, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6930003 = idf(docFreq=404, maxDocs=44218)
               0.109375 = fieldNorm(doc=4175)
         0.08677098 = weight(abstract_txt:chosen in 4175) [ClassicSimilarity], result of:
           0.08677098 = score(doc=4175,freq=1.0), product of:
             0.12259581 = queryWeight, product of:
               1.1539447 = boost
               6.4711404 = idf(docFreq=185, maxDocs=44218)
               0.016417604 = queryNorm
             0.70778096 = fieldWeight in 4175, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.4711404 = idf(docFreq=185, maxDocs=44218)
               0.109375 = fieldNorm(doc=4175)
         0.14777555 = weight(abstract_txt:probability in 4175) [ClassicSimilarity], result of:
           0.14777555 = score(doc=4175,freq=2.0), product of:
             0.13876641 = queryWeight, product of:
               1.2276919 = boost
               6.8847027 = idf(docFreq=122, maxDocs=44218)
               0.016417604 = queryNorm
             1.064923 = fieldWeight in 4175, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               6.8847027 = idf(docFreq=122, maxDocs=44218)
               0.109375 = fieldNorm(doc=4175)
         0.15728967 = weight(abstract_txt:theoretic in 4175) [ClassicSimilarity], result of:
           0.15728967 = score(doc=4175,freq=1.0), product of:
             0.18226057 = queryWeight, product of:
               1.4069983 = boost
               7.890225 = idf(docFreq=44, maxDocs=44218)
               0.016417604 = queryNorm
             0.86299336 = fieldWeight in 4175, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.890225 = idf(docFreq=44, maxDocs=44218)
               0.109375 = fieldNorm(doc=4175)
         0.29687697 = weight(abstract_txt:coin in 4175) [ClassicSimilarity], result of:
           0.29687697 = score(doc=4175,freq=1.0), product of:
             0.2783622 = queryWeight, product of:
               1.7388109 = boost
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.016417604 = queryNorm
             1.0665132 = fieldWeight in 4175, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.109375 = fieldNorm(doc=4175)
         0.032127175 = weight(abstract_txt:information in 4175) [ClassicSimilarity], result of:
           0.032127175 = score(doc=4175,freq=2.0), product of:
             0.08579348 = queryWeight, product of:
               2.1585362 = boost
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.016417604 = queryNorm
             0.37447104 = fieldWeight in 4175, 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=4175)
         0.11954269 = weight(abstract_txt:theory in 4175) [ClassicSimilarity], result of:
           0.11954269 = score(doc=4175,freq=1.0), product of:
             0.24095057 = queryWeight, product of:
               3.2354984 = boost
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.016417604 = queryNorm
             0.4961295 = fieldWeight in 4175, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.109375 = fieldNorm(doc=4175)
         0.42491984 = weight(abstract_txt:algorithmic in 4175) [ClassicSimilarity], result of:
           0.42491984 = score(doc=4175,freq=1.0), product of:
             0.5098836 = queryWeight, product of:
               4.076086 = boost
               7.61935 = idf(docFreq=58, maxDocs=44218)
               0.016417604 = queryNorm
             0.8333664 = fieldWeight in 4175, 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=4175)
       0.32 = coord(8/25)
   

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

   0.08246606 = sum of:
     0.08246606 = product of:
       0.51541287 = sum of:
         0.06453739 = weight(abstract_txt:ideas in 969) [ClassicSimilarity], result of:
           0.06453739 = score(doc=969,freq=1.0), product of:
             0.09206734 = queryWeight, product of:
               5.6078424 = idf(docFreq=440, maxDocs=44218)
               0.016417604 = queryNorm
             0.7009803 = fieldWeight in 969, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6078424 = idf(docFreq=440, maxDocs=44218)
               0.125 = fieldNorm(doc=969)
         0.119420685 = weight(abstract_txt:probability in 969) [ClassicSimilarity], result of:
           0.119420685 = score(doc=969,freq=1.0), product of:
             0.13876641 = queryWeight, product of:
               1.2276919 = boost
               6.8847027 = idf(docFreq=122, maxDocs=44218)
               0.016417604 = 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.025962677 = weight(abstract_txt:information in 969) [ClassicSimilarity], result of:
           0.025962677 = score(doc=969,freq=1.0), product of:
             0.08579348 = queryWeight, product of:
               2.1585362 = boost
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.016417604 = 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.3054921 = weight(abstract_txt:theory in 969) [ClassicSimilarity], result of:
           0.3054921 = score(doc=969,freq=5.0), product of:
             0.24095057 = queryWeight, product of:
               3.2354984 = boost
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.016417604 = 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.16 = coord(4/25)
   

3. Wong, S.K.M.: On modelling information retrieval with probabilistic inference (1995) 0.08

   0.07614269 = sum of:
     0.07614269 = product of:
       0.38071346 = sum of:
         0.048403047 = weight(abstract_txt:ideas in 1938) [ClassicSimilarity], result of:
           0.048403047 = score(doc=1938,freq=1.0), product of:
             0.09206734 = queryWeight, product of:
               5.6078424 = idf(docFreq=440, maxDocs=44218)
               0.016417604 = queryNorm
             0.52573526 = fieldWeight in 1938, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.6078424 = idf(docFreq=440, maxDocs=44218)
               0.09375 = fieldNorm(doc=1938)
         0.12080773 = weight(abstract_txt:probabilistic in 1938) [ClassicSimilarity], result of:
           0.12080773 = score(doc=1938,freq=2.0), product of:
             0.134455 = queryWeight, product of:
               1.2084695 = boost
               6.7769065 = idf(docFreq=136, maxDocs=44218)
               0.016417604 = queryNorm
             0.89849937 = fieldWeight in 1938, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               6.7769065 = idf(docFreq=136, maxDocs=44218)
               0.09375 = fieldNorm(doc=1938)
         0.089565516 = weight(abstract_txt:probability in 1938) [ClassicSimilarity], result of:
           0.089565516 = score(doc=1938,freq=1.0), product of:
             0.13876641 = queryWeight, product of:
               1.2276919 = boost
               6.8847027 = idf(docFreq=122, maxDocs=44218)
               0.016417604 = queryNorm
             0.6454409 = fieldWeight in 1938, 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=1938)
         0.019472009 = weight(abstract_txt:information in 1938) [ClassicSimilarity], result of:
           0.019472009 = score(doc=1938,freq=1.0), product of:
             0.08579348 = queryWeight, product of:
               2.1585362 = boost
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.016417604 = queryNorm
             0.22696373 = fieldWeight in 1938, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.09375 = fieldNorm(doc=1938)
         0.10246516 = weight(abstract_txt:theory in 1938) [ClassicSimilarity], result of:
           0.10246516 = score(doc=1938,freq=1.0), product of:
             0.24095057 = queryWeight, product of:
               3.2354984 = boost
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.016417604 = queryNorm
             0.42525387 = fieldWeight in 1938, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.09375 = fieldNorm(doc=1938)
       0.2 = coord(5/25)
   

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

   0.075132705 = sum of:
     0.075132705 = product of:
       0.6261059 = sum of:
         0.032127175 = weight(abstract_txt:information in 974) [ClassicSimilarity], result of:
           0.032127175 = score(doc=974,freq=2.0), product of:
             0.08579348 = queryWeight, product of:
               2.1585362 = boost
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.016417604 = 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.16905887 = weight(abstract_txt:theory in 974) [ClassicSimilarity], result of:
           0.16905887 = score(doc=974,freq=2.0), product of:
             0.24095057 = queryWeight, product of:
               3.2354984 = boost
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.016417604 = 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.42491984 = weight(abstract_txt:algorithmic in 974) [ClassicSimilarity], result of:
           0.42491984 = score(doc=974,freq=1.0), product of:
             0.5098836 = queryWeight, product of:
               4.076086 = boost
               7.61935 = idf(docFreq=58, maxDocs=44218)
               0.016417604 = 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.12 = coord(3/25)
   

5. Pross, T.: ¬An action-theory-based treatment of temporal individuals (2014) 0.07

   0.074915014 = sum of:
     0.074915014 = product of:
       0.37457508 = sum of:
         0.07837238 = weight(abstract_txt:specify in 3408) [ClassicSimilarity], result of:
           0.07837238 = score(doc=3408,freq=1.0), product of:
             0.16635148 = queryWeight, product of:
               1.3441896 = boost
               7.538004 = idf(docFreq=63, maxDocs=44218)
               0.016417604 = queryNorm
             0.47112525 = fieldWeight in 3408, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.538004 = idf(docFreq=63, maxDocs=44218)
               0.0625 = fieldNorm(doc=3408)
         0.08987981 = weight(abstract_txt:theoretic in 3408) [ClassicSimilarity], result of:
           0.08987981 = score(doc=3408,freq=1.0), product of:
             0.18226057 = queryWeight, product of:
               1.4069983 = boost
               7.890225 = idf(docFreq=44, maxDocs=44218)
               0.016417604 = queryNorm
             0.49313906 = fieldWeight in 3408, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.890225 = idf(docFreq=44, maxDocs=44218)
               0.0625 = fieldNorm(doc=3408)
         0.09673646 = weight(abstract_txt:formalism in 3408) [ClassicSimilarity], result of:
           0.09673646 = score(doc=3408,freq=1.0), product of:
             0.19141594 = queryWeight, product of:
               1.4419037 = boost
               8.085969 = idf(docFreq=36, maxDocs=44218)
               0.016417604 = queryNorm
             0.50537306 = fieldWeight in 3408, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.085969 = idf(docFreq=36, maxDocs=44218)
               0.0625 = fieldNorm(doc=3408)
         0.012981338 = weight(abstract_txt:information in 3408) [ClassicSimilarity], result of:
           0.012981338 = score(doc=3408,freq=1.0), product of:
             0.08579348 = queryWeight, product of:
               2.1585362 = boost
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.016417604 = queryNorm
             0.15130915 = fieldWeight in 3408, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4209464 = idf(docFreq=10677, maxDocs=44218)
               0.0625 = fieldNorm(doc=3408)
         0.09660508 = weight(abstract_txt:theory in 3408) [ClassicSimilarity], result of:
           0.09660508 = score(doc=3408,freq=2.0), product of:
             0.24095057 = queryWeight, product of:
               3.2354984 = boost
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.016417604 = queryNorm
             0.40093318 = fieldWeight in 3408, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.5360413 = idf(docFreq=1287, maxDocs=44218)
               0.0625 = fieldNorm(doc=3408)
       0.2 = coord(5/25)