 See Also

Links
 “Can a Transformer Represent a Kalman Filter?”, Goel & Bartlett 2023
 “The Expressive Power of Transformers With ChainofThought”, Merrill & Sabharwal 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
 “Characterizing Intrinsic Compositionality in Transformers With Tree Projections”, Murty et al 2022
 “Transformers Learn Shortcuts to Automata”, Liu et al 2022
 “Transformers Implement FirstOrder Logic With Majority Quantifiers”, Merrill & Sabharwal 2022
 “Python Type Hints Are Turing Complete”, Roth 2022
 “What Can Transformers Learn InContext? A Case Study of Simple Function Classes”, Garg et al 2022
 “Perceptein: A Synthetic Proteinlevel Neural Network in Mammalian Cells”, Chen et al 2022
 “Neural Networks and the Chomsky Hierarchy”, Delétang et al 2022
 “LogPrecision Transformers Are ConstantDepth Uniform Threshold Circuits”, Merrill & Sabharwal 2022
 “An RNAbased Theory of Natural Universal Computation”, Akhlaghpour 2022
 “Overcoming a Theoretical Limitation of SelfAttention”, Chiang & Cholak 2022
 “A Deep Dive into an NSO Zeroclick 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
 “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 Longestrunning 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 Objectqb﹚ Cube”, Vučinović 2018
 “Weird Machines, Exploitability, and Provable Unexploitability”, Dullien 2017
 “Communication between Viruses Guides Lysislysogeny 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 PageFault Weird Machine: Lessons in Instructionless Computation”, Bangert 2013
 “Is the Network TuringComplete? 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
 “AntBased 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
 “Algorithmic Selfassembly 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
 “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 WellDefined Problems”, Hutter 2002
 “Sendmail As a Turing Machine”, Oleg 2000
 “P/NP, and the Quantum Field Computer”, Freedman 1998
 “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
 “Bicontinuous Extensions of Invertible Combinatorial Functions”, Toffoli 1981
 “Unpredictable Iterations”, Conway 1972
 “FLODAC—A Pure Fluid Digital Computer”, Gluskin et al 1964
 “On NonComputable Functions”, Rado 1962
 “‘Computational Complexity of Air Travel Planning’, De Marcken 2003 [ITA Software]”
 “Universal Search § OOPS and Other Incremental Variations”
 “Artificial Immune System”
 “Büchi Arithmetic”
 “Chris Langton”
 “Common Lisp”
 “Common Lisp Object System”
 “Continuation”
 “Emacs”
 “Flavors (programming Language)”
 “GNU Emacs”
 “Open Genera”
 “Goodstein's Theorem”
 “Iota and Jot”
 “JSFuck”
 “Kolmogorov Complexity § Chaitin's Incompleteness Theorem”
 “Langton's Ant”
 “Lisp Machine Lisp”
 “Lisp Machines”
 “Lisp Machine”
 “Macsyma”
 “Metaobject”
 “Quorum Sensing”
 “Symbolics”
 “Symbolics Document Examiner”
 “TC0”
 “Turmite”
 “Zmacs”
 “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
 Miscellaneous
 Link Bibliography
See Also
Links
“Can a Transformer Represent a Kalman Filter?”, Goel & Bartlett 2023
“The Expressive Power of Transformers With ChainofThought”, Merrill & Sabharwal 2023
“The Expressive Power of Transformers with ChainofThought”
“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
“Tighter Bounds on the Expressivity of Transformer Encoders”
“Memory Augmented Large Language Models Are Computationally Universal”, Schuurmans 2023
“Memory Augmented Large Language Models are Computationally Universal”
“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 FirstOrder Logic With Majority Quantifiers”, Merrill & Sabharwal 2022
“Transformers Implement FirstOrder Logic with Majority Quantifiers”
“Python Type Hints Are Turing Complete”, Roth 2022
“What Can Transformers Learn InContext? A Case Study of Simple Function Classes”, Garg et al 2022
“What Can Transformers Learn InContext? A Case Study of Simple Function Classes”
“Perceptein: A Synthetic Proteinlevel Neural Network in Mammalian Cells”, Chen et al 2022
“Perceptein: A synthetic proteinlevel neural network in mammalian cells”
“Neural Networks and the Chomsky Hierarchy”, Delétang et al 2022
“LogPrecision Transformers Are ConstantDepth Uniform Threshold Circuits”, Merrill & Sabharwal 2022
“LogPrecision Transformers are ConstantDepth Uniform Threshold Circuits”
“An RNAbased Theory of Natural Universal Computation”, Akhlaghpour 2022
“Overcoming a Theoretical Limitation of SelfAttention”, Chiang & Cholak 2022
“A Deep Dive into an NSO Zeroclick IMessage Exploit: Remote Code Execution”, Beer & Groß 2021
“A deep dive into an NSO zeroclick 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
“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 Longestrunning 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 Objectqb﹚ Cube”, Vučinović 2018
“Mechanical Computing System Using Only One Physical Objectqb﹚ cube”
“Weird Machines, Exploitability, and Provable Unexploitability”, Dullien 2017
“Weird machines, exploitability, and provable unexploitability”
“Communication between Viruses Guides Lysislysogeny Decisions”, Erez et al 2017
“Communication between viruses guides lysislysogeny 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
“On Having No Head: Cognition throughout Biological Systems”
“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 PageFault Weird Machine: Lessons in Instructionless Computation”, Bangert 2013
“The PageFault Weird Machine: Lessons in Instructionless Computation”
“Is the Network TuringComplete? EPFL Technical Report 187131”, Peresini & Kostic 2013
“Is the Network TuringComplete? 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”
“AntBased 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”
“Algorithmic Selfassembly 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”
“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 WellDefined Problems”, Hutter 2002
“The Fastest and Shortest Algorithm for All WellDefined Problems”
“Sendmail As a Turing Machine”, Oleg 2000
“P/NP, and the Quantum Field Computer”, Freedman 1998
“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
“Bicontinuous Extensions of Invertible Combinatorial Functions”, Toffoli 1981
“Bicontinuous extensions of invertible combinatorial functions”
“Unpredictable Iterations”, Conway 1972
“FLODAC—A Pure Fluid Digital Computer”, Gluskin et al 1964
“On NonComputable 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”
“Artificial Immune System”
“Büchi Arithmetic”
“Chris Langton”
“Common Lisp”
“Common Lisp Object System”
“Continuation”
“Emacs”
“Flavors (programming Language)”
“GNU Emacs”
“Open Genera”
“Goodstein's Theorem”
“Iota and Jot”
“JSFuck”
“Kolmogorov Complexity § Chaitin's Incompleteness Theorem”
“Langton's Ant”
“Lisp Machine Lisp”
“Lisp Machines”
“Lisp Machine”
“Macsyma”
“Metaobject”
“Quorum Sensing”
“Symbolics”
“Symbolics Document Examiner”
“TC0”
“Turmite”
“Zmacs”
“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 & autolabeled for easier browsing.
Beginning with the newest annotation, it uses the embedding of each annotation to attempt to create a list of nearestneighbor annotations, creating a progression of topics. For more details, see the link.
universalcomputation
weirdmachines
computabilitytheory
computability
transformeranalysis
Miscellaneous

/doc/cs/computable/2022gargfigure5btransformersbeatxgboostatfittingsmalldecisiontrees.png
: 
http://pepijndevos.nl/2022/01/30/predictingthetidewithananalogcomputermadefromlego.html

https://blog.computationalcomplexity.org/2023/12/wheredononprimitiverecursive.html

https://dev.to/grahamthedev/bubblesortinpurecssnojs3bb1

https://dev.to/grahamthedev/purecssneuralnetworkaiitseasierthatyouthinkf02

https://dspace.mit.edu/bitstream/handle/1721.1/6486/AIM1026a.pdf?sequence=2
: 
https://eli.thegreenplace.net/2023/demystifyingtuppersformula/

https://github.com/mgarciaisaia/JavaScriptIsWeirdasacompressor

https://github.com/mmulet/coderelay/blob/main/markdown/HowIDidIt.md

https://nostalgebraist.tumblr.com/post/740164510909890560/informationflowintransformers

https://twitter.com/prerationalist/status/1612872812414308403

https://web.archive.org/web/20170815022856/http://acarol.woz.org/LegoDifferenceEngine.html

https://www.amirrorclear.net/academic/ideas/simulation/index.html

https://www.lesswrong.com/posts/HkghiK6Rt35nbgwKA/hardcodingneuralcomputation

https://www.lesswrong.com/posts/bC5xd7wQCnTDw7Kyx/gettinguptospeedonthespeedpriorin2022

https://www.quantamagazine.org/innewparadoxblackholesappeartoevadeheatdeath20230606/

https://www.quantamagazine.org/thebeautifulintelligenceofbacteriaandothermicrobes20171113/

https://www.quantamagazine.org/themysteriousmathofbilliardstables20240215/

https://www.reenigne.org/blog/8088pcspeakermodplayerhowitsdone/

https://xorshammer.com/2010/02/17/quantishphysicsadiscretemodelofquantumphysics/
Link Bibliography

https://arxiv.org/abs/2305.17872
: “Universal Mechanical Polycomputation in Granular Matter”, Atoosa Parsa, Sven Witthaus, Nidhi Pashine, Corey S. O’Hern, Rebecca KramerBottiglio, Josh Bongard 
https://arxiv.org/abs/2208.01066
: “What Can Transformers Learn InContext? 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 PeraltaSalas, Francisco Presas 
https://www.quantamagazine.org/howtheslowestcomputerprogramsilluminatemathsfundamentallimits20201210/
: “How the Slowest Computer Programs Illuminate Math’s Fundamental Limits: The Goal of the ‘busy Beaver’ Game Is to Find the Longestrunning Computer Program. Its Pursuit Has Surprising Connections to Some of the Most Profound Questions and Concepts in Mathematics”, John Pavlus 
2019aaronson.pdf
: “The Busy Beaver Frontier”, Scott Aaronson 
https://www.cs.dartmouth.edu/~sergey/wm/
: “What Are Weird Machines?”, Sergey Bratus 
2013conway.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