An Unsolvable Problem of Elementary Number Theory

1936/04/01 by Alonzo Church · 65 citations
Mathematics · #History and Theory of Mathematics #Advanced Mathematical Theories

paper · doi:10.2307/2371045

Cited by

• The Mathematical Universe
• Physics, Topology, Logic and Computation: A Rosetta Stone
• Constraints on the universe as a numerical simulation
• Superintelligence Cannot be Contained: Lessons from Computability Theory
• On Computable Numbers, with an Application to the Entscheidungsproblem
• I.—COMPUTING MACHINERY AND INTELLIGENCE
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• The influence of domain interpretations on computational models
• Gems of Corrado Böhm
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• The World Is Bigger! A Computationally-Embedded Perspective on the Big World Hypothesis
• MSO logic of the real order with the set quantifiers ranging over the Borel sets
• The Tractable Cognition Thesis
• A Study of NP-Completeness and Undecidable Word Problems in Semigroups
• A clear case for scientific progress at the origin of analytic philosophy
• Random state comonads encode cellular automata evaluation
• Impossibility Results in AI: A Survey
• Towards Language Model Guided TLA+ Proof Automation
• On Learning to Think: Algorithmic Information Theory for Novel\n Combinations of Reinforcement Learning Controllers and Recurrent Neural World\n Models
• Deep learning in neural networks: An overview
• Testing the Machine Consciousness Hypothesis
• Quantum computing
• Medium Independence and the Failure of the Mechanistic Account of Computation
• The prehistory of generative grammar and Chomsky’s debt to Emil Post
• On the Realizability of Prime Conjectures in Heyting Arithmetic
• Actor Model of Computation: Scalable Robust Information Systems
• Practical Intractability: A Critique of the Hypercomputation Movement
• Formalizing common sense for scalable inconsistency-robust information integration using Direct Logic(TM) reasoning and the Actor Model
• Unified Foundations for Mathematics
• Notions of computability at higher types I
• One Big Net For Everything
• A case for weakening the Church-Turing Thesis
• Analog and Symbolic Computation through the Koopman Framework
• A Matter of Time: Towards a General Theory of Agency
• Storage Modification Machines
• Information processing pathway maps — A scalable framework for mapping cortical processing
• A Lambda Calculus for Quantum Computation
• 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
• Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions
• Roadblocks and Opportunities in Quantum Algorithms -- Insights from the National Quantum Initiative Joint Algorithms Workshop, May 20--22, 2024
• Beyond Turing: Memory-Amortized Inference as a Foundation for Cognitive Computation
• Certified Compilation based on Gödel Numbers
• Does resolving PvNP require a paradigm shift?
• Basic interactive algorithms: Preview
• The Gremlin graph traversal machine and language (invited talk)
• Alan Turing [wikipedia]
• Church–Turing thesis [wikipedia]
• PowerPlay: Training an Increasingly General Problem Solver by Continually Searching for the Simplest Still Unsolvable Problem. [europepmc]
• On recursion. [europepmc]
• Compositional Reasoning in Early Childhood. [europepmc]
• The computational stance in biology. [europepmc]
• Pathways to cellular supremacy in biocomputing. [europepmc]
• Agent Inaccessibility as a Fundamental Principle in Quantum Mechanics: Objective Unpredictability and Formal Uncomputability. [europepmc]
• Quantum Foundations of Classical Reversible Computing. [europepmc]
• Computational Creativity and Aesthetics with Algorithmic Information Theory. [europepmc]
• Naturalizing relevance realization: why agency and cognition are fundamentally not computational. [europepmc]
• Quantum Collapse and Computation in an Everett Multiverse. [europepmc]
• A Categorical Model of General Consciousness. [europepmc]
• Assembly theory and its relationship with computational complexity. [europepmc]
• Minding the gap between artificial and biological computing paradigms for biologically loyal AI. [europepmc]
• Achieving Operational Universality through a Turing Complete Chemputer. [europepmc]
• Putting reasons back into reasoning: how genuine reasoning is inference-based and why neuro-symbolic NLI could achieve it. [europepmc]
• Interplay Between Vertical and Horizontal Schemes of Computation: From Bayesian Inference to Quantum Logic via Gluing Boolean Algebras. [europepmc]