Abstract:
An explicit recursion-theoretic definition of the program-size complexity measure operating on finite strings of symbols was given by Chaitin [17]-[18], Kolmogorov [47] and Solomonoff [65] in the 60's. The modified version of program-size complexity leading to the break- through in program size theory and its applications has been presented by Chaitin [21], Levin [55] and Schnorr [63]. We will investigate mainly the computational properties of both program-size complexity measures with an emphasis on using techniques of classical computability theory. After the introduction and summary in Chapter II we will study the phenomenon of autocomputability of infinite sequences which naturally can be considered as being opposite to incompressibility. Moreover, we will study some structural properties of uft-reducibility and solve the problem of elementary equivalence for this reducibility.