Ask, and it shall be given: Turing completeness of prompting
Computer Scientists Combine Two ‘Beautiful’ Proof Methods [ZK + PCP]
Hypercomputation without Bothering the Cactus People: Software Development for the DMT Headspace
Quantum Convolutional Neural Networks are (Effectively) Classically Simulable
Chain-of-Thought Empowers Transformers to Solve Inherently Serial Problems
Linux/4004: Slowly Booting Full Linux on the Intel 4004 CPU for Fun, Art, and Absolutely No Profit
Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly the Star-Free Languages
The Expressive Power of Transformers with Chain-of-Thought
Towards Revealing the Mystery behind Chain-of-Thought: A Theoretical Perspective
Tighter Bounds on the Expressivity of Transformer Encoders
Memory Augmented Large Language Models are Computationally Universal
Characterizing Intrinsic Compositionality in Transformers with Tree Projections
Transformers Implement First-Order Logic with Majority Quantifiers
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes
Perceptein: A synthetic protein-level neural network in mammalian cells
Log-Precision Transformers are Constant-Depth Uniform Threshold Circuits
A deep dive into an NSO zero-click iMessage exploit: Remote Code Execution
Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine
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
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
Remembering John Conway’s FRACTRAN, a ridiculous, yet surprisingly deep language
On the Turing Completeness of Modern Neural Network Architectures
Deciphering the Molecular Mechanism Underpinning Phage Arbitrium Communication Systems
Mechanical Computing System Using Only One Physical Object-qb cube
Weird machines, exploitability, and provable unexploitability
Communication between viruses guides lysis-lysogeny decisions
A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
Advances in Physarum Machines: Sensing and Computing with Slime Mould
On Having No Head: Cognition throughout Biological Systems
Teaching Mario to Play Pong and Snake Through Innumerable Exploits
Converting Untrusted PDFs into Trusted Ones: The Qubes Way
The Page-Fault Weird Machine: Lessons in Instruction-Less Computation
Using Routers to Build Logic Circuits: How Powerful Is BGP?
Is the Network Turing-Complete? EPFL Technical Report 187131
Turning oscillations into opportunities: lessons from a bacterial decision gate
Exploitation and State Machines: Programming the ‘Weird Machine’ Revisited
Quantum computation with devices whose contents are never read
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
On the Computational Power of Threshold Circuits with Sparse Activity
Good and Real: Demystifying Paradoxes from Physics to Ethics
A Box, Darkly: Obfuscation, Weird Languages, and Code esthetics
The halting problem is decidable on a set of asymptotic probability one
A Simple Proof for the Turing-Completeness of XSLT and XQuery
Analytic and Algorithmic Solution of Random Satisfiability Problems
The Fastest and Shortest Algorithm for All Well-Defined Problems
FRACTRAN: A Simple Universal Programming Language for Arithmetic
Bi-continuous extensions of invertible combinatorial functions
‘Computational Complexity of Air Travel Planning’, De Marcken 2003 [ITA Software]
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...).
C99 Doesn’t Need Function Bodies, Or, ‘VLAs Are Turing Complete’
2022-garg-figure5b-transformersbeatxgboostatfittingsmalldecisiontrees.png
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
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://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/K7AyY8LMrcKhwfbyj/no-really-attention-is-all-you-need-attention-can-do
https://www.lesswrong.com/posts/QNQuWB3hS5FrGp5yZ/programmatic-backdoors-dnns-can-use-sgd-to-run-arbitrary
https://www.lesswrong.com/posts/bC5xd7wQCnTDw7Kyx/getting-up-to-speed-on-the-speed-prior-in-2022
https://www.pypy.org/posts/2018/09/the-first-15-years-of-pypy-3412615975376972020.html#why-did-we-abandon-partial-evaluation
99ddb5cdb94272b117d779153234a77b05980897.html#why-did-we-abandon-partial-evaluation
https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/
https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/
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/
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes
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
https%253A%252F%252Fwww.quantamagazine.org%252Fhow-the-slowest-computer-programs-illuminate-maths-fundamental-limits-20201210%252F.html
https%253A%252F%252Fwww.cs.dartmouth.edu%252F~sergey%252Fwm%252F.html
https%253A%252F%252Fwww.ncbi.nlm.nih.gov%252Fpmc%252Farticles%252FPMC18139%252F.html
https%253A%252F%252Fwww.sciencedirect.com%252Fscience%252Farticle%252Fpii%252F002200009390001D.html
Wikipedia Bibliography:
