On the size of machines
From MaRDI portal
Publication:5549809
DOI10.1016/S0019-9958(67)90546-3zbMath0165.02102OpenAlexW1968738492WikidataQ56038300 ScholiaQ56038300MaRDI QIDQ5549809
No author found.
Publication date: 1967
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(67)90546-3
Related Items (43)
1998 European Summer Meeting of the Association for Symbolic Logic ⋮ On recursive bounds for the exceptional values in speed-up ⋮ A Note on Blum Static Complexity Measures ⋮ On the notion of infinite pseudorandom sequences ⋮ Separating the Classes of Recursively Enumerable Languages Based on Machine Size ⋮ Why it might pay to assume that languages are infinite ⋮ Program Size Complexity of Correction Grammars in the Ershov Hierarchy ⋮ Index sets in the arithmetical hierarchy ⋮ Splittings of effectively speedable sets and effectively levelable sets ⋮ Programmkomplexität von berechenbaren Funktionen ⋮ Infinitary self-reference in learning theory ⋮ On the power of recursive optimizers ⋮ Unnamed Item ⋮ On Goedel speed-up and succinctness of language representations ⋮ Speed-Ups by changing the order in which sets are enumerated ⋮ 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 ⋮ Computational speed-up by effective operators ⋮ Several results in program size complexity ⋮ Complexity of algorithms and computations ⋮ The independence of control structures in abstract programming systems ⋮ Concise description of finite languages ⋮ On size vs. efficiency for programs admitting speed-ups ⋮ Optimal enumerations and optimal gödel numberings ⋮ An incomplete set of shortest descriptions ⋮ Algorithmic complexity of recursive and inductive algorithms ⋮ Anomalous learning helps succinctness ⋮ Effective category and measure in abstract complexity theory ⋮ DESCRIPTIONAL COMPLEXITY IN ENCODED BLUM STATIC COMPLEXITY SPACES ⋮ Effective category and measure in abstract complexity theory ⋮ Syntax and semantics of universal programming languages ⋮ Total complexity and the inference of best programs ⋮ Comparison of identification criteria for machine inductive inference ⋮ Searching for shortest and least programs ⋮ Finite approximate approach to the study of the complexity of recursive predicates ⋮ Table approximations to recursive predicates ⋮ Teorie della complessità di calcolo ⋮ On Approximate Decidability of Minimal Programs ⋮ Effective choice functions and index sets ⋮ Subrecursive programming languages. II. On program size ⋮ Regular approximations of recursive predicates ⋮ Toward an abstract theory of data compression ⋮ Busy beaver sets and the degrees of unsolvability
This page was built for publication: On the size of machines
