Computation of recursive functionals using minimal initial segments (Q787965)

The computational complexity of recursive functionals has been extensively studied (e.g. by R. L. Constable, N. A. Lynch). In the paper under review, the authors initiate a different approach to this problem, namely the study of the ''amount of information'' requested by the computation of recursive functionals by measuring the length of the initial segments used as input. This approach is suggested by Kolmogorov's definition of complexity [\textit{A. N. Kolmogorov}, Probl. Peredachi Inf. 1, No.1, 3-11 (1965; Zbl 0271.94018)]; a connection with the algorithmic information theory is realized in the last technical paragraph where the authors prove that a machine for 0-1 sequences which realizes a given level of significance in a universal P. Martin-Löf test [\textit{P. Martin-Löf}, Inf. Control 9, 602-619 (1966; Zbl 0244.62008)] must have unbounded redundancy. The paper ends with a discussion concerning alternative measures for the amount of information which may be relevant in this context.