- Determination of the fifth Busy Beaver value
2025/09/15 by The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs +34 · 20 voices · 2 citations
Agricultural and Biological Sciences · Computer Science · Environmental Science · Mathematics · #Beaver #Botany and Plant Ecology Studies #Ecology and biodiversity studies #Turing #Turing machine #Value (mathematics) #cs.FL #cs.LO #math.LO
- Large Language Models Pass the Turing Test
2025/03/31 by Cameron R. Jones, Jones, Cameron R., Benjamin K. Bergen +1 · 73 voices · 35 citations
Computer Science · Medicine · Social Sciences · #AI in Service Interactions #Artificial Intelligence in Healthcare and Education #Baseline (sea) #Human language #Language and cultural evolution #Language model #Test (biology) #Turing #Turing machine #Turing test
- A Framework for Universality in Physics, Computer Science, and Beyond
2024/08/29 by Tomáš Gonda, Tobias Reinhart, Sebastian Stengele +1 · 2 citations
Computer Science · Mathematics · #Algorithm #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computer science #Mathematics #Physics #Quantum Computing Algorithms and Architecture #Theoretical computer science #Turing #Turing machine #Universal Turing machine #Universality (dynamical systems)
- Did Turing prove the undecidability of the halting problem?
2024/06/30 by Joel David Hamkins, Theodor Nenu, Hamkins, Joel David +1 · 5 voices · 1 citation
Computer Science · #Algorithm #Computability, Logic, AI Algorithms #Computation #Computer science #Description number #Halting problem #Programming language #Turing #Turing machine #Universal Turing machine
- Python Type Hints are Turing Complete
2022/08/31 by Ori Roth, Roth, Ori · 3 voices · 1 citation
Computer Science · #Computation #Computational Physics and Python Applications #Computer science #Java #Logic, programming, and type systems #Programming language #Python (programming language) #Software Engineering Research #Subtyping #Theoretical computer science #Turing #Turing machine #cs.PL
- Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine
2021/04/22 by Pontus Johnson, Johnson, Pontus · 2 voices · 1 citation
Computer Science · #Advanced Malware Detection Techniques #Code (set theory) #Computation #Computer science #Computer security #Description number #Distributed systems and fault tolerance #Machine code #Programming language #Security and Verification in Computing #Super-recursive algorithm #Theoretical computer science #Turing #Turing machine #Universal Turing machine #Vulnerability (computing)
- Complexity Blowup in Simulating Analog Linear Time-Invariant Systems on Digital Computers
2021/01/01 by Holger Boche, Volker Pohl · 3 voices · 1 citation
Computer Science · Mathematics · #Algorithm #Cellular Automata and Applications #Computability #Computability, Logic, AI Algorithms #Computer science #Description number #Differentiable function #Discrete mathematics #Invariant (physics) #Mathematical analysis #Mathematics #Probabilistic Turing machine #Pure mathematics #Quantum Computing Algorithms and Architecture #Super-recursive algorithm #Turing #Turing machine #Universal Turing machine #Upper and lower bounds
- The 2021 Conference on Artificial Life (full proceedings pdf)
2021/01/01 by Jitka Čejková, Barbora Hudcová, Tomáš Mikolov +3 · 1 voice
Computer Science · Engineering · #Algorithm #Artificial intelligence #Artificial life #Automata theory #Automaton #Cellular Automata and Applications #Cellular automaton #Computability, Logic, AI Algorithms #Computation #Computational complexity theory #Computer science #Elementary cellular automaton #Emulation #Graph #Mobile automaton #Modular Robots and Swarm Intelligence #Programming language #Set (abstract data type) #Theoretical computer science #Turing machine
- Embracing the Laws of Physics: Three Reversible Models of Computation
2018/11/08 by Jacques Carette, Roshan P. James, Carette, Jacques +3 · 1 voice · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Algebra over a field #Algorithm #Artificial intelligence #Coherence (philosophical gambling strategy) #Commutative property #Computability, Logic, AI Algorithms #Computation #Computer science #Conservation law #Distributed and Parallel Computing Systems #Mathematics #Negation #Perspective (graphical) #Programming language #Pure mathematics #Quantum Computing Algorithms and Architecture #Theoretical computer science #Turing machine #cs.LO #cs.PL #math.CT #msc:68Q05 #quant-ph
- Implementing Neural Turing Machines
2018/07/23 by Mark Collier, Collier, Mark, Joeran Beel +1 · 1 voice · 2 citations
Computer Science · Engineering · Mathematics · #Algorithm #Artificial intelligence #Artificial neural network #Auxiliary memory #Class (philosophy) #Computation #Computer hardware #Computer science #Domain Adaptation and Few-Shot Learning #Ferroelectric and Negative Capacitance Devices #Initialization #Machine Learning and Algorithms #Machine learning #Programming language #Scheme (mathematics) #Turing #Turing machine #cs.LG #stat.ML
- Mechanical Computing Systems Using Only Links and Rotary Joints
2018/01/10 by Ralph C. Merkle, Robert A. Freitas Jr., Robert A. Freitas +5 · 3 voices · 4 citations
Computer Science · Engineering · Physics and Astronomy · #Advanced Memory and Neural Computing #Algorithm #Artificial intelligence #Computation #Computational science #Computer engineering #Computer science #Control engineering #Engineering #Implementation #Mechanical and Optical Resonators #Mechanical system #Molecular Junctions and Nanostructures #Programming language #Simplicity #Turing machine #cs.AR #cs.ET
- Superintelligence Cannot be Contained: Lessons from Computability Theory
2016/07/04 by Manuel Alfonseca, Manuel Cebrián, Manuel Cebrian +6 · 2 voices · 7 citations
Computer Science · Decision Sciences · #Artificial intelligence #Computability #Computability, Logic, AI Algorithms #Computer science #Containment (computer programming) #Epistemology #Philosophy #Programming language #Scientific Computing and Data Management #State (computer science) #TRACE (psycholinguistics) #Theoretical computer science #Turing #Turing machine
- Braid is undecidable
2014/12/02 by Linus Hamilton, Hamilton, Linus · 2 voices
Computer Science · Mathematics · #Algorithm #Artificial Intelligence in Games #Artificial intelligence #Braid #Braid group #Braid theory #Cellular Automata and Applications #Combinatorics #Computability, Logic, AI Algorithms #Computation #Computer science #DTIME #Description number #Discrete mathematics #EXPTIME #Embedding #Mathematics #NSPACE #Super-recursive algorithm #Theoretical computer science #Time hierarchy theorem #Turing machine #Undecidable problem #Universal Turing machine #cs.CC
- Memcomputing NP -complete problems in polynomial time using polynomial resources and collective states
2014/11/18 by Fabio L. Traversa, Chiara Ramella, Fabrizio Bonani +1 · 1 voice · 7 citations
Computer Science · Engineering · Mathematics · #Advanced Memory and Neural Computing #Algorithm #Architecture #Computation #Computer science #Ferroelectric and Negative Capacitance Devices #Mathematics #NP #NSPACE #Non-deterministic Turing machine #Nondeterministic algorithm #Overhead (engineering) #Polynomial #Programming language #Quantum Computing Algorithms and Architecture #State (computer science) #Theoretical computer science #Time hierarchy theorem #Turing machine #Universal Turing machine #Von Neumann architecture #cs.ET #cs.NE
- Neural Turing Machines
2014/10/20 by Alex Graves, Graves, Alex, Greg Wayne +3 · 11 voices · 107 citations
Computer Science · Engineering · #Advanced Memory and Neural Computing #Algorithm #Artificial intelligence #Artificial neural network #Computation #Computer science #Content-addressable memory #Description number #Ferroelectric and Negative Capacitance Devices #NSPACE #Neural Networks and Applications #Non-deterministic Turing machine #Programming language #Super-recursive algorithm #Theoretical computer science #Turing #Turing machine #Turing machine examples #Universal Turing machine #Von Neumann architecture #cs.NE
- Toward the Minimal Universal Petri Net
2013/02/15 by Dmitry A. Zaitsev · 1 citation
Computer Science · Mathematics · #Petri Nets in System Modeling #Formal Methods in Verification #Distributed systems and fault tolerance #Petri net #Computer science #Encoding (memory) #Net (polyhedron) #Turing machine #Class (philosophy) #Time complexity #Stochastic Petri net #Algorithm #Exponential function #Theoretical computer science #Discrete mathematics #Sequence (biology) #Parallel computing #Mathematics #Artificial intelligence #Computation #Geometry
- Approximation complexity of Metric Dimension problem
2011/12/08 by Mathias Hauptmann, Richard Schmied, Claus Viehmann · 5 citations
Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Bounded function #Chordal graph #Combinatorics #DTIME #Degree (music) #Dimension (graph theory) #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Mathematical analysis #Mathematics #Metric (unit) #Metric dimension #Turing machine #Vertex (graph theory) #Vertex cover #graph theory and CDMA systems
- Graph Problems: Hard Problems
2009/03/26 by Steven S. Skiena, Steven Skiena · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Computational complexity theory #Computer science #Graph #Graph isomorphism #Heuristics #Line graph #Mathematical optimization #Mathematics #NP #Theoretical computer science #Time complexity #Turing machine #VLSI and FPGA Design Techniques #Vehicle Routing Optimization Methods
- P-completeness of Cellular Automaton Rule 110
2006/01/01 by Turlough Neary, Damien Woods · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Automaton #Cellular Automata and Applications #Cellular automaton #Completeness (order theory) #Computability, Logic, AI Algorithms #Computation #Computer science #Corollary #DNA and Biological Computing #Discrete mathematics #Exponential function #Mathematics #Overhead (engineering) #Programming language #Super-recursive algorithm #Theoretical computer science #Time complexity #Time hierarchy theorem #Turing #Turing machine #Universal Turing machine
- Experience, generations, and limits in machine learning
2004/01/02 by Mark Burgin, Allen Klinger · 1 citation
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Artificial intelligence #Automaton #Bounded function #Computability, Logic, AI Algorithms #Computer science #Construct (python library) #Machine Learning and Algorithms #Machine learning #Mathematics #Programming language #Super-recursive algorithm #Theoretical computer science #Turing #Turing machine #Universal Turing machine
- Infinite Time Turing Machines
2002/11/01 by Joel David Hamkins · 1 citation
Computer Science · Mathematics · #Advanced Topology and Set Theory #Algorithm #Computability #Computability, Logic, AI Algorithms #Computation #Computer science #Description number #Discrete mathematics #Expressive power #Mathematics #Programming language #Super-recursive algorithm #Theoretical computer science #Theory of computation #Time hierarchy theorem #Topological and Geometric Data Analysis #Transfinite number #Turing #Turing machine #Universal Turing machine
- Hypercomputation: computing more than the Turing machine
2002/09/25 by Toby Ord, Ord, Toby · 1 voice · 6 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Artificial intelligence #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #Computation #Computer science #Description number #Gödel #Gödel's incompleteness theorems #Mathematics #Model of computation #NSPACE #Non-deterministic Turing machine #Programming language #Quantum Computing Algorithms and Architecture #Randomness #Super-recursive algorithm #Theoretical computer science #Time hierarchy theorem #Turing #Turing machine #Turing machine examples #Universal Turing machine #cs.OH #math-ph #math.LO #math.MP #msc:03D10 #msc:68Q10 #msc:68Q30
- Building Infinite Machines
2001/12/01 by E. Brian Davies · 1 citation
Computer Science · Physics and Astronomy · Mathematics · #Computability, Logic, AI Algorithms #Quantum Mechanics and Applications #Quantum Computing Algorithms and Architecture #Intuitionism #Relevance (law) #Turing #Computer science #Epistemology #Turing machine #Universe #Mathematics #Mathematical economics #Philosophy #Programming language #Physics #Political science
- Minds, Machines and Turing
2000/10/01 by S. Harnad, Stevan Harnad · 1 citation
Computer Science · Mathematics · Neuroscience · Psychology · #Algorithm #Argument (complex analysis) #Computability, Logic, AI Algorithms #Computation #Computer science #Counterexample #Discrete mathematics #Embodied and Extended Cognition #Function (biology) #Hierarchy #Mathematical economics #Mathematics #Philosophy and Theoretical Science #Programming language #Turing #Turing machine
- Defining the Turing Jump
1999/01/01 by Richard A. Shore, Theodore A. Slaman · 1 citation
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #semigroups and automata theory #Cellular Automata and Applications #Turing machine #Mathematics #Time hierarchy theorem #Equivalence relation #Transitive relation #Computability theory #Discrete mathematics #Turing #Halting problem #Computable function #Probabilistic Turing machine #Transfinite number #Combinatorics #Universal Turing machine #Computer science #Computation #Algorithm
- How to make Zuse's Z3 a universal computer
1998/01/01 by Raúl Rojas · 1 citation
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Quantum Computing Algorithms and Architecture #Cellular Automata and Applications #Arithmetic function #Turing machine #Computer science #Subtraction #Division (mathematics) #Universal Turing machine #Arithmetic #Computation #Multiplication (music) #Theoretical computer science #Discrete mathematics #Algebra over a field #Mathematics #Programming language #Pure mathematics #Combinatorics
- Computability and Recursion
1996/09/01 by Robert I. Soare · 3 citations
Computer Science · Mathematics · #Algorithm #Cellular Automata and Applications #Computability #Computability theory #Computability, Logic, AI Algorithms #Computable function #Computation #Computer science #Decidability #Discrete mathematics #Function (biology) #Mathematics #Programming language #Recursion (computer science) #Theoretical computer science #Turing #Turing machine #semigroups and automata theory
- Software protection and simulation on oblivious RAMs
1996/05/01 by Oded Goldreich, Rafail Ostrovsky · 54 citations
Computer Science · Mathematics · #Algorithm #Complexity and Algorithms in Graphs #Computation #Computer science #Cryptography and Data Security #Heuristics #Logarithm #Mathematics #Model of computation #Operating system #Parallel computing #Privacy-Preserving Technologies in Data #Programming language #Slowdown #Software #Theoretical computer science #Turing #Turing machine
- Undecidable boundedness problems for datalog programs
1995/11/01 by Gerd G. Hillebrand, Gerd G Hillebrand, Paris C Kanellakis +5 · 1 citation
Computer Science · Mathematics · #Algorithm #Arity #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Datalog #Decidability #Discrete mathematics #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Mathematics #Partition (number theory) #Predicate (mathematical logic) #Programming language #Turing machine #Undecidable problem
- An Implementation of von Neumann's Self-Reproducing Machine
1995/01/01 by U. Pesavento · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Artificial intelligence #Automaton #Boundary value problem #Cellular Automata and Applications #Cellular automaton #Computer science #DNA and Biological Computing #Extension (predicate logic) #Finite-state machine #Mathematics #Modular Robots and Swarm Intelligence #Neumann boundary condition #Programming language #Theoretical computer science #Turing machine #Universal Turing machine #Von Neumann architecture
more