scientific article

Publication date: 1980

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Gödel's incompleteness theorem undecidable problems Kleene's recursion theorems universal programs computability of partial recursive functions by register machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Undecidability and degrees of sets of sentences (03D35) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Turing machines and related notions (03D10) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (88)

LF+ in Coq for "fast and loose" reasoning ⋮ An analog characterization of the Grzegorczyk hierarchy ⋮ Structured algebraic specifications: A kernel language ⋮ ACKERMANN’S FUNCTION IN ITERATIVE FORM: A PROOF ASSISTANT EXPERIMENT ⋮ On theorems of Gödel and Kreisel: Completeness and Markov's principle ⋮ Non-computable rational expectations equilibria ⋮ Further results on Hilbert's tenth problem ⋮ Equational derivation vs. computation ⋮ A Short Introduction to Implicit Computational Complexity ⋮ The complexity of first-order and monadic second-order logic revisited ⋮ Confluent complement: an algorithm for the intersection of face ideals ⋮ Burgess’PVis Robinson’sQ ⋮ The data type variety of stack algebras ⋮ Toward a generalized computability theory ⋮ Robust program equilibrium ⋮ Small universal register machines ⋮ Bounded fixed-parameter tractability and reducibility ⋮ Parametric Church's thesis: synthetic computability without choice ⋮ Elementary functions and loop programs ⋮ Designing paradoxes: a revision-theoretic approach ⋮ Elementary realizability ⋮ A Medida de Informação de Shannon: Entropia ⋮ $$ITRM$$-Recognizability from Random Oracles ⋮ Randomness and universal machines ⋮ Computable functions in tabular databases ⋮ Generic Kleene fixed point theorem ⋮ Inequalities related to certain inverse trigonometric and inverse hyperbolic functions ⋮ Extended regular expressions: succinctness and decidability ⋮ Recursively enumerable subsets of $\mathbb{R}^{q}$ in two computing models Blum-Shub-Smale machine and Turing machine ⋮ Diagonalization in double frames ⋮ Specification and verification of concurrent systems by causality and realizability ⋮ Incompleteness of arithmetic from the viewpoint of Diophantine set theory ⋮ The never-ending recursion ⋮ An Enhanced Theory of Infinite Time Register Machines ⋮ On proofs of properties of semirecursive sets ⋮ All melodies are lost -- recognizability for weak and strong $\alpha $-register machines ⋮ Decidability of NP-complete problems ⋮ Mapcode characterization of partial recursive maps ⋮ The Gödelian Foundations of Self-Reference,the Liar and Incompleteness: Arms Racein Complex Strategic Innovation ⋮ Fixed point theorems and semantics: A folk tale ⋮ Diophantine sets of representations ⋮ Computability and Recursion ⋮ On the Semantics of Intensionality ⋮ Concerning existential definition of the class $NP$: Theoretical analysis of an alternative approach ⋮ The distribution of ITRM-recognizable reals ⋮ Register computations on ordinals ⋮ Training digraphs ⋮ The fixed point problem of a simple reversible language ⋮ A class of recursive permutations which is primitive recursive complete ⋮ I-categories as a framework for solving domain equations ⋮ Diagonalization, uniformity, and fixed-point theorems ⋮ Minimum-complexity pairing functions ⋮ Computable Queries for Object Oriented Databases ⋮ Ordinal Computability ⋮ A core model for choreographic programming ⋮ On the reification of semantic linearity ⋮ The natural algorithmic approach of mixed trigonometric-polynomial problems ⋮ A bound for orders in differential Nullstellensatz ⋮ Cooperation and computability in $n$-player games ⋮ Analog computation beyond the Turing limit ⋮ A characterization of computable analysis on unbounded domains using differential equations ⋮ On the interactive power of higher-order processes extended with parameterization ⋮ A Coinductive Animation of Turing Machines ⋮ The Church-Turing Thesis over Arbitrary Domains ⋮ Speed-up theorems in type-2 computations using oracle Turing machines ⋮ A class of reversible primitive recursive functions ⋮ Counting nondeterministic computations ⋮ A computable approach to measure and integration theory ⋮ A Generalised Dynamical System, Infinite Time Register Machines, and $\Pi^1_1$ -CA0 ⋮ Taming Koepke's zoo. II: Register machines ⋮ On the computational power of context-free PC grammar systems ⋮ Turing oracle machines, online computing, and three displacements in computability theory ⋮ Can a Program Reverse-Engineer Itself? ⋮ On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines ⋮ A game-semantic model of computation ⋮ The influence of domain interpretations on computational models ⋮ The Value-Passing Calculus ⋮ Communication, computability, and common interest games ⋮ Forecasting errors and bounded rationality: An example ⋮ Formalizing abstract computability: Turing categories in Coq ⋮ Rearrangements of the simple random walk ⋮ Aspects of Categorical Recursion Theory ⋮ On the Computable Theory of Bounded Analytic Functions ⋮ Lower bounds on $\beta (\alpha)$ ⋮ Intensional Kleene and Rice theorems for abstract program semantics ⋮ Using information systems to solve recursive domain equations ⋮ Communication errors in the $\pi$-calculus are undecidable ⋮ An exactification of the monoid of primitive recursive functions

This page was built for publication: