- See Also
-
Links
- “The Illusion of State in State-Space Models”, Merrill et al 2024
- “Why Are Sensitive Functions Hard for Transformers?”, Hahn & Rofin 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
- “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
- “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
- “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
- “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
- “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
- “On Unsettleable Arithmetical Problems”, Conway 2013
- “The Page-Fault Weird Machine: Lessons in Instruction-Less Computation”, Bangert 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
- “Exploitation and State Machines: Programming the ‘Weird Machine’ Revisited”, Flake 2011
- “Ant-Based Computing”, Michael 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
- “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
- “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
- “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
- “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
- “Time Travel and Computing”, Moravec 1991
- “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”
- “ByteByteJump”, Wiki 2024
- “Linear Bounded Automaton”
- “OISC”
- “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...).”
- Sort By Magic
- Wikipedia
- Miscellaneous
- Link Bibliography
See Also
Links
“The Illusion of State in State-Space Models”, Merrill et al 2024
“Why Are Sensitive Functions Hard for Transformers?”, Hahn & Rofin 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
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
“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
“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
“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
“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
“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
“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
“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
“Exploitation and State Machines: Programming the ‘Weird Machine’ Revisited”, Flake 2011
Exploitation and State Machines: Programming the ‘Weird Machine’ Revisited
“Ant-Based Computing”, Michael 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
“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
“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
“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
“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
“Time Travel and Computing”, Moravec 1991
“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
“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]”
‘Computational Complexity of Air Travel Planning’, de Marcken 2003 [ITA Software]
“Universal Search § OOPS and Other Incremental Variations”
“ByteByteJump”, Wiki 2024
“Linear Bounded Automaton”
“OISC”
“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...).”
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-complete
transformers
computability
Wikipedia
Miscellaneous
-
/doc/cs/computable/2022-garg-figure5b-transformersbeatxgboostatfittingsmalldecisiontrees.png: -
http://pepijndevos.nl/2022/01/30/predicting-the-tide-with-an-analog-computer-made-from-lego.html:View HTML (15MB):
/doc/www/pepijndevos.nl/dcfffdcd34b8de66767de7bf2953b037ebeaf4f8.html -
https://blog.computationalcomplexity.org/2023/12/where-do-non-primitive-recursive.html: -
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://eli.thegreenplace.net/2023/demystifying-tuppers-formula/ -
https://github.com/mgarciaisaia/JavaScript-Is-Weird-as-a-compressor -
https://github.com/mmulet/code-relay/blob/main/markdown/HowIDidIt.md -
https://nickdrozd.github.io/2022/01/10/another-self-cleaning-turing-machine.html: -
https://nostalgebraist.tumblr.com/post/740164510909890560/information-flow-in-transformers -
https://thaliaarchi.github.io/coq-turing-typeclass/:View External Link:
-
https://twitter.com/prerationalist/status/1612872812414308403: -
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 -
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/
Link Bibliography
-
https://arxiv.org/abs/2402.09963: “Why Are Sensitive Functions Hard for Transformers?”, Michael Hahn, Mark Rofin -
https://arxiv.org/abs/2305.17872: “Universal Mechanical Polycomputation in Granular Matter”, Atoosa Parsa, Sven Witthaus, Nidhi Pashine, Corey S. O’Hern, Rebecca Kramer-Bottiglio, Josh Bongard -
https://arxiv.org/abs/2208.01066: “What Can Transformers Learn In-Context? A Case Study of Simple Function Classes”, Shivam Garg, Dimitris Tsipras, Percy Liang, Gregory Valiant -
https://arxiv.org/abs/2106.06981: “RASP: Thinking Like Transformers”, Gail Weiss, Yoav Goldberg, Eran Yahav -
https://arxiv.org/abs/2012.12828: “Constructing Turing Complete Euler Flows in Dimension 3”, Robert Cardona, Eva Miranda, Daniel Peralta-Salas, Francisco Presas -
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”, John Pavlus -
2019-aaronson.pdf: “The Busy Beaver Frontier”, Scott Aaronson -
https://www.cs.dartmouth.edu/~sergey/wm/: “What Are Weird Machines?”, Sergey Bratus -
2013-conway.pdf: “On Unsettleable Arithmetical Problems”, John H. Conway -
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC18139/: “P/NP, and the Quantum Field Computer”, M H. Freedman -
https://www.sciencedirect.com/science/article/pii/002200009390001D: “Threshold Circuits of Bounded Depth”, András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán