Classes of Predictably Computable Functions
From MaRDI portal
Publication:3293402
DOI10.2307/1993719zbMath0107.01001OpenAlexW4255332478MaRDI QIDQ3293402
Publication date: 1963
Full work available at URL: https://doi.org/10.2307/1993719
Related Items
Two-way automata with more than one storage medium ⋮ A universal two-way automaton ⋮ V-comprehensions and P space ⋮ Some observations on the connection between counting and recursion ⋮ A generalized Grzegorczyk hierarchy and low complexity classes ⋮ Algorithmically broad languages for polynomial time and space ⋮ An algebra and a logic for \(NC^ 1\) ⋮ Generalized finite automata theory with an application to a decision problem of second-order logic ⋮ Elementary functions and loop programs ⋮ Elementary realizability ⋮ Unnamed Item ⋮ Functions realizable by one-dimensional iterative systems ⋮ The intrinsic difficulty of recursive functions ⋮ Rudimentary relations and primitive recursion: A toolbox ⋮ Subrecursiveness: Machine-independent notions of computability in restricted time and storage ⋮ Nondeterministic stack register machines ⋮ Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\) ⋮ A method for constructing maximal subalgebras of algebras of general recursive functions ⋮ Predecessor machines ⋮ Computation models and function algebras ⋮ A New Hierarchy of Elementary Functions ⋮ On maximal subalgebras of the algebras of unary recursive functions ⋮ A maximal sequence of classes transformable by primitive recursion in a given class ⋮ Complexity of algorithms and computations ⋮ Jede mit Stackautomaten berechenbare Funktion ist elementar ⋮ On the computational power of automata with time or space bounded by Ackermann's or superexponential functions ⋮ On a complexity-based way of constructivizing the recursive functions ⋮ A machine description and the hierarchy of initial Grzegorczyk classes ⋮ Machine-independent description of certain machine complexity classes ⋮ Theories with self-application and computational complexity. ⋮ Arithmetizing uniform \(NC\) ⋮ Continuous-time computation with restricted integration capabilities ⋮ Combinatorial principles in elementary number theory ⋮ Unnamed Item ⋮ On the Computational Complexity of Algorithms ⋮ On Turing degrees of Walrasian models and a general impossibility result in the theory of decision-making ⋮ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msup><mml:mi mathvariant="script">E</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:math>-computability of e, π and Other Famous Constants ⋮ Functions Definable by Arithmetic Circuits ⋮ A new recursion-theoretic characterization of the polytime functions ⋮ Recursive function theory and numerical analysis ⋮ On primitive recursive wordfunctions ⋮ Die mit Nestedstackautomaten Berechenbaren Funktionen sind Elementar ⋮ Polynomial and abstract subrecursive classes ⋮ A sequence of complexly computable functions ⋮ On the density of honest subrecursive classes ⋮ On computational reducibility ⋮ Techniques for separating space complexity classes ⋮ Relating refined space complexity classes ⋮ A recursive and a grammatical characterization of the exponential-time languages ⋮ A recursion-theoretic characterisation of the positive polynomial-time functions ⋮ Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\) ⋮ A note on complexity measures for inductive classes in constructive type theory ⋮ Complexity Hierarchies beyond Elementary ⋮ Derivational complexity and context-sensitive Rewriting ⋮ On the computational complexity of imperative programming languages ⋮ On the generative power of transformational grammars ⋮ Tape-reversal bounded Turing machine computations ⋮ Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity ⋮ The complexity of computing exponents ⋮ Complexity classes and theories of finite models ⋮ Relativization of the Theory of Computational Complexity ⋮ Generalized finite automata theory with an application to a decision problem of second-order logic ⋮ On effectively computable realizations of choice functions
Cites Work
