Computation of recursive functionals using minimal initial segments (Q787965)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computation of recursive functionals using minimal initial segments |
scientific article |
Statements
Computation of recursive functionals using minimal initial segments (English)
0 references
1983
0 references
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.
0 references
recursive functional
0 references
Martin-Löf test
0 references
amount of information
0 references
algorithmic information theory
0 references