Recursion Theory and Effective Aspects of Randomness

点击翻译按钮获取中文摘要

Slaman proposes to investigate the effective aspects of randomness. The central questionto be answered is, "How can we evaluate the random content of an infinite binarysequence?" One case is well understood, that in which an infinite sequence X of 0'sand 1's is random if and only if each digit is chosen independently and with equalprobability for the values of 0 and 1. In this case, X's being effectively random hasbeen equivalently characterized by Martin-Lof in terms of X's having the propertiesof almost all infinite sequences and by Kolmogorov and others in terms of X's beingunpredictable and indescribable. Slaman proposes to study the non-uniform case, itsassociated criteria for effective randomness, and its possibilities for the sets of randomsequences. Even the most basic questions are open. For example, for a given infi-nite binary sequence X, under what conditions does there exist a measure relative towhich X is random? This is a classic mathematical problem, given an individual dataset determine a distribution which would generate it. Qualitatively, a measure relativeto which X is random concentrates on the nonrandom aspects of X and thereby separatesthose from the random ones. Other ways to quantify X's random content includethe complexity of X's initial segments and X's ability to compute uniformly randomsequences. The proposal is to investigate all of these and the relationships betweenthem.