Computation of recursive functionals using minimal initial segments
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.
- A Machine-Independent Theory of the Complexity of Recursive Functions
- An Overview of the Theory of Computational Complexity
- scientific article; zbMATH DE number 3480091 (Why is no real title available?)
- scientific article; zbMATH DE number 3557239 (Why is no real title available?)
- scientific article; zbMATH DE number 3433847 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Minimal determining sets of locally finitely-determined functionals
- On degrees of unsolvability
- On the sequential nature of functions
- The definition of random sequences
- Minimal determining sets of locally finitely-determined functionals
- Type 2 computational complexity of functions on Cantor's space
- Comparison between the complexity of a function and the complexity of its graph
- scientific article; zbMATH DE number 782018 (Why is no real title available?)
- How much partiality is needed for a theory of computability?
This page was built for publication: Computation of recursive functionals using minimal initial segments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q787965)