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