On Computable Numbers, with an Application to the Entscheidungsproblem
1937/01/01 by A. M. Turing, Alan Turing · 1 voice · 155 citations
Computer Science · #Computability, Logic, AI Algorithms #Logic, Reasoning, and Knowledge
paper · doi:10.1112/plms/s2-42.1.230
Citations
Cited by
- I.—COMPUTING MACHINERY AND INTELLIGENCE
- What is computation?
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Von Menschen und Maschinen: Psychologiehistorische Reflexionen über Künstliche Intelligenz
- Design and Construction of a Brain-Like Computer: A New Class of Frequency-Fractal Computing Using Wireless Communication in a Supramolecular Organic, Inorganic System
- The influence of domain interpretations on computational models
- Machine, organism and language: a comparative epistemology of AI models
- The Halting Paradox
- Libertarian free will and quantum indeterminism
- Information theory, predictability, and the emergence of complex life
- Can we express every transfinite concept constructively?
- On the Church-Turing thesis
- Towards a Neural Model for Serial Order in Frontal Cortex: a Brain Theory from Memory Development to Higher-Level Cognition
- Is a deterministic universe logically consistent with a probabilistic Quantum Theory?
- Artificial Consciousness and Security
- The world of strategies with memory
- Computable structures on topological manifolds
- There is a Hyper-Greedoid lurking behind every Graphical Accessible Computational Search Problem solvable in Polynomial Time: P \not= NP
- On Polynomial Time Computable Numbers
- Machines, Logic and Quantum Physics
- Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine
- The Tractable Cognition Thesis
- Halfway Up To the Mathematical Infinity: On the Ontological and Epistemic Sustainability of Georg Cantor's Transfinite Design
- Interface agents: A review of the field
- Computable g- Frames
- Typologies of Computation and Computational Models
- Rare Speed-up in Automatic Theorem Proving Reveals Tradeoff Between Computational Time and Information Value
- Autism, epistemic injustice, and epistemic disablement: a relational account of epistemic agency
- A clear case for scientific progress at the origin of analytic philosophy
- Impossibility Results in AI: A Survey
- Quantum Computing: Lecture Notes
- On Learning to Think: Algorithmic Information Theory for Novel\n Combinations of Reinforcement Learning Controllers and Recurrent Neural World\n Models
- Kolmogorov Complexity and Information Content
- The risk of divergence
- Deep learning in neural networks: An overview
- Towards a Church-Turing-Thesis for Infinitary Computations
- Nature of codes and codes of nature: A short excursion into the past and the future of the biological codes
- The Machine as Data: A Computational View of Emergence and Definability
- A Short Introduction to Model Selection, Kolmogorov Complexity and Minimum Description Length (MDL)
- Mental programming of spatial sequences in working memory in the macaque frontal cortex
- The prehistory of generative grammar and Chomsky’s debt to Emil Post
- The Turing machine of a harmonic oscillator: from the code to the dynamic system
- Artificial Life Meets Computational Creativity?
- Haptic Assembly and Prototyping: An Expository Review
- Measuring Machine Companionship: Scale Development and Validation for AI Companions
- Ethical Artificial Intelligence
- Observations on the Halting Problem
- Deep Learning Works in Practice. But Does it Work in Theory?
- Formalizing common sense for scalable inconsistency-robust information integration using Direct Logic(TM) reasoning and the Actor Model
- A Framework for Algebraic Characterizations in Recursive Analysis
- Burning Geometric Graphs
- On P vs. NP, Geometric Complexity Theory, Explicit Proofs and the Complexity Barrier
- Risks of abuse of large language models, like <scp>ChatGPT</scp>, in scientific publishing: Authorship, predatory publishing, and paper mills
- Generating Asymptotically Non-Terminating Initial Values for Linear\n Programs
- Martin Davis: An Overview of his Work in Logic, Computer Science, and Philosophy
- Can Turing machines capture everything we can compute?
- On Programs and Genomes
- Engineering a cognition-based specification method
- Un énoncé et un texte inaugural
- Complex Networks from Simple Rewrite Systems
- Extended Models of Finite Automata
- Modeling the Mutation and Competition of Certain Nutrient-Producing Protocells by Means of Specific Turing Machines
- Lifting countable to uncountable mathematics
- On The Dynamical Nature Of Computation
- Simplification and integration in computing and cognition: the SP theory\n and the multiple alignment concept
- Veridical data science
- On the algorithmic descriptive complexity of attractors in topological dynamics
- Technoliberalism and the Network Social
- The complexity of small universal Turing machines: a survey
- Gaussian Attention Model and Its Application to Knowledge Base Embedding and Question Answering
- XV—On Consistency and Existence in Mathematics
- A nondeterministic Turing machine variant to compute functions
- Rebooting Neuromorphic Hardware Design -- A Complexity Engineering Approach
- One Big Net For Everything
- A thorough introduction to non-relativistic matrix mechanics in multi-qudit systems with a study on quantum entanglement and quantum quantifiers
- A case for weakening the Church-Turing Thesis
- Thoughts on Computational Creativity
- Long multiplication by instruction sequences with backward jump instructions
- A pumping lemma for non-cooperative self-assembly
- Computing as compression: the SP theory of intelligence
- The Relativity of Induction
- Neurocoder: Learning General-Purpose Computation Using Stored Neural Programs
- Speculative machines and us: more-than-human intuition and the algorithmic condition
- Most tensor problems are NP-hard
- Culture, Computation, Morality
- Implementing distributed λ-calculus interpreter
- Translational tilings: structured or wild?
- Computable analysis on the space of marked groups
- Open Quantum Systems and Quantum Algorithms
- An infinite version of arrow's theorem in the effective setting
- The Story of Telebrain: A multi-performer telematic platform for\n performatization
- Zeno machines and Running Turing machine for infinite time
- On the basis of brain: neural-network-inspired changes in general-purpose chips
- Between order and chaos
- Intractability and the use of heuristics in psychological explanations
- Complex Dynamical Systems
- Information processing pathway maps — A scalable framework for mapping cortical processing
- Epistemic Horizons: This Sentence is \(1)/(\√(2))(|True\⟩ +\n |False\⟩)
- What Is Working Memory and Mental Imagery? A Robot that Learns to Perform Mental Computations
- Universal Computation Is 'Almost Surely' Chaotic
- Epimenides, Gödel, Turing: an Eternal Gölden Tangle
- The Fundamental Theorem of Algebra made effective: an elementary real-algebraic proof via Sturm chains
- Is there a "loophole" in Goedel's interpretation of his formal reasoning and its consequences?
- Epistemic phase transitions in mathematical proofs
- On Arithmetic Modular Categories
- A Lambda Calculus for Quantum Computation
- On the proper treatment of connectionism
- On computable abstractions (a conceptual introduction)
- The reverse mathematics of Cousin's lemma
- On the uncountability of ℝ
- A synthesis and a practical approach to complex systems
- Logical Limitations to Machine Ethics with Consequences to Lethal\n Autonomous Weapons
- Confusion in the Church-Turing Thesis
- Introduction to Quantum Algorithms
- The Surprising Creativity of Digital Evolution: A Collection of Anecdotes from the Evolutionary Computation and Artificial Life Research Communities
- The formal roots of Platonism
- A spiking neural algorithm for the Network Flow problem
- Forecast and event control: On what is and what cannot be possible
- Rate Distortion and Denoising of Individual Data Using Kolmogorov\n complexity
- Turing Patterns with Turing Machines: Emergence and Low-level Structure\n Formation
- Local Hamiltonians in Quantum Computation
- Reactive Turing Machines
- Resolution of The Linear-Bounded Automata Question
- Some relations between quantum Turing machines and Turing machines
- Separation of PSPACE and EXP
- Avoiding Contradictions in the Paradoxes, the Halting Problem, and\n Diagonalization
- Algorithmically probable mutations reproduce aspects of evolution such\n as convergence rate, genetic memory, and modularity
- State-of-Charge Estimation of a Li-Ion Battery using Deep Forward Neural\n Networks
- Between Turing and Kleene
- Memory and attention in deep learning
- Using biased coins as oracles
- Does resolving PvNP require a paradigm shift?
- Expected Outcomes and Manipulations in Online Fair Division
- Autosolvability of halting problem instances for instruction sequences
- Wave Computing based on Dynamical Networks: Applications in Optimization Problems
- The Gremlin graph traversal machine and language (invited talk)
- Whether a quantum computation employs nonlocal resources is operationally undecidable
- On Empirical Entropy
- Universality in symbolic dynamics constrained by Medvedev degrees
- Design of the Ouroboros packet network
- Type-driven Neural Programming by Example
- Life, The Mind, and Everything
- Finite Computational Structures and Implementations
- Ramsey Theory on Infinite Structures and the Method of Strong Coding Trees
- "Defective" Logic: Using spatiotemporal patterns in coupled relaxation oscillator arrays for computation
- 'Almost Sure' Chaotic Properties of Machine Learning Methods
- A Model for Auto-Programming for General Purposes
- Cheap Non-standard Analysis and Computability
- Minimum Complexity Pursuit for Universal Compressed Sensing
- Alan Turing [wikipedia]
- Church–Turing thesis [wikipedia]
- Claude Shannon [wikipedia]
- Computable number [wikipedia]
- Definable real number [wikipedia]
- History of computing hardware [wikipedia]
Discussions