‘computability’ directory
- See Also
-
Links
- “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
- “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
- “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
- “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
- “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
- “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
- “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
- “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
- “The Busy Beaver Frontier”, Aaronson 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
- “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
- “Weird Machines, Exploitability, and Provable Unexploitability”, Dullien 2017
- “Communication between Viruses Guides Lysis-Lysogeny Decisions”, Erez et al 2017
- “Java Generics Are Turing Complete”, Grigore 2016
- “A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory”, Yedidia & Aaronson 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
- “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
- “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
- “Robust Soldier Crab Ball Gate”, Gunji et al 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
- “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
- 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 Simple Proof for the Turing-Completeness of XSLT and XQuery”, Kepser 2004
- “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
- “Sendmail As a Turing Machine”, Oleg 2000
- “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
- “FLODAC—A Pure Fluid Digital Computer”, Gluskin et al 1964
- “On Non-Computable Functions”, Rado 1962
- “‘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”
- “ByteByteJump”, Wiki 2025
- “Linear Bounded Automaton”
- “OISC”
- “HexHive/printbf: Brainfuck Interpreter inside Printf”
- “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 2025 - “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”
- “Weird Machines HQ”
- “OpenTTD Logic”
- “The Infinity Machine”
- Fontemon
- “A Computational No-Coincidence Principle”
- “A Brief History of Liquid Computers”
- “On The Turing Completeness of PowerPoint”
- Sort By Magic
- Wikipedia
- Miscellaneous
- Bibliography
See Also
Links
“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
“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
“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
“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
“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
“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
“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
“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
“The Busy Beaver Frontier”, Aaronson 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
“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
“Weird Machines, Exploitability, and Provable Unexploitability”, Dullien 2017
Weird machines, exploitability, and provable unexploitability
“Communication between Viruses Guides Lysis-Lysogeny Decisions”, Erez et al 2017
Communication between viruses guides lysis-lysogeny decisions
“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
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
“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
“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”
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
“Robust Soldier Crab Ball Gate”, Gunji et al 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
“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
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 Simple Proof for the Turing-Completeness of XSLT and XQuery”, Kepser 2004
A Simple Proof for the Turing-Completeness of XSLT and XQuery
“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
“Sendmail As a Turing Machine”, Oleg 2000
“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:
“FLODAC—A Pure Fluid Digital Computer”, Gluskin et al 1964
FLODAC—A Pure Fluid Digital Computer :
View PDF:
“On Non-Computable Functions”, Rado 1962
“‘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”
“ByteByteJump”, Wiki 2025
“Linear Bounded Automaton”
“OISC”
OISC :
“HexHive/printbf: Brainfuck Interpreter inside Printf”
“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 2025
“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”
“Weird Machines HQ”
“OpenTTD Logic”
View External Link:
“The Infinity Machine”
Fontemon
“A Computational No-Coincidence Principle”
“A Brief History of Liquid Computers”
“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.
turing-completeness
universal-computation
transformer-theory
Wikipedia
Miscellaneous
-
/doc/cs/computable/2022-garg-figure5b-transformersbeatxgboostatfittingsmalldecisiontrees.png: -
/doc/cs/computable/2008-neary-figure111-spacetimetradeoffinminimalturingmachines.jpg: -
http://pepijndevos.nl/2022/01/30/predicting-the-tide-with-an-analog-computer-made-from-lego.html: -
http://weblog.raganwald.com/2004/10/beware-of-turing-tar-pit.html -
https://blog.computationalcomplexity.org/2023/12/where-do-non-primitive-recursive.html: -
https://blog.cryptographyengineering.com/2017/07/02/beyond-public-key-encryption/: -
https://dev.to/grahamthedev/bubble-sortin-pure-css-no-js-3bb1 -
https://dev.to/grahamthedev/pure-css-neural-network-aiits-easier-that-you-think-f02 -
https://dspace.mit.edu/bitstream/handle/1721.1/6486/AIM-1026a.pdf?sequence=2: -
https://dwarffortresswiki.org/index.php/v0.31:Creature_logic:View External Link:
https://dwarffortresswiki.org/index.php/v0.31:Creature_logic -
https://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#hieroglyphs: -
https://github.com/mgarciaisaia/JavaScript-Is-Weird-as-a-compressor -
https://nostalgebraist.tumblr.com/post/740164510909890560/information-flow-in-transformers: -
https://thaliaarchi.github.io/coq-turing-typeclass/:View External Link:
-
https://web.archive.org/web/20170815022856/http://acarol.woz.org/LegoDifferenceEngine.html: -
https://willhbr.net/2024/03/15/making-a-compiler-to-prove-tmux-is-turing-complete/ -
https://www.amirrorclear.net/academic/ideas/simulation/index.html -
https://www.lesswrong.com/posts/HkghiK6Rt35nbgwKA/hard-coding-neural-computation:View External Link:
https://www.lesswrong.com/posts/HkghiK6Rt35nbgwKA/hard-coding-neural-computation -
https://www.lesswrong.com/posts/bC5xd7wQCnTDw7Kyx/getting-up-to-speed-on-the-speed-prior-in-2022: -
https://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/2410.18077#deepmind: “ALTA: Compiler-Based Analysis of 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”,