Computability of Recursive Functions

DOI10.1145/321160.321170zbMath0118.25401OpenAlexW2094542439WikidataQ56639060 ScholiaQ56639060MaRDI QIDQ5729305

Publication date: 1963

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321160.321170

zbMATH Keywords

mathematical logic

Related Items (93)

A direct method for simulating partial recursive functions by Diophantine equations ⋮ Expired data collection in shared dataspaces. ⋮ The undecidability of the Turing machine immortality problem ⋮ On the expressive power of movement and restriction in pure mobile ambients ⋮ When to Move to Transfer Nets ⋮ The ∀∃-theory of ℛ(≤,∨,∧) is undecidable ⋮ Register machine proof of the theorem on exponential diophantine representation of enumerable sets ⋮ Algorithmic properties of structures ⋮ Some general incompleteness results for partial correctness logics ⋮ Primitive iteration and unary functions ⋮ Rekursionszahlen und die Grzegorczyk-Hierarchie ⋮ Generation of invertible functions ⋮ Bounded variability of metric temporal logic ⋮ From Turing machines to computer viruses ⋮ A process algebraic view of Linda coordination primitives ⋮ The expressiveness of locally stratified programs ⋮ Conditional semi-Thue systems for presenting monoids ⋮ On transformations of programs ⋮ Program schemes, recursion schemes, and formal languages ⋮ Predecessor machines ⋮ Unconventional algorithms: complementarity of axiomatics and construction ⋮ Alternating automatic register machines ⋮ Computability by Normal Algorithms ⋮ Discrete Transfinite Computation ⋮ A New Hierarchy of Elementary Functions ⋮ Sleptsov nets are Turing-complete ⋮ On the expressiveness and decidability of higher-order process calculi ⋮ On the Minimum Computation Time of Functions ⋮ Sequence recursiveness without cylindrification and limited register machines ⋮ On the computational power of automata with time or space bounded by Ackermann's or superexponential functions ⋮ Some post canonical systems in one letter ⋮ A survey of state vectors ⋮ On a complexity-based way of constructivizing the recursive functions ⋮ Recursion in Partial Type‐1 Objects With Well‐Behaved Oracles ⋮ Theses for Computation and Recursion on Concrete and Abstract Structures ⋮ From Mathesis Universalis to Provability, Computability, and Constructivity ⋮ Undecidability of bisimilarity for Petri nets and some related problems ⋮ Programs, Grammars and Arguments: A Personal View of some Connections between Computation, Language and Logic ⋮ Process calculi as a tool for studying coordination, contracts and session types ⋮ On the power of several queues ⋮ Models of quantum computation and quantum programming languages ⋮ Confusion of memory ⋮ Minimality considerations for ordinal computers modeling constructibility ⋮ On the computational strength of pure ambient calculi ⋮ On the algorithmic complexity of static structures ⋮ Maze recognizing automata and nondeterministic tape complexity ⋮ The work of Kurt Gödel ⋮ From behaviorism to neobehaviorism ⋮ Instruction sequence processing operators ⋮ A characterization of the power of vector machines ⋮ Effective proper procedures and universal classes of program schemata ⋮ Dynamic interpolation search revisited ⋮ Computational expressiveness of genetic systems ⋮ Existential arithmetization of Diophantine equations ⋮ Some definitional suggestions for automata theory ⋮ Bemerkung zu Gurevich's Arbeit über das Entscheidungsproblem für Standardklassen ⋮ Towards a theory of semantics and compilers for programming languages ⋮ Execution traces and programming-language semantics ⋮ On the expressive power of process interruption and compensation ⋮ Über einen Automaten mit Pufferspeicherung ⋮ A Generalised Dynamical System, Infinite Time Register Machines, and $\Pi^1_1$ -CA0 ⋮ The lambda-gamma calculus: A language adequate for defining recursive functions ⋮ On a Model of Virtual Address Translation ⋮ Subrecursive programming languages. II. On program size ⋮ PROGRAMMED GRAMMARS WITH RULE QUEUES ⋮ Characterizations of semantic domains for randomized algorithms ⋮ On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines ⋮ Sequential and jumping machines and their relation to computers ⋮ Beitrag zur algebraischen Rekursionstheorie ⋮ (Tissue) P systems with cell polarity ⋮ On the expressive power of recursion, replication and iteration in process calculi ⋮ Deciding reachability problems in Turing-complete fragments of Mobile Ambients ⋮ Subrecursive program schemata I P II. I: Undecidable equivalence problems. II: Decidable equivalence problems ⋮ Comparative analysis of the expressiveness of shared dataspace coordination ⋮ Comparing three semantics for Linda-like languages ⋮ On the computational power of BlenX ⋮ Unnamed Item ⋮ Some undecidable theories with monadic predicates and without equality ⋮ ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS ⋮ Translatability of schemas over restricted interpretations ⋮ The Developments of the Concept of Machine Computability from 1936 to the 1960s ⋮ A procedural theory of eye movements in doing arithmetic ⋮ A simple proof of the undecidability of inhabitation in λP ⋮ Quantitative information in the tuple space coordination model ⋮ On the expressiveness of Linda coordination primitives. ⋮ A new order-theoretic characterisation of the polytime computable functions ⋮ Expressiveness Issues in Brane Calculi: A Survey ⋮ Closure functions and general iterates as reflectors ⋮ Analysis issues in Petri nets with inhibitor arcs ⋮ Counter machines ⋮ The $\exists\forall^2$ fragment of the first-order theory of atomic set constraints is $\Pi_1^0$-hard ⋮ Prefix classes of krom formulae with identity ⋮ Some thoughts on computational models: from massive human computing to abstract state machines, and beyond

This page was built for publication: Computability of Recursive Functions