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
    0 references
    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
    0 references
    recursive functional
    0 references
    Martin-Löf test
    0 references
    amount of information
    0 references
    algorithmic information theory
    0 references
    0 references