A Machine-Independent Theory of the Complexity of Recursive Functions
From MaRDI portal
Publication:5537605
DOI10.1145/321386.321395zbMath0155.01503OpenAlexW2089442854WikidataQ55918695 ScholiaQ55918695MaRDI QIDQ5537605
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
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, 1998–1999 Winter Meeting of the Association for Symbolic Logic, Exact Pairs for Abstract Bounded Reducibilities, Learnability: Admissible, co-finite, and hypersimple languages, [https://portal.mardi4nfdi.de/wiki/Publication:5587565 Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung], Splittings of effectively speedable sets and effectively levelable sets, Parsimony hierarchies for inductive inference, Infinitary self-reference in learning theory, Ignoring data may be the only way to learn efficiently, A note on dense and nondense families of complexity classes, Prudence in vacillatory language identification, Machine learning of higher-order programs, Speed-Ups by changing the order in which sets are enumerated, Komplexität von Algorithmen mit Anwendung auf die Analysis, Measure independent Gödel speed‐ups and the relative difficulty of recognizing sets, Computational complexity of random access stored program machines, On restricted turing computability, Efficient unidimensional universal cellular automaton, Reflecting and self-confident inductive inference machines, Expressing computational complexity in constructive type theory, Machine induction without revolutionary paradigm shifts, Subclasses of \textsc{Ptime} interpreted by programming languages, ON SHAVRUKOV’S NON-ISOMORPHISM THEOREM FOR DIAGONALIZABLE ALGEBRAS, Computational speed-up by effective operators, On size vs. efficiency for programs admitting speed-ups, Recursion in Partial Type‐1 Objects With Well‐Behaved Oracles, Unnamed Item, Unnamed Item, The structure of intrinsic complexity of learning, Effective category and measure in abstract complexity theory, Explanatory and creative alternatives to the MDL principle, Robust learning with infinite additional information, Costs of general purpose learning, On the learnability of recursively enumerable languages from good examples, Synthesizing noise-tolerant language learners, Complexity properties of recursively enumerable sets and \(bsQ\)-completeness, Synthesizing learners tolerating computable noisy data, Robust learning is rich, Implicit measurements of dynamic complexity properties and splittings of speedable sets, Vacillatory and BC learning on noisy data, Control structures in hypothesis spaces: The influence on learning, Aspects of complexity of probabilistic learning under monotonicity constraints, Unnamed Item, Execution traces and programming-language semantics, The operator gap theorem in α-recursion theory, NON-SPLITTINGS OF SPEEDABLE SETS, Oracle Quantum Computing, On centain decompositions of Gödel numberings, Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees, Refutable language learning with a neighbor system., On learning of functions refutably., Intrinsic complexity of learning geometrical concepts from positive data, Splitting theorems for speed-up related to order of enumeration, Robust learning -- rich and poor, A Note on Blum Static Complexity Measures, Generality's price: Inescapable deficiencies in machine-learned programs, Characterization of realizable space complexities, Results on memory-limited U-shaped learning, Strategies for managing the structural and dynamic consequences of project complexity, Unnamed Item, A complexity measure for data flow models, Generalized kolmogorov complexity and other dual complexity measures, Two recursion theoretic characterizations of proof speed-ups, The intrinsic difficulty of recursive functions, Unnamed Item, Learning-theoretic perspectives of acceptable numberings, Computability-theoretic learning complexity, Learning from Positive Data and Negative Counterexamples: A Survey, Kolmogorov numberings and minimal identification, PROBLEMS WITH COMPLEXITY IN GOLD'S PARADIGM OF INDUCTION Part I: Dynamic Complexity, PROBLEMS WITH COMPLEXITY IN GOLD'S PARADIGM OF INDUCTION Part II: Static Complexity, Probabilistic language learning under monotonicity constraints, Unnamed Item, Intrinsic complexity of partial learning, Gold-Style Learning Theory, Classifying the computational complexity of problems, On subcreative sets and S-reducibility, A fresh look at research strategies in computational cognitive science: the case of enculturated mathematical problem solving, Learning in Friedberg Numberings, Computational complexity of formal translations, Learning how to separate., Honest bounds for complexity classes of recursive functions, Some natural conditions on incremental learning, Some independence results for control structures in complete numberings, Martin Davis and Hilbert’s Tenth Problem, Iterative learning from positive data and negative counterexamples, Learning multiple languages in groups, On the Amount of Nonconstructivity in Learning Recursive Functions, Robust separations in inductive inference, On complexity properties of recursively enumerable sets, Bi-immunity over different size alphabets, “Helping”: several formalizations, THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS, On degrees of unsolvability and complexity properties, Unconventional complexity measures for unconventional computers, Syntax and semantics of universal programming languages, Total complexity and the inference of best programs, Variations on U-shaped learning, COMPLEXITY OF DESCRIPTIONS OF SYSTEMS: A FOUNDATIONAL STUDY, Diophantine complexity, On computational complexity and honest polynomial degrees, General random sequences and learnable sequences, Quantitative aspects of speed-up and gap phenomena, INPUT/OUTPUT CODINGS AND TRANSITION FUNCTIONS IN EFFECTIVE SYSTEMS, On generalized computational complexity, On computational complexity in weakly admissible structures, Monoidal computer III: a coalgebraic view of computability and complexity (extended abstract), Some results on measure independent Gödel speed-ups, Multitape one-way nonwriting automata, Learning correction grammars, Computational complexity, speedable and levelable sets, Recursively enumerable complexity sequences and measure independence, Relationships between nondeterministic and deterministic tape complexities, Approximation and complexity of functions on the integers, Rice and Rice-Shapiro Theorems for transfinite correction grammars, The enumerability and invariance of complexity classes, On the structure of subrecursive degrees, Subrecursive programming languages. II. On program size, Intrinsic Complexity of Partial Learning, Complexity problems in real time languages, Abstract computational complexity and cycling computations, Classes of recursively enumerable sets and Q-reducibility, Priced Learning, Effective operators with no strong gaps, Degrees of computational complexity, A property of enumerable sets containing complexly deducible formulas, Tape-reversal bounded Turing machine computations, Learning languages and functions by erasing, The complexity of the word problems for commutative semigroups and polynomial ideals, Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems, Unnamed Item, Learning classes of approximations to non-recursive functions., Unnamed Item, The synthesis of language learners., Incremental concept learning for bounded data mining., Robust behaviorally correct learning., Inductive inference of approximations for recursive concepts, Relations between Gold-style learning and query learning, Busy beaver sets and the degrees of unsolvability, Intensional Kleene and Rice theorems for abstract program semantics, On the interplay between inductive inference of recursive functions, complexity theory and recursive numberings, Language learning from texts: Degrees of intrinsic complexity and their characterizations, Relativization of the Theory of Computational Complexity, Inductive inference with additional information., Variants of iterative learning, Learning languages with decidable hypotheses, Subrecursive equivalence relations and (non-)closure under lattice operations, Degree structures of conjunctive reducibility
