The Kleene hierarchy classification of recursively random sequences

Introduction. In 1, Church suggests a precise formulation for the notion of random sequence as conceived by von Mises. This paper introduces a modified formulation to avoid some objections inherent in the "classical" case (see Loveland 8 or 9), and defines corresponding sets which are then located in the Kleene hierarchy of recursive unsolvability. More precisely, we locate a collection of classes in the hierarchy containing some of the defined sets, including the "lowest" class in which these sets may be found. We confine our attention to sequences of O's and l's and then make the natural correspondence between sequences and sets by associating with the infinite sequence a0, alt a2,. . . the set /1 a= 1. (We only consider infinite sequences. ) Unlike the modern concept of "random sequence, " the von Mises theory allows the label "random" or "nonrandom" to be applied to a specific sequence of outcomes of events, according as to whether or not the sequence has a given structure. In essence, if a sequence A = (a0, au a2,. . . ) of O's and l's has a certain limiting relative frequency p of l's to number of places, then every (infinite) sequence, composed of members of the sequence A, which could represent a betting scheme played by someone attempting to "beat" the system, (i. e. , achieve a different limiting relative frequency) must indeed result in the limiting relative frequency p. The intuitive concept of "betting scheme" is this: if we regard the indices of the given sequence as indicating the order of performance of the "events" (such as coin-tossing) and the corresponding sequence entries as the outcomes of these events, the "betting scheme" is some effective rule wherein the better observes outcomes of certain events and then uses this information to select an event on which to bet, the selection being made without knowledge of the outcome of that event. If the selection rule allows an infinite number of selections (bets) to be made over the infinite sequence, it is called a proper selection rule, otherwise it is improper with respect to that sequence. Only betting schemes that are proper selection rules shall be of concern in identifying random sequences. ("Effective rule" here means