On Computable Numbers, with an Application to the Entscheidungsproblem
From MaRDI portal
Publication:5765445
DOI10.1112/plms/s2-42.1.230zbMath0016.09701WikidataQ25864184 ScholiaQ25864184MaRDI QIDQ5765445
Publication date: 1936
Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1112/plms/s2-42.1.230
Related Items
The incompleteness theorems after 70 years, Fundamentals of quantum information theory, Graph automata: Natural expression of self-reproduction, Computability in linear algebra, Turing machines, transition systems, and interaction, From reaction-diffusion to physarum computing, Real numbers, continued fractions and complexity classes, Computing degrees of unsolvability, A procedural theory of eye movements in doing arithmetic, Représentations des nombres réels par développements en base entière et complexité. (Representations of real numbers by expansions on integer basis and complexity), Process algebras as support for sustainable systems of services, Three concepts of decidability for general subsets of uncountable spaces, Stability versus speed in a computable algebraic model, Divergence bounded computable real numbers, Computing equilibria: a computational complexity perspective, A hierarchy of Turing degrees of divergence bounded computable real numbers, Effectively open real functions, Computing Schrödinger propagators on type-2 Turing machines, Universality and semicomputability for nondeterministic programming languages over abstract algebras, Searching for computational creativity, What can quantum computers do?, Decidability in elementary analysis. II, The cellular computer DNA: Program or data, Minimum message length encoding and the comparison of macromolecules, Satisfiability of formulae with one \(\forall\) is decidable in exponential time, A uniform method for proving lower bounds on the computational complexity of logical theories, Borel complexity and computability of the Hahn-Banach theorem, Asymptotic behavior and halting probability of Turing machines, Towards molecular computers that operate in a biological environment, The domino problem of the hyperbolic plane is undecidable, A computable version of Banach's inverse mapping theorem, Gödel incompleteness and the Black hole information paradox, Classification of computably approximable real numbers, A constructive Borel-Cantelli lemma. Constructing orbits with required statistical properties, The road to two theorems of logic, Emergence as a computability-theoretic phenomenon, How to build a hypercomputer, Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics, Automated theorem proving methods, Model-theoretic and algorithmic questions in group theory, A note on Parikh maps, abstract languages, and decision problems, On effectively computable realizations of choice functions, Living with a new mathematical species, Introduction to the concept of recursiveness of fuzzy functions, A universal machine without change of state, Representations of the real numbers and of the open subsets of the set of real numbers, Incompleteness theorems for random reals, Lower bounds on degrees of game-theoretic structures, An infinite version of Arrow's theorem in the effective setting, Random problems, Physics of selective systems: Computation and biology, Computational complexity of real functions, On Turing degrees of Walrasian models and a general impossibility result in the theory of decision-making, Logic, ontology, mathematical practice, Finite automata with multiplication, ``V-tape, a virtual memory oriented data type, and its resource requirements, Anomalies of self-description, The miraculous universal distribution, A domain-theoretic approach to computability on the real line, Markov's constructive analysis; a participant's view, What is computation?, On Alan Turing's anticipation of connectionism, Searle's abstract argument against strong AI, Weights for total division orderings on strings, Somewhat finite approaches to infinite sentences., DNA computing: Arrival of biological mathematics, Using macrotransducers to specify partial continuous operators in metric spaces, Direct constructions of universal extended H systems., The generalized universal law of generalization., A blend of methods of recursion theory and topology., On the hierarchy and extension of monotonically computable real numbers., Computability on subsets of metric spaces., Toward a theory of intelligence, Super-tasks, accelerating Turing machines and uncomputability, The modal argument for hypercomputing minds, Frontier between decidability and undecidability: A survey, The Turing closure of an Archimedean field, On Turing's Turing Test and why the matter matters, Computationalism, A manifesto for the computational method, Real number computation through Gray code embedding., Physical quantum algorithms, A blend of methods of recursion theory and topology: a \(\Pi_1^0\) tree of shadow points, Complexity of the calculus of continued fraction representation of real numbers, Nonalgorithmic discrete procedures, Organization of computations on the atomic-molecular level, Consciousness: Computing the uncomputable, Definability, decidability, complexity, On the expressiveness of choice quantification, On the complexity of decision using destinies in \(H\)-bounded structures, Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations, Informational properties of neural nets performing algorithmic and logical tasks, An abstract data type for real numbers, Tiling problems and undecidability in the cluster variation method., Physical complexity of symbolic sequences, Building a model of a useful Turing machine, On the time complexity of partial real functions, Radical anti-realism, Wittgenstein and the length of proofs, Polynomial differential equations compute all real computable functions on computable compact intervals, More really is different, Algorithmic complexity of points in dynamical systems, The laterality problem for non-erasing Turing machines on $\lbrace 0,1\rbrace $ is completely solved, Characterizations of re languages starting from internal contextual languages∗, Prolegomenon to the relation between social theory and method*, Alonzo church:his life, his work and some of his miracles, Scanning the structure of ill‐known spaces: Part 1. Founding principles about mathematical constitution of space, Nonlinear phenomena in spaces of algorithms, Necessary and Sufficient Conditions for Quantum Computation, Economic Dynamics and Computation—Resurrecting the Icarus Tradition, ARITHMETIC IN THE FORM, The myth of the Turing machine: the failings of functionalism and related theses, Philosophy, engineering, biology, and history: a vindication of Turing's views about the distinction between the cognitive and physical sciences, Inductive learning and defeasible inference, Meanings of Model Checking, The challenge of computer mathematics, Computational unsolvability of domains of attraction of nonlinear systems, Unnamed Item, On the hierarchies of Δ20-real numbers, Non-computable Julia sets, Turing-Complete Subclasses of CHR, Monogenic normal systems are universal, The theory of languages, Semi-effective numberings and definitions of the computable numbers, The theory of languages, On restricted turing computability, Heuristic programming: A survey, Probabilistic Turing Machines and Computability, The Failure in Computable Analysis of a Classical Existence Theorem for Differential Equations, Church’s thesis and its relation to the concept of realizability in biology and physics, Computability by Probabilistic Turing Machines, Contributions to the reduction theory of the decision problem, Contributions to the reduction theory of the decision problem, Motivation for working in numerical analysis, Recursive Predicates and Quantifiers, The mathematical universe, Physical constraints on hypercomputation, On the complexity of algebraic numbers. II: Continued fractions, Biological function and the genetic code are interdependent, A hypercomputational alien, How much can analog and hybrid systems be proved (super-)Turing, The Church-Turing thesis: Still valid after all these years?, Church's thesis meets the \(N\)-body problem, Computational power of infinite quantum parallelism, Design of test inputs and their sequences in multi-function system testing, Finite state and finite stop quantum languages, The concept of effective method applied to computational problems of linear algebra, Sexually reproducing cellular automata, The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp, Elementarily computable functions over the real numbers and \(\mathbb R\)-sub-recursive functions, Turing-machines and the Entscheidungsproblem, Improved matrix pair undecidability results, Calculatrices digitales. Du déchiffrage de formules logico- mathématiques par la machine même dans la conception du programme, Varianten von Turingmaschinen, Remarks on the development of computability, On the definitions of some complexity classes of real numbers, How We Think of Computing Today, On Turing degrees of points in computable topology, Real Number Calculations and Theorem Proving, NMR Quantum Computing, Three Paths to Effectiveness, On computably locally compact Hausdorff spaces, Prediction of Recursive Real-Valued Functions from Finite Examples, All-Termination(T), Gödel's Introduction to Logic in 1939, Symbolism and enactivism: an experimental test of conflicting approaches to artificial intelligence, Computability, noncomputability and undecidability of maximal intervals of IVPs, An Undecidable Permutation of the Natural Numbers, Unnamed Item, On the complexity of computable real sequences, Global order from local sources, Perceptual-learning machines and the brain, Description of restricted automata by first-order formulae, Syntax and semantics of universal programming languages, Horn clause computability, Abstract Computability and Its Relation to the General Purpose Analog Computer (Some Connections Between Logic, Differential Equations and Analog Computers), Recursively enumerable sets and degrees, Execution traces and programming-language semantics
