A Machine-Independent Theory of the Complexity of Recursive Functions
From MaRDI portal
Publication:5537605
DOI10.1145/321386.321395zbMath0155.01503OpenAlexW2089442854WikidataQ55918695 ScholiaQ55918695MaRDI QIDQ5537605
No author found.
Publication date: 1967
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321386.321395
Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)
Related Items (only showing first 100 items - show all)
On speedable and levelable vector spaces ⋮ The basic theory of partial \(\alpha\)-recursive operators ⋮ Characterizing language identification by standardizing operations ⋮ On recursive bounds for the exceptional values in speed-up ⋮ Reverse complexity ⋮ Approximation to measurable functions and its relation to probabilistic computation ⋮ Program size restrictions in computational learning ⋮ The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem ⋮ Computational complexity of functions ⋮ Learning in the presence of inaccurate information ⋮ Lower bounds on degrees of game-theoretic structures ⋮ Learning languages in a union ⋮ Strongly non-U-shaped language learning results by general techniques ⋮ On aggregating teams of learning machines ⋮ On the power of recursive optimizers ⋮ Saving the phenomena: Requirements that inductive inference machines not contradict known data ⋮ Learning all subfunctions of a function ⋮ A note on the best-case complexity ⋮ Mind change speed-up for learning languages from positive data ⋮ Data representation and computational complexity ⋮ Complexity classes of provable recursive functions ⋮ Indexings of subrecursive classes ⋮ Speedup for natural problems and noncomputability ⋮ Iterative learning from texts and counterexamples using additional information ⋮ Hierarchy of complexity of computation of partial functions with values 0 and 1 ⋮ Research in the theory of inductive inference by GDR mathematicians - A survey ⋮ Complexity of algorithms and computations ⋮ The independence of control structures in abstract programming systems ⋮ A note on A.E. h-complex functions ⋮ Reversible parallel computation: An evolving space-model ⋮ Theory construction in psychology: The interpretation and integration of psychological data ⋮ Two types of properties for complexity measures ⋮ A complexity theory of efficient parallel algorithms ⋮ Optimal language learning from positive data ⋮ Parametrization over inductive relations of a bounded number of variables ⋮ On a complexity-based way of constructivizing the recursive functions ⋮ Learning recursive functions: A survey ⋮ Reflective inductive inference of recursive functions ⋮ Learning indexed families of recursive languages from positive data: A survey ⋮ Learning and extending sublanguages ⋮ Computational complexity of real functions ⋮ Non-U-shaped vacillatory and team learning ⋮ Learning languages from positive data and negative counterexamples ⋮ Optimal algorithms for co-NP-sets and the EXP\(\overset{!}{ = }\)NEXP problem ⋮ Learning in the presence of partial explanations ⋮ Learning in Friedberg numberings ⋮ Entropy algebras and Birkhoff factorization ⋮ Anomalous learning helps succinctness ⋮ Aggregating inductive expertise on partial recursive functions ⋮ Effective category and measure in abstract complexity theory ⋮ The complexity types of computable sets ⋮ A note on the diagonalizable algebras of PA and ZF ⋮ On the non-existence of maximal inference degrees for language identification ⋮ Consistent and coherent learning with \(\delta \)-delay ⋮ Diagonalization, uniformity, and fixed-point theorems ⋮ Program self-reference in constructive Scott subdomains ⋮ The extent and density of sequences within the minimal-program complexity hierarchies ⋮ On some open problems in reflective inductive inference ⋮ Closure operations on measures of computational complexity ⋮ Augmented loop languages and classes of computable functions ⋮ The non-renamability of honesty classes ⋮ Complexity classes of partial recursive functions ⋮ The computational complexity of program schemata ⋮ An operator embedding theorem for complexity classes of recursive functions ⋮ Polynomial and abstract subrecursive classes ⋮ Accepting networks of genetic processors are computationally complete ⋮ On the density of honest subrecursive classes ⋮ Nonexistence of program optimizers in several abstract settings ⋮ On computational reducibility ⋮ Complexity-class-encoding sets ⋮ Comparison of identification criteria for machine inductive inference ⋮ ``Natural properties of flowchart step-counting measures ⋮ Some natural properties of strong-identification in inductive inference ⋮ On the inference of optimal descriptions ⋮ Some applications of the McCreight-Meyer algorithm in abstract complexity theory ⋮ Characterizing programming systems allowing program self-reference ⋮ Resource restricted computability theoretic learning: Illustrative topics and problems ⋮ Speed-up theorems in type-2 computations using oracle Turing machines ⋮ On splitting recursive sets ⋮ The complexity of total order structures ⋮ Some lowness properties and computational complexity sequences ⋮ Finite approximate approach to the study of the complexity of recursive predicates ⋮ Sequential fuzzy system identification ⋮ U-shaped, iterative, and iterative-with-counter learning ⋮ A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes ⋮ Complexity properties of recursively enumerable sets and \(sQ\)-completeness ⋮ Learning with refutation ⋮ Factorizing RSA keys, an improved analogue solution ⋮ Instability, complexity, and evolution ⋮ Forecasting errors and bounded rationality: An example ⋮ Computation of recursive functionals using minimal initial segments ⋮ Toward an abstract theory of data compression ⋮ On the complexity-relativized strong reducibilities ⋮ One-sided error probabilistic inductive inference and reliable frequency identification ⋮ On the inference of approximate programs ⋮ On average time hierarchies ⋮ A universal cellular automaton in quasi-linear time and its S-m-n form ⋮ Computability, complexity and economics ⋮ Uncontrollable computational growth in theoretical physics ⋮ Type 2 recursion theory
This page was built for publication: A Machine-Independent Theory of the Complexity of Recursive Functions
