Contemporary Mathematics
Volume 257, 2000
Randomness in Computability Theory
KLAUS AMBOS-SPIES AND ANTONIN KUCERA
ABSTRACT.
We discuss some aspects of algorithmic randomness and state
some open problems in this area. The first part is devoted to the question
"What is a computably random sequence?" Here we survey some of the ap-
proaches to algorithmic randomness and address some questions on these con-
cepts. In the second part we look at the Turing degrees of Martin-LOf random
sets. Finally, in the third part we deal with relativized randomness. Here we
look at oracles which do not change randomness.
1.
Introduction
Formalizations of the intuitive notions of computability and randomness are
among the major achievements in the foundations of mathematics in the 20th cen-
tury.
It is commonly accepted that various equivalent formal computability notions -
like Turing computability or J.t-recursiveness- which were introduced in the 1930s
and 1940s adequately capture computability in the intuitive sense. This belief
is expressed in
the well known Church-Turing thesis (see Soare
[30]
for a recent
account of the history of formal computability).
The process of formalizing randomness took a long time. In part this was due
to the fact that randomness in an absolute sense does not exist. So one faced
the problem to decide which form of restricted randomness adequately captures
the intuitive notion. In 1940 Church suggested that intuitive randomness should
be viewed as algorithmic randomness and he proposed a formal computable ran-
domness notion. His thesis became widely accepted but his formal concept had
some flaws from the statistical point of view. In 1966, however, Martin-Lof
[22]
introduced a new formal concept of algorithmic randomness which eliminated these
insufficiencies and which is widely considered to be adequate.
In this note we discuss some aspects of algorithmic randomness focusing on
some open problems. In the first part (Section 2) we review some of the important
formal randomness notions introduced in the literature and pose some still open
problems arising from these notions. In particular we discuss the shift from com-
putable randomness (Church) to computably enumerable randomness (Martin-Lof)
which still leaves open the question whether there is an adequate formalization of
computable randomness. The second part (Section 3) is devoted to (Martin-Lof)
1980 Mathematics Subject Classification. Primary 03080; Secondary 03028.
©
2000 American Mathematical Society
1
http://dx.doi.org/10.1090/conm/257/04023
Previous Page Next Page