‘C (language)omputable’ directory
- See Also
- Links
- “Classical Billiards Can Compute”, Miranda & Ramos 2025
- “CSS Values and Units Module Level 5 § 8.3: Conditional Value Selection: the
if()Notation”, Atkins et al 2025 - “A Technical Introduction to Solomonoff Induction without K-Complexity”, Lang 2025
- “Researchers Discover the Optimal Way To Optimize: The Leading Approach to the Simplex Method, a Widely Used Technique for Balancing Complex Logistical Constraints, Can’t Get Any Better”, Nadis 2025
- “The QMA Singularity [GPT-5-Thinking Proves a Key Lemma]”, Aaronson 2025
- “Google’s Obfuscating VM-Based Anti-Bot System (BotGuard) Was Very Effective…”, Hearn 2025
- “NeuRaLaTeX: A Machine Learning Library Written in Pure LaTeX”, Gardner et al 2025
- “Topological Kleene Field Theories As a Model of Computation”, González-Prieto et al 2025
- “Quantum Speedup Found for Huge Class of Hard Problems: It’s Been Difficult to Find Important Questions That Quantum Computers Can Answer Faster Than Classical Machines, but a New Algorithm Appears to Do It for Some Critical Optimization Tasks”, Ornes 2025
- “‘Next-Level’ Chaos Traces the True Limit of Predictability”
- “Simulating Time With Square-Root Space”, Williams 2025
- “Regex Chess: A 2-Ply Minimax Chess Engine in 84,688 Regular Expressions”, Carlini 2025
- “Solving Sudoku With Tmux”
- “Tokenization Is NP-Complete”, Whittington et al 2024
- “Ask, and It Shall Be Given: Turing Completeness of Prompting”, Qiu et al 2024
- “ALTA: Compiler-Based Analysis of Transformers”, Shaw et al 2024
- “Autoregressive Large Language Models Are Computationally Universal”, Schuurmans et al 2024
- “Computer Scientists Combine Two ‘Beautiful’ Proof Methods [ZK + PCP]”
- “Hypercomputation without Bothering the Cactus People: Software Development for the DMT Headspace”, Flipper 2024
- “Tiling With 3 Polygons Is Undecidable”, Demaine & Langerman 2024
- “Fully Characterizing Lossy Catalytic Computation”, Folkertsma et al 2024
- “On the Complexity of Neural Computation in Superposition”, Adler & Shavit 2024
- “Lossy Catalytic Computation”, Gupta et al 2024
- “Quantum Convolutional Neural Networks Are (Effectively) Classically Simulable”, Bermejo et al 2024
- “Optimization by Decoded Quantum Interferometry”, Jordan et al 2024
- “Automata Extraction from Transformers”, Zhang et al 2024
- “A Programming Language Embedded in Magic: The Gathering”, Yin & Churchill 2024
- “The Illusion of State in State-Space Models”, Merrill et al 2024
- “Language Generation in the Limit”, Kleinberg & Mullainathan 2024
- “Chain-Of-Thought Empowers Transformers to Solve Inherently Serial Problems”, Li et al 2024
- “Why Are Sensitive Functions Hard for Transformers?”, Hahn & Rofin 2024
- “FBSH: Font With Built-In Syntax Highlighting for Hand-Coded Websites”, Lotvonen 2024
- “Linux/4004: Slowly Booting Full Linux on the Intel 4004 CPU for Fun, Art, and Absolutely No Profit”, Grinberg 2024
- “Can a Transformer Represent a Kalman Filter?”, Goel & Bartlett 2023
- “Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly the Star-Free Languages”, Angluin et al 2023
- “The Expressive Power of Transformers With Chain-Of-Thought”, Merrill & Sabharwal 2023
- “How to Build a Computer Using Origami”, Green 2023
- “Flat Origami Is Turing Complete”, Hull & Zakharevich 2023
- “Learning Transformer Programs”, Friedman et al 2023
- “Universal Mechanical Polycomputation in Granular Matter”, Parsa et al 2023
- “Towards Revealing the Mystery behind Chain-Of-Thought: A Theoretical Perspective”, Feng et al 2023
- “Neural Oscillators Are Universal”, Lanthaler et al 2023
- “Looped Transformers As Programmable Computers”, Giannou et al 2023
- “Tighter Bounds on the Expressivity of Transformer Encoders”, Chiang et al 2023
- “Memory Augmented Large Language Models Are Computationally Universal”, Schuurmans 2023
- “Control of Cell Proliferation by Memories of Mitosis”, Meitinger et al 2022
- “Characterizing Intrinsic Compositionality in Transformers With Tree Projections”, Murty et al 2022
- “Transformers Learn Shortcuts to Automata”, Liu et al 2022
- “Transformers Implement First-Order Logic With Majority Quantifiers”, Merrill & Sabharwal 2022
- “Python Type Hints Are Turing Complete”, Roth 2022
- “What Can Transformers Learn In-Context? A Case Study of Simple Function Classes”, Garg et al 2022
- “Perceptein: A Synthetic Protein-Level Neural Network in Mammalian Cells”, Chen et al 2022
- “Neural Networks and the Chomsky Hierarchy”, Delétang et al 2022
- “Log-Precision Transformers Are Constant-Depth Uniform Threshold Circuits”, Merrill & Sabharwal 2022
- “Verifiable Quantum Advantage without Structure”, Yamakawa & Zhandry 2022
- “An RNA-Based Theory of Natural Universal Computation”, Akhlaghpour 2022
- “Overcoming a Theoretical Limitation of Self-Attention”, Chiang & Cholak 2022
- “A Deep Dive into an NSO Zero-Click IMessage Exploit: Remote Code Execution”, Beer & Groß 2021
- “Quantum Advantage in Learning from Experiments”, Huang et al 2021
- “Minimum Description Length Recurrent Neural Networks”, Lan et al 2021
- “JPEG XL Would Be Turing-Complete”, Bohdan 2021
- “RASP: Thinking Like Transformers”, Weiss et al 2021
- “Turing Completeness and Sid Meier’s Civilization”, Wynter 2021
- “Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine”, Johnson 2021
- “Sensitivity As a Complexity Measure for Sequence Classification Tasks”, Hahn et al 2021
- “Gene Regulatory Networks Exhibit Several Kinds of Memory: Quantification of Memory in Biological and Random Transcriptional Networks”, Biswas et al 2021
- “Constructing Turing Complete Euler Flows in Dimension 3”, Cardona et al 2020
- “How the Slowest Computer Programs Illuminate Math’s Fundamental Limits: The Goal of the ‘Busy Beaver’ Game Is to Find the Longest-Running Computer Program. Its Pursuit Has Surprising Connections to Some of the Most Profound Questions and Concepts in Mathematics”, Pavlus 2020
- “"Less Than One"-Shot Learning: Learning n Classes From M < N Samples”, Sucholutsky & Schonlau 2020
- “Catalytic Approaches to the Tree Evaluation Problem”, Cook & Mertz 2020
- “Remembering John Conway’s FRACTRAN, a Ridiculous, yet Surprisingly Deep Language”, Braithwaite 2020
- “Magic: the Gathering Is As Hard As Arithmetic”, Biderman 2020
- “Recursed Is Not Recursive: A Jarring Result”, Demaine et al 2020
- “Are Transformers Universal Approximators of Sequence-To-Sequence Functions?”, Yun et al 2019
- “The Busy Beaver Frontier”, Aaronson 2019
- “Universal Approximation With Deep Narrow Networks”, Kidger & Lyons 2019
- “Magic: The Gathering Is Turing Complete”, Churchill et al 2019
- “On the Turing Completeness of Modern Neural Network Architectures”, Pérez et al 2019
- “Mismorphism: The Heart of the Weird Machine”, Anantharaman et al 2019
- “Deciphering the Molecular Mechanism Underpinning Phage Arbitrium Communication Systems”, Sol et al 2019
- “Mechanical Computing: The Computational Complexity of Physical Devices”, Reif 2018
- “Adversarial Reprogramming of Neural Networks”, Elsayed et al 2018
- “Mechanical Computing System Using Only One Physical Object-qb Cube”, Vučinović 2018
- “Go Experience Report: Generics in Kubernetes”, Schlesinger 2017
- “Weird Machines, Exploitability, and Provable Unexploitability”, Dullien 2017
- “On the Glitch Phenomenon”, Lamport & Palais 2017
- “Communication between Viruses Guides Lysis-Lysogeny Decisions”, Erez et al 2017
- “Why Does Deep and Cheap Learning Work so Well?”, Lin et al 2016
- “Java Generics Are Turing Complete”, Grigore 2016
- “A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory”, Yedidia & Aaronson 2016
- “Open Games: Compositional Game Theory”, Ghani et al 2016
- Advances in Physarum Machines: Sensing and Computing With Slime Mould, Adamatzky 2016
- “On Having No Head: Cognition throughout Biological Systems”, Baluška & Levin 2016
- “We Need Less Powerful Languages [Langsec]”, Plant 2015
- “Undecidability of the Spectral Gap”, Cubitt et al 2015
- “What Are Weird Machines?”, Bratus 2015
- “Braid Is Undecidable”, Hamilton 2014
- “Computing With a Full Memory: Catalytic Space”, Buhrman et al 2014
- “Implementing a Web Server in a Single
printf()Call” - “Teaching Mario to Play Pong and Snake Through Innumerable Exploits”
- “Converting Untrusted PDFs into Trusted Ones: The Qubes Way”
- “Mathematics in the Age of the Turing Machine”, Hales 2013
- “On Unsettleable Arithmetical Problems”, Conway 2013
- “The Page-Fault Weird Machine: Lessons in Instruction-Less Computation”, Bangert 2013
- “Using Routers to Build Logic Circuits: How Powerful Is BGP?”, Chiesa 2013
- “Is the Network Turing-Complete? EPFL Technical Report 187131”, Peresini & Kostic 2013
- “Turning Oscillations into Opportunities: Lessons from a Bacterial Decision Gate”, Schultz et al 2013
- “The Configuration Complexity Clock”, Hadlow 2012
- “Buridan’s Principle”, Lamport 2012
- “Robust Soldier Crab Ball Gate”, Gunji et al 2012
- “Buridan’s Principle [Publication Problems Delaying 1984 → 2012]”, Lamport 2012
- “Exploitation and State Machines: Programming the ‘Weird Machine’ Revisited”, Flake 2011
- “Quantum Computation With Devices Whose Contents Are Never Read”, Yakaryilmaz et al 2010
- “Ant-Based Computing”, Michael 2009
- “Physics, Topology, Logic and Computation: A Rosetta Stone”, Baez & Stay 2009
- “High Performance SQL With PostgreSQL 8.4: Lists and Recursion and Trees, Oh My!”, Fetter 2009
- “Deciding Fate in Adverse Times: Sporulation and Competence in Bacillus Subtilis”, Schultz et al 2009
- “Small Universal Turing Machines”, Neary 2008
- “Closed Timelike Curves Make Quantum and Classical Computing Equivalent”, Aaronson & Watrous 2008
- “Omega Monad: Enumerating a Context-Free Language”, Palmer 2008
- “Perl Cannot Be Parsed: A Formal Proof”, Kegler 2008
- “Algorithmic Self-Assembly of DNA”, Winfree 2008
- “On Universal Prediction and Bayesian Confirmation”, Hutter 2007
- “Infinite Sets That Admit Fast Exhaustive Search”, Escardo 2007
- “Can Newtonian Systems, Bounded in Space, Time, Mass and Energy Compute All Functions?”, Beggs & Tucker 2007
- “Infinite Versions of Minesweeper Are Turing Complete”, Kate 2007
- “On the Computational Power of Threshold Circuits With Sparse Activity”, Uchizawa et al 2006
- “No Quantum Advantage for Nonlocal Computation”, Linden et al 2006
- “Static Typing for a Faulty Lambda Calculus”, Walker et al 2006
- “Is There an Elegant Universal Theory of Prediction?”, Legg 2006
- Good and Real: Demystifying Paradoxes from Physics to Ethics, Drescher 2006
- “A Box, Darkly: Obfuscation, Weird Languages, and Code Esthetics”, Mateas & Montfort 2005
- “The Halting Problem Is Decidable on a Set of Asymptotic Probability One”, Hamkins & Miasnikov 2005
- “A Theory of Quantum Gravity Based on Quantum Computation”, Lloyd 2005
- “A Simple Proof for the Turing-Completeness of XSLT and XQuery”, Kepser 2004
- “Gödel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements”, Schmidhuber 2003
- “Philosophical Problems in Logic § Ultrafinitism”, Friedman 2002 (page 4)
- “Analytic and Algorithmic Solution of Random Satisfiability Problems”, Mezard et al 2002
- “The Fastest and Shortest Algorithm for All Well-Defined Problems”, Hutter 2002
- “Forbidden Information”, Levin 2002
- “Sendmail As a Turing Machine”, Kiselyov 2000
- “Counterfactual Computation”, Mitchison & Jozsa 1999
- “P/NP, and the Quantum Field Computer”, Freedman 1998
- “Limitations of Noisy Reversible Computation”, Aharonov et al 1996
- “A Personal View of Average-Case Complexity”, Impagliazzo 1995
- “Threshold Circuits of Bounded Depth”, Hajnal et al 1993
- “The Complexity of N-Body Simulation”, Reif & Tate 1993
- “Average Case Complexity under the Universal Distribution Equals Worst-Case Complexity”, Li & Vitányi 1992
- “Time Travel and Computing”, Moravec 1991
- “Unpredictability and Undecidability in Dynamical Systems”, Moore 1990
- “A Differentiation Primitive for Extended Λ–calculus”, Flaherty 1988
- “FRACTRAN: A Simple Universal Programming Language for Arithmetic”, Conway 1987
- “Conservative Logic”, Fredkin & Toffoli 1982
- “Bi-Continuous Extensions of Invertible Combinatorial Functions”, Toffoli 1981
- “Unpredictable Iterations”, Conway 1972
- “О Невозможности Элиминации Полного Перебора При Вычислении Функций Относительно Их Графиков”, Дехтярь 1969
- “FLODAC—A Pure Fluid Digital Computer”, Gluskin et al 1964
- “Tag Systems and Lag Systems”, Wang 1963
- “On Non-Computable Functions”, Rado 1962
- “Representation of Events in Nerve Nets and Finite Automata”, Kleene 1951
- “‘Computational Complexity of Air Travel Planning’, De Marcken 2003 [ITA Software]”
- “Universal Search § OOPS and Other Incremental Variations”
- “Computing With Time: Microarchitectural Weird Machines”
- “How Exploits Impact Computer Science Theory”
- “The Dhall Configuration Language”
- “ByteByteJump”, Wiki 2026
- “Linear Bounded Automaton”
- “OISC”
- “HexHive/printbf: Brainfuck Interpreter inside Printf”
- “InkboxSoftware/excelCPU: 16-Bit CPU for Excel, and Related Files”
- “A WebAssembly Runtime Implemented in TypeScript Types [Which Runs Doom]”
- “
roguetype: The First Ever Rogue-Like Written in the OCaml Type System”, Octachron 2026 - “Sudoku Solving in Python Packaging”
- “MalbolgeLisp Is a LISP Interpreter Written in Malbolge. It’s (As of 2020 and 2021), the Most Advanced, Usable Malbolge Program Ever Created. It Supports Everything Lisps Generally Tend to Support (Like
cond,let,lambda, Etc…).” - “How I Did Relay Quine”
- “Using SQL’s Turing Completeness to Build Tetris”
- “C99 Doesn’t Need Function Bodies, Or, ‘VLAs Are Turing Complete’”
- “Another New Record in Self-Cleaning Turing Machines”
- “
find+mkdirIs Turing Complete (Retracted)”, Kako 2026 - “Predicting the Tide With an Analog Computer Made from Lego”
- “PEP 611: The One Million Limit”
- “Choon Programming Language”
- “Rosser’s Theorem via Turing Machines”
- “Busy Beaver(5) Is Now Proven to Be 47,176,870”
- “Rust’s Type System Is Turing-Complete”, Leffler 2026
- “OpenTTD Logic”
- “Weird Machines HQ”
- “The Infinity Machine”
- Fontemon
- “A Computational No-Coincidence Principle”
- “A Brief History of Liquid Computers”
- “Rule 110 Train Turing Machine Explained”
- “I Built ChatGPT With Minecraft Redstone!”
- “Turing Machine Busy Beaver 5 Champ–47,176,870 Steps–Perfect Pixel Binning”
- “On The Turing Completeness of PowerPoint”
- Sort By Magic
- Wikipedia (47)
- Miscellaneous
- Bibliography
See Also
Links
“Classical Billiards Can Compute”, Miranda & Ramos 2025
“CSS Values and Units Module Level 5 § 8.3: Conditional Value Selection: the if() Notation”, Atkins et al 2025
CSS Values and Units Module Level 5 § 8.3: Conditional Value Selection: the if() notation
“A Technical Introduction to Solomonoff Induction without K-Complexity”, Lang 2025
A Technical Introduction to Solomonoff Induction without K-Complexity
“Researchers Discover the Optimal Way To Optimize: The Leading Approach to the Simplex Method, a Widely Used Technique for Balancing Complex Logistical Constraints, Can’t Get Any Better”, Nadis 2025
“The QMA Singularity [GPT-5-Thinking Proves a Key Lemma]”, Aaronson 2025
“Google’s Obfuscating VM-Based Anti-Bot System (BotGuard) Was Very Effective…”, Hearn 2025
Google’s obfuscating VM-based anti-bot system (BotGuard) was very effective…
“NeuRaLaTeX: A Machine Learning Library Written in Pure LaTeX”, Gardner et al 2025
NeuRaLaTeX: A machine learning library written in pure LaTeX
“Topological Kleene Field Theories As a Model of Computation”, González-Prieto et al 2025
“Quantum Speedup Found for Huge Class of Hard Problems: It’s Been Difficult to Find Important Questions That Quantum Computers Can Answer Faster Than Classical Machines, but a New Algorithm Appears to Do It for Some Critical Optimization Tasks”, Ornes 2025
“‘Next-Level’ Chaos Traces the True Limit of Predictability”
“Simulating Time With Square-Root Space”, Williams 2025
“Regex Chess: A 2-Ply Minimax Chess Engine in 84,688 Regular Expressions”, Carlini 2025
Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions
“Solving Sudoku With Tmux”
“Tokenization Is NP-Complete”, Whittington et al 2024
“Ask, and It Shall Be Given: Turing Completeness of Prompting”, Qiu et al 2024
Ask, and it shall be given: Turing completeness of prompting
“ALTA: Compiler-Based Analysis of Transformers”, Shaw et al 2024
“Autoregressive Large Language Models Are Computationally Universal”, Schuurmans et al 2024
Autoregressive Large Language Models are Computationally Universal
“Computer Scientists Combine Two ‘Beautiful’ Proof Methods [ZK + PCP]”
Computer Scientists Combine Two ‘Beautiful’ Proof Methods [ZK + PCP]
“Hypercomputation without Bothering the Cactus People: Software Development for the DMT Headspace”, Flipper 2024
Hypercomputation without bothering the cactus people: Software development for the DMT headspace
“Tiling With 3 Polygons Is Undecidable”, Demaine & Langerman 2024
“Fully Characterizing Lossy Catalytic Computation”, Folkertsma et al 2024
“On the Complexity of Neural Computation in Superposition”, Adler & Shavit 2024
“Lossy Catalytic Computation”, Gupta et al 2024
“Quantum Convolutional Neural Networks Are (Effectively) Classically Simulable”, Bermejo et al 2024
Quantum Convolutional Neural Networks are (Effectively) Classically Simulable
“Optimization by Decoded Quantum Interferometry”, Jordan et al 2024
“Automata Extraction from Transformers”, Zhang et al 2024
“A Programming Language Embedded in Magic: The Gathering”, Yin & Churchill 2024
“The Illusion of State in State-Space Models”, Merrill et al 2024
“Language Generation in the Limit”, Kleinberg & Mullainathan 2024
“Chain-Of-Thought Empowers Transformers to Solve Inherently Serial Problems”, Li et al 2024
Chain-of-Thought Empowers Transformers to Solve Inherently Serial Problems
“Why Are Sensitive Functions Hard for Transformers?”, Hahn & Rofin 2024
“FBSH: Font With Built-In Syntax Highlighting for Hand-Coded Websites”, Lotvonen 2024
FBSH: Font with Built-In Syntax Highlighting for Hand-Coded Websites
“Linux/4004: Slowly Booting Full Linux on the Intel 4004 CPU for Fun, Art, and Absolutely No Profit”, Grinberg 2024
Linux/4004: Slowly booting full Linux on the Intel 4004 CPU for fun, art, and absolutely no profit
“Can a Transformer Represent a Kalman Filter?”, Goel & Bartlett 2023
“Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly the Star-Free Languages”, Angluin et al 2023
Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly the Star-Free Languages
“The Expressive Power of Transformers With Chain-Of-Thought”, Merrill & Sabharwal 2023
“How to Build a Computer Using Origami”, Green 2023
“Flat Origami Is Turing Complete”, Hull & Zakharevich 2023
“Learning Transformer Programs”, Friedman et al 2023
“Universal Mechanical Polycomputation in Granular Matter”, Parsa et al 2023
“Towards Revealing the Mystery behind Chain-Of-Thought: A Theoretical Perspective”, Feng et al 2023
Towards Revealing the Mystery behind Chain-of-Thought: A Theoretical Perspective
“Neural Oscillators Are Universal”, Lanthaler et al 2023
“Looped Transformers As Programmable Computers”, Giannou et al 2023
“Tighter Bounds on the Expressivity of Transformer Encoders”, Chiang et al 2023
“Memory Augmented Large Language Models Are Computationally Universal”, Schuurmans 2023
Memory Augmented Large Language Models are Computationally Universal
“Control of Cell Proliferation by Memories of Mitosis”, Meitinger et al 2022
“Characterizing Intrinsic Compositionality in Transformers With Tree Projections”, Murty et al 2022
Characterizing Intrinsic Compositionality in Transformers with Tree Projections
“Transformers Learn Shortcuts to Automata”, Liu et al 2022
“Transformers Implement First-Order Logic With Majority Quantifiers”, Merrill & Sabharwal 2022
Transformers Implement First-Order Logic with Majority Quantifiers
“Python Type Hints Are Turing Complete”, Roth 2022
“What Can Transformers Learn In-Context? A Case Study of Simple Function Classes”, Garg et al 2022
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes
“Perceptein: A Synthetic Protein-Level Neural Network in Mammalian Cells”, Chen et al 2022
Perceptein: A synthetic protein-level neural network in mammalian cells
“Neural Networks and the Chomsky Hierarchy”, Delétang et al 2022
“Log-Precision Transformers Are Constant-Depth Uniform Threshold Circuits”, Merrill & Sabharwal 2022
Log-Precision Transformers are Constant-Depth Uniform Threshold Circuits
“Verifiable Quantum Advantage without Structure”, Yamakawa & Zhandry 2022
“An RNA-Based Theory of Natural Universal Computation”, Akhlaghpour 2022
“Overcoming a Theoretical Limitation of Self-Attention”, Chiang & Cholak 2022
“A Deep Dive into an NSO Zero-Click IMessage Exploit: Remote Code Execution”, Beer & Groß 2021
A deep dive into an NSO zero-click iMessage exploit: Remote Code Execution
“Quantum Advantage in Learning from Experiments”, Huang et al 2021
“Minimum Description Length Recurrent Neural Networks”, Lan et al 2021
“JPEG XL Would Be Turing-Complete”, Bohdan 2021
“RASP: Thinking Like Transformers”, Weiss et al 2021
“Turing Completeness and Sid Meier’s Civilization”, Wynter 2021
“Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine”, Johnson 2021
“Sensitivity As a Complexity Measure for Sequence Classification Tasks”, Hahn et al 2021
Sensitivity as a Complexity Measure for Sequence Classification Tasks
“Gene Regulatory Networks Exhibit Several Kinds of Memory: Quantification of Memory in Biological and Random Transcriptional Networks”, Biswas et al 2021
“Constructing Turing Complete Euler Flows in Dimension 3”, Cardona et al 2020
“How the Slowest Computer Programs Illuminate Math’s Fundamental Limits: The Goal of the ‘Busy Beaver’ Game Is to Find the Longest-Running Computer Program. Its Pursuit Has Surprising Connections to Some of the Most Profound Questions and Concepts in Mathematics”, Pavlus 2020
“"Less Than One"-Shot Learning: Learning n Classes From M < N Samples”, Sucholutsky & Schonlau 2020
"Less Than One"-Shot Learning: Learning n Classes From M < N Samples
“Catalytic Approaches to the Tree Evaluation Problem”, Cook & Mertz 2020
Catalytic Approaches to the Tree Evaluation Problem :
View PDF:
“Remembering John Conway’s FRACTRAN, a Ridiculous, yet Surprisingly Deep Language”, Braithwaite 2020
Remembering John Conway’s FRACTRAN, a ridiculous, yet surprisingly deep language
“Magic: the Gathering Is As Hard As Arithmetic”, Biderman 2020
“Recursed Is Not Recursive: A Jarring Result”, Demaine et al 2020
“Are Transformers Universal Approximators of Sequence-To-Sequence Functions?”, Yun et al 2019
Are Transformers universal approximators of sequence-to-sequence functions?
“The Busy Beaver Frontier”, Aaronson 2019
“Universal Approximation With Deep Narrow Networks”, Kidger & Lyons 2019
“Magic: The Gathering Is Turing Complete”, Churchill et al 2019
“On the Turing Completeness of Modern Neural Network Architectures”, Pérez et al 2019
On the Turing Completeness of Modern Neural Network Architectures
“Mismorphism: The Heart of the Weird Machine”, Anantharaman et al 2019
“Deciphering the Molecular Mechanism Underpinning Phage Arbitrium Communication Systems”, Sol et al 2019
Deciphering the Molecular Mechanism Underpinning Phage Arbitrium Communication Systems
“Mechanical Computing: The Computational Complexity of Physical Devices”, Reif 2018
Mechanical Computing: The Computational Complexity of Physical Devices :
View PDF:
“Adversarial Reprogramming of Neural Networks”, Elsayed et al 2018
“Mechanical Computing System Using Only One Physical Object-qb Cube”, Vučinović 2018
Mechanical Computing System Using Only One Physical Object-qb cube
“Go Experience Report: Generics in Kubernetes”, Schlesinger 2017
“Weird Machines, Exploitability, and Provable Unexploitability”, Dullien 2017
Weird machines, exploitability, and provable unexploitability
“On the Glitch Phenomenon”, Lamport & Palais 2017
“Communication between Viruses Guides Lysis-Lysogeny Decisions”, Erez et al 2017
Communication between viruses guides lysis-lysogeny decisions
“Why Does Deep and Cheap Learning Work so Well?”, Lin et al 2016
“Java Generics Are Turing Complete”, Grigore 2016
“A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory”, Yedidia & Aaronson 2016
A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
“Open Games: Compositional Game Theory”, Ghani et al 2016
Advances in Physarum Machines: Sensing and Computing With Slime Mould, Adamatzky 2016
Advances in Physarum Machines: Sensing and Computing with Slime Mould
“On Having No Head: Cognition throughout Biological Systems”, Baluška & Levin 2016
“We Need Less Powerful Languages [Langsec]”, Plant 2015
“Undecidability of the Spectral Gap”, Cubitt et al 2015
“What Are Weird Machines?”, Bratus 2015
“Braid Is Undecidable”, Hamilton 2014
“Computing With a Full Memory: Catalytic Space”, Buhrman et al 2014
“Implementing a Web Server in a Single printf() Call”
“Teaching Mario to Play Pong and Snake Through Innumerable Exploits”
Teaching Mario to Play Pong and Snake Through Innumerable Exploits
“Converting Untrusted PDFs into Trusted Ones: The Qubes Way”
“Mathematics in the Age of the Turing Machine”, Hales 2013
“On Unsettleable Arithmetical Problems”, Conway 2013
“The Page-Fault Weird Machine: Lessons in Instruction-Less Computation”, Bangert 2013
The Page-Fault Weird Machine: Lessons in Instruction-less Computation :
“Using Routers to Build Logic Circuits: How Powerful Is BGP?”, Chiesa 2013
Using routers to build logic circuits: How powerful is BGP? :
“Is the Network Turing-Complete? EPFL Technical Report 187131”, Peresini & Kostic 2013
Is the Network Turing-Complete? EPFL Technical Report 187131 :
“Turning Oscillations into Opportunities: Lessons from a Bacterial Decision Gate”, Schultz et al 2013
Turning oscillations into opportunities: lessons from a bacterial decision gate
“The Configuration Complexity Clock”, Hadlow 2012
“Buridan’s Principle”, Lamport 2012
“Robust Soldier Crab Ball Gate”, Gunji et al 2012
“Buridan’s Principle [Publication Problems Delaying 1984 → 2012]”, Lamport 2012
Buridan’s Principle [publication problems delaying 1984 → 2012]
“Exploitation and State Machines: Programming the ‘Weird Machine’ Revisited”, Flake 2011
Exploitation and State Machines: Programming the ‘Weird Machine’ Revisited :
View PDF:
“Quantum Computation With Devices Whose Contents Are Never Read”, Yakaryilmaz et al 2010
Quantum computation with devices whose contents are never read
“Ant-Based Computing”, Michael 2009
“Physics, Topology, Logic and Computation: A Rosetta Stone”, Baez & Stay 2009
“High Performance SQL With PostgreSQL 8.4: Lists and Recursion and Trees, Oh My!”, Fetter 2009
High Performance SQL with PostgreSQL 8.4: Lists and Recursion and Trees, Oh My! :
“Deciding Fate in Adverse Times: Sporulation and Competence in Bacillus Subtilis”, Schultz et al 2009
Deciding fate in adverse times: sporulation and competence in Bacillus subtilis
“Small Universal Turing Machines”, Neary 2008
“Closed Timelike Curves Make Quantum and Classical Computing Equivalent”, Aaronson & Watrous 2008
Closed Timelike Curves Make Quantum and Classical Computing Equivalent
“Omega Monad: Enumerating a Context-Free Language”, Palmer 2008
“Perl Cannot Be Parsed: A Formal Proof”, Kegler 2008
“Algorithmic Self-Assembly of DNA”, Winfree 2008
“On Universal Prediction and Bayesian Confirmation”, Hutter 2007
“Infinite Sets That Admit Fast Exhaustive Search”, Escardo 2007
“Can Newtonian Systems, Bounded in Space, Time, Mass and Energy Compute All Functions?”, Beggs & Tucker 2007
Can Newtonian systems, bounded in space, time, mass and energy compute all functions?
“Infinite Versions of Minesweeper Are Turing Complete”, Kate 2007
“On the Computational Power of Threshold Circuits With Sparse Activity”, Uchizawa et al 2006
On the Computational Power of Threshold Circuits with Sparse Activity
“No Quantum Advantage for Nonlocal Computation”, Linden et al 2006
“Static Typing for a Faulty Lambda Calculus”, Walker et al 2006
“Is There an Elegant Universal Theory of Prediction?”, Legg 2006
Good and Real: Demystifying Paradoxes from Physics to Ethics, Drescher 2006
Good and Real: Demystifying Paradoxes from Physics to Ethics
“A Box, Darkly: Obfuscation, Weird Languages, and Code Esthetics”, Mateas & Montfort 2005
A Box, Darkly: Obfuscation, Weird Languages, and Code esthetics
“The Halting Problem Is Decidable on a Set of Asymptotic Probability One”, Hamkins & Miasnikov 2005
The halting problem is decidable on a set of asymptotic probability one
“A Theory of Quantum Gravity Based on Quantum Computation”, Lloyd 2005
“A Simple Proof for the Turing-Completeness of XSLT and XQuery”, Kepser 2004
A Simple Proof for the Turing-Completeness of XSLT and XQuery
“Gödel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements”, Schmidhuber 2003
Gödel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements
“Philosophical Problems in Logic § Ultrafinitism”, Friedman 2002 (page 4)
“Analytic and Algorithmic Solution of Random Satisfiability Problems”, Mezard et al 2002
Analytic and Algorithmic Solution of Random Satisfiability Problems
“The Fastest and Shortest Algorithm for All Well-Defined Problems”, Hutter 2002
The Fastest and Shortest Algorithm for All Well-Defined Problems
“Forbidden Information”, Levin 2002
“Sendmail As a Turing Machine”, Kiselyov 2000
“Counterfactual Computation”, Mitchison & Jozsa 1999
“P/NP, and the Quantum Field Computer”, Freedman 1998
“Limitations of Noisy Reversible Computation”, Aharonov et al 1996
“A Personal View of Average-Case Complexity”, Impagliazzo 1995
“Threshold Circuits of Bounded Depth”, Hajnal et al 1993
“The Complexity of N-Body Simulation”, Reif & Tate 1993
“Average Case Complexity under the Universal Distribution Equals Worst-Case Complexity”, Li & Vitányi 1992
Average case complexity under the universal distribution equals worst-case complexity
“Time Travel and Computing”, Moravec 1991
“Unpredictability and Undecidability in Dynamical Systems”, Moore 1990
“A Differentiation Primitive for Extended Λ–calculus”, Flaherty 1988
“FRACTRAN: A Simple Universal Programming Language for Arithmetic”, Conway 1987
FRACTRAN: A Simple Universal Programming Language for Arithmetic
“Conservative Logic”, Fredkin & Toffoli 1982
“Bi-Continuous Extensions of Invertible Combinatorial Functions”, Toffoli 1981
Bi-continuous extensions of invertible combinatorial functions
“Unpredictable Iterations”, Conway 1972
View PDF:
“О Невозможности Элиминации Полного Перебора При Вычислении Функций Относительно Их Графиков”, Дехтярь 1969
О невозможности элиминации полного перебора при вычислении функций относительно их графиков :
View PDF:
“FLODAC—A Pure Fluid Digital Computer”, Gluskin et al 1964
FLODAC—A Pure Fluid Digital Computer :
View PDF:
“Tag Systems and Lag Systems”, Wang 1963
“On Non-Computable Functions”, Rado 1962
“Representation of Events in Nerve Nets and Finite Automata”, Kleene 1951
Representation of Events in Nerve Nets and Finite Automata :
View PDF:
“‘Computational Complexity of Air Travel Planning’, De Marcken 2003 [ITA Software]”
‘Computational Complexity of Air Travel Planning’, de Marcken 2003 [ITA Software] :
“Universal Search § OOPS and Other Incremental Variations”
“Computing With Time: Microarchitectural Weird Machines”
“How Exploits Impact Computer Science Theory”
“The Dhall Configuration Language”
“ByteByteJump”, Wiki 2026
“Linear Bounded Automaton”
“OISC”
“HexHive/printbf: Brainfuck Interpreter inside Printf”
“InkboxSoftware/excelCPU: 16-Bit CPU for Excel, and Related Files”
InkboxSoftware/excelCPU: 16-bit CPU for Excel, and related files
“A WebAssembly Runtime Implemented in TypeScript Types [Which Runs Doom]”
A WebAssembly runtime implemented in TypeScript types [which runs Doom]
“roguetype: The First Ever Rogue-Like Written in the OCaml Type System”, Octachron 2026
roguetype: The first ever rogue-like written in the OCaml type system
“Sudoku Solving in Python Packaging”
“MalbolgeLisp Is a LISP Interpreter Written in Malbolge. It’s (As of 2020 and 2021), the Most Advanced, Usable Malbolge Program Ever Created. It Supports Everything Lisps Generally Tend to Support (Like cond, let, lambda, Etc…).”
“How I Did Relay Quine”
“Using SQL’s Turing Completeness to Build Tetris”
“C99 Doesn’t Need Function Bodies, Or, ‘VLAs Are Turing Complete’”
C99 doesn’t need function bodies, or, ‘VLAs are Turing complete’
“Another New Record in Self-Cleaning Turing Machines”
“find + mkdir Is Turing Complete (Retracted)”, Kako 2026
“Predicting the Tide With an Analog Computer Made from Lego”
“PEP 611: The One Million Limit”
“Choon Programming Language”
“Rosser’s Theorem via Turing Machines”
“Busy Beaver(5) Is Now Proven to Be 47,176,870”
“Rust’s Type System Is Turing-Complete”, Leffler 2026
Rust’s Type System is Turing-Complete
View External Link:
“OpenTTD Logic”
“Weird Machines HQ”
“The Infinity Machine”
Fontemon
“A Computational No-Coincidence Principle”
“A Brief History of Liquid Computers”
“Rule 110 Train Turing Machine Explained”
“I Built ChatGPT With Minecraft Redstone!”
“Turing Machine Busy Beaver 5 Champ–47,176,870 Steps–Perfect Pixel Binning”
Turing Machine Busy Beaver 5 Champ–47,176,870 Steps–Perfect Pixel Binning
“On The Turing Completeness of PowerPoint”
Sort By Magic
Annotations sorted by machine learning into inferred 'tags'. This provides an alternative way to browse: instead of by date order, one can browse in topic order. The 'sorted' list has been automatically clustered into multiple sections & auto-labeled for easier browsing.
Beginning with the newest annotation, it uses the embedding of each annotation to attempt to create a list of nearest-neighbor annotations, creating a progression of topics. For more details, see the link.
universal-prediction
turing-completeness
universal-approximator
threshold-circuits expressivity computation transformers log-precision circuits
Wikipedia (47)
Miscellaneous
/doc/cs/computable/2022-garg-figure5b-transformersbeatxgboostatfittingsmalldecisiontrees.png/doc/cs/computable/2008-neary-figure111-spacetimetradeoffinminimalturingmachines.jpghttp://pepijndevos.nl/2022/01/30/predicting-the-tide-with-an-analog-computer-made-from-lego.htmlhttp://weblog.raganwald.com/2004/10/beware-of-turing-tar-pit.htmlhttps://blog.computationalcomplexity.org/2023/12/where-do-non-primitive-recursive.htmlhttps://blog.cryptographyengineering.com/2017/07/02/beyond-public-key-encryption/https://dev.to/grahamthedev/bubble-sortin-pure-css-no-js-3bb1https://dev.to/grahamthedev/pure-css-neural-network-aiits-easier-that-you-think-f02https://dspace.mit.edu/bitstream/handle/1721.1/6486/AIM-1026a.pdf?sequence=2https://dwarffortresswiki.org/index.php/v0.31:Creature_logicView External Link:
https://dwarffortresswiki.org/index.php/v0.31:Creature_logichttps://eli.thegreenplace.net/2023/demystifying-tuppers-formula/View External Link:
https://eli.thegreenplace.net/2023/demystifying-tuppers-formula/https://github.com/harfbuzz/harfbuzz-wasm-examples?tab=readme-ov-file#hieroglyphshttps://github.com/mgarciaisaia/JavaScript-Is-Weird-as-a-compressorhttps://nostalgebraist.tumblr.com/post/740164510909890560/information-flow-in-transformershttps://thaliaarchi.github.io/coq-turing-typeclass/View External Link:
https://web.archive.org/web/20170815022856/http://acarol.woz.org/LegoDifferenceEngine.htmlhttps://willhbr.net/2024/03/15/making-a-compiler-to-prove-tmux-is-turing-complete/https://www.amirrorclear.net/academic/ideas/simulation/index.htmlhttps://www.lesswrong.com/posts/HkghiK6Rt35nbgwKA/hard-coding-neural-computationView External Link:
https://www.lesswrong.com/posts/HkghiK6Rt35nbgwKA/hard-coding-neural-computationhttps://www.lesswrong.com/posts/bC5xd7wQCnTDw7Kyx/getting-up-to-speed-on-the-speed-prior-in-2022https://www.quantamagazine.org/in-new-paradox-black-holes-appear-to-evade-heat-death-20230606/https://www.quantamagazine.org/the-beautiful-intelligence-of-bacteria-and-other-microbes-20171113/https://www.quantamagazine.org/the-mysterious-math-of-billiards-tables-20240215/https://www.reenigne.org/blog/8088-pc-speaker-mod-player-how-its-done/https://xorshammer.com/2010/02/17/quantish-physics-a-discrete-model-of-quantum-physics/
Bibliography
https://arxiv.org/abs/2503.24187: “NeuRaLaTeX: A Machine Learning Library Written in Pure LaTeX”,https://arxiv.org/abs/2502.17779: “Simulating Time With Square-Root Space”,https://arxiv.org/abs/2410.18077#deepmind: “ALTA: Compiler-Based Analysis of Transformers”,https://arxiv.org/abs/2410.03170#deepmind: “Autoregressive Large Language Models Are Computationally Universal”,https://arxiv.org/abs/2408.08292: “Optimization by Decoded Quantum Interferometry”,https://arxiv.org/abs/2406.05564: “Automata Extraction from Transformers”,https://arxiv.org/abs/2402.09963: “Why Are Sensitive Functions Hard for Transformers?”,https://arxiv.org/abs/2305.17872: “Universal Mechanical Polycomputation in Granular Matter”,https://arxiv.org/abs/2208.01066: “What Can Transformers Learn In-Context? A Case Study of Simple Function Classes”,https://arxiv.org/abs/2106.06981: “RASP: Thinking Like Transformers”,https://arxiv.org/abs/2012.12828: “Constructing Turing Complete Euler Flows in Dimension 3”,https://www.quantamagazine.org/how-the-slowest-computer-programs-illuminate-maths-fundamental-limits-20201210/: “How the Slowest Computer Programs Illuminate Math’s Fundamental Limits: The Goal of the ‘Busy Beaver’ Game Is to Find the Longest-Running Computer Program. Its Pursuit Has Surprising Connections to Some of the Most Profound Questions and Concepts in Mathematics”,2019-aaronson.pdf: “The Busy Beaver Frontier”,https://www.cs.dartmouth.edu/~sergey/wm/: “What Are Weird Machines?”,2013-conway.pdf: “On Unsettleable Arithmetical Problems”,2006-walker.pdf: “Static Typing for a Faulty Lambda Calculus”,https://www.ncbi.nlm.nih.gov/pmc/articles/PMC18139/: “P/NP, and the Quantum Field Computer”,https://www.sciencedirect.com/science/article/pii/002200009390001D: “Threshold Circuits of Bounded Depth”,1990-moore.pdf: “Unpredictability and Undecidability in Dynamical Systems”,https://esolangs.org/wiki/ByteByteJump: “ByteByteJump”,