Computable explanations

✍ Scribed by J. V. Howard

• Publisher: John Wiley and Sons
• Year: 1975
• Tongue: English
• Weight: 697 KB
• Volume: 21
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19750210129

✦ Synopsis

und Cjrundhgen d. M d h . lid. 21. SK. 215-224 (1975) COMPUTABLE EXPLANATIONS by J. .. HOWARD in Harrow, Middlesex (Great Brit,ain) I . Introduction 'l'liis paper is concerned with the problem of finding explanations for sequences of O ' S atid 1 's. ('lassification of deterministic explanations for such sequences is achieved in l(t*c*ursive Function Theory, and in the notion of definable sets of natural numbers.

H( ever, we are interested in the more general problem, where statistical explanations of t t i v nryuencc are to be permitted. VON MISES [ l ] defined the idea of a random ~~~~i i ~~t i c e of 0's and 1's as one in which the limiting frequency, p, of 0's in the sequence exists, and for which no rule can be given for choosing an infinite subsequence in wlric.11 this limiting frequency is not p. CHURCH [2] made this definition precise by taking * * I i i k " to mean "algorithm" (i.e. computable procedure). It is, however, easy to think of stat istical explanations which are far more complicated than " 0's occur independently wit ti constant probability p".

1 1 1 Section 2 we define what we mean by an "explanation", and what we mean by saving that a n explanation "explains" a particular infinite sequence of 0's and 1's.

one would hope, if a sequence is produced in accordance with a particular explanation, t l i c b i i that explanation will almost certainly explain it. We show that there are int.splic*able sequences. It is shown that sequences explained by "0's occur independently with probability 3" (for example) form a proper subset of the VON MISES-CHURCH

S ~~I I C I I C C S

with limiting frequency 4. This is because some of these sequences can be bettw explained by saying t h a t 0's occur independently with probability p(n) in the n'th place, where p ( n ) tends to 4 as n tends t o infinity.