--- title: '‘computability’ directory' description: "Bibliography for directory cs/computable, most recent first: 213 annotations & 57 links ()." thumbnail: /doc/cs/computable/2008-neary-figure111-spacetimetradeoffinminimalturingmachines.jpg thumbnail-text: '' thumbnail-css: "outline" created: 2019-11-13 modified: 2026-09-14 status: in progress previous: /doc/cs/cellular-automaton/index next: /doc/cs/cryptography/index confidence: log importance: 0 css-extension: dropcaps-not index: True backlink: False ... # See Also ::: {#see-alsos .directory-indexes .columns} - [Parent ('*`CS`{=html}*' tag)](/doc/cs/index "Link to parent directory 'doc/cs/' (ascending)"){#_E6OE902I .link-annotated .link-tag .directory-indexes-upwards rel="tag"} ::: # Links {.display-pop-not} ## `“Executable Emoji”`{=html} {#_s1UJU-Pt-section} **[`Executable Emoji`{=html}](https://martypc.blogspot.com/2026/08/executable-emoji.html "Executable Emoji"){.link-modified-recently .id-not .include-annotation}** ::: aux-links-transclude-file ::: collapse **View HTML**: [`https://martypc.blogspot.com/2026/08/executable-emoji.html`](https://martypc.blogspot.com/2026/08/executable-emoji.html){.id-not .link-annotated-not .include-content .include-lazy} ::: ::: ## `“If LLMs Have Human-Like Attributes, Then So Does Age of Empires II”, Wynter 2026`{=html} {#wynter-2026-section} **[`If LLMs Have Human-Like Attributes, Then So Does Age of Empires II`{=html}](https://arxiv.org/abs/2605.31514 "'If LLMs Have Human-Like Attributes, Then So Does Age of Empires II', Wynter 2026"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Jira Is Turing-Complete: Building a Minsky Machine in Atlassian Automation”, Seriot 2026`{=html} {#seriot-2026-section} **[`Jira Is Turing-Complete: Building a Minsky Machine in Atlassian Automation`{=html}](https://seriot.ch/computation/jira.html "'Jira Is Turing-Complete: Building a Minsky Machine in Atlassian Automation', Seriot 2026"){.link-annotated-partial .id-not .include-annotation}** ## `“Every Feedforward Neural Network Definable in an O-Minimal Structure Has Finite Sample Complexity”, Kratsios et al 2026`{=html} {#kratsios-et-al-2026-section} **[`Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity`{=html}](https://arxiv.org/abs/2605.07097 "'Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity', Kratsios et al 2026"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“EML: All Elementary Functions from a Single Binary Operator”, Odrzywołek 2026`{=html} {#odrzywołek-2026-section} **[`EML: All elementary functions from a single binary operator`{=html}](https://arxiv.org/abs/2603.21852 "'EML: All elementary functions from a single binary operator', Odrzywołek 2026"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Classical Billiards Can Compute”, Miranda & Ramos 2025`{=html} {#miranda-ramos-2025-section} **[`Classical billiards can compute`{=html}](https://arxiv.org/abs/2512.19156 "'Classical billiards can compute', Miranda & Ramos 2025"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“CSS Values and Units Module Level 5 § 8.3: Conditional Value Selection: the if() Notation”, Atkins et al 2025`{=html} {#atkins-et-al-2025-section} **[`CSS Values and Units Module Level 5 § 8.3: Conditional Value Selection: the if() notation`{=html}](https://drafts.csswg.org/css-values-5/#if-notation "'CSS Values and Units Module Level 5 § 8.3: Conditional Value Selection: the if() notation', Atkins et al 2025"){.id-not .include-annotation}** ::: aux-links-transclude-file ::: collapse **View HTML**: [`/doc/www/drafts.csswg.org/9052fccfabee6ea55ee2f272a0eeb7d60acd57b4.html#if-notation`](/doc/www/drafts.csswg.org/9052fccfabee6ea55ee2f272a0eeb7d60acd57b4.html#if-notation){.id-not .link-annotated-not .include-content .include-lazy link-icon="internet-archive" link-icon-type="svg"} ::: ::: ## `“A Technical Introduction to Solomonoff Induction without K-Complexity”, Lang 2025`{=html} {#lang-2025-section} **[`A Technical Introduction to Solomonoff Induction without K-Complexity`{=html}](https://www.lesswrong.com/posts/HSDumToH57nSRdLST/a-technical-introduction-to-solomonoff-induction-without-k "'A Technical Introduction to Solomonoff Induction without K-Complexity', Lang 2025"){.link-annotated-partial .id-not .include-annotation link-icon="LW" link-icon-type="text" link-icon-color="#7faf83"}** ## `“Transformers Are Inherently Succinct”, Bergsträßer et al 2025`{=html} {#bergsträßer-et-al-2025-section} **[`Transformers are Inherently Succinct`{=html}](https://arxiv.org/abs/2510.19315 "'Transformers are Inherently Succinct', Bergsträßer et al 2025"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“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`{=html} {#nadis-2025-section} **[`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`{=html}](https://www.quantamagazine.org/researchers-discover-the-optimal-way-to-optimize-20251013/ "'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"){.id-not .include-annotation link-icon="quanta" link-icon-type="svg" link-icon-color="#ff8600"}** ## `“The QMA Singularity [GPT-5-Thinking Proves a Key Lemma]”, Aaronson 2025`{=html} {#aaronson-2025-section} **[`The QMA Singularity [GPT-5-Thinking proves a key lemma]`{=html}](https://scottaaronson.blog/?p=9183 "'The QMA Singularity [GPT-5-Thinking proves a key lemma]', Aaronson 2025"){.link-annotated-partial .id-not .include-annotation link-icon="SA" link-icon-type="text,sans" link-icon-color="#4181b7"}** ## `“Google’s Obfuscating VM-Based Anti-Bot System (BotGuard) Was Very Effective…”, Hearn 2025`{=html} {#hearn-2025-section} **[`Google’s obfuscating VM-based anti-bot system (BotGuard) was very effective…`{=html}](https://news.ycombinator.com/item?id=43764108 "'Google’s obfuscating VM-based anti-bot system (BotGuard) was very effective…', Hearn 2025"){.link-annotated .id-not .include-annotation link-icon="hacker-news" link-icon-type="svg" link-icon-color="#f26522"}** ## `“NeuRaLaTeX: A Machine Learning Library Written in Pure LaTeX”, Gardner et al 2025`{=html} {#gardner-et-al-2025-section} **[`NeuRaLaTeX: A machine learning library written in pure LaTeX`{=html}](https://arxiv.org/abs/2503.24187 "'NeuRaLaTeX: A machine learning library written in pure LaTeX', Gardner et al 2025"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Topological Kleene Field Theories As a Model of Computation”, González-Prieto et al 2025`{=html} {#gonzález-prieto-et-al-2025-section} **[`Topological Kleene Field Theories as a model of computation`{=html}](https://arxiv.org/abs/2503.16100 "'Topological Kleene Field Theories as a model of computation', González-Prieto et al 2025"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“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`{=html} {#ornes-2025-section} **[`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`{=html}](https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/ "'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"){.id-not .include-annotation link-icon="quanta" link-icon-type="svg" link-icon-color="#ff8600"}** ## `“‘Next-Level’ Chaos Traces the True Limit of Predictability”`{=html} {#_MRvQUyxr-section} **[`‘Next-Level’ Chaos Traces the True Limit of Predictability`{=html}](https://www.quantamagazine.org/next-level-chaos-traces-the-true-limit-of-predictability-20250307/ "‘Next-Level’ Chaos Traces the True Limit of Predictability"){.link-annotated-partial .id-not .include-annotation link-icon="quanta" link-icon-type="svg" link-icon-color="#ff8600"}** ## `“Simulating Time With Square-Root Space”, Williams 2025`{=html} {#williams-2025-section} **[`Simulating Time With Square-Root Space`{=html}](https://arxiv.org/abs/2502.17779 "'Simulating Time With Square-Root Space', Williams 2025"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Regex Chess: A 2-Ply Minimax Chess Engine in 84,688 Regular Expressions”, Carlini 2025`{=html} {#carlini-2025-section} **[`Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions`{=html}](https://nicholas.carlini.com/writing/2025/regex-chess.html "'Regex Chess: A 2-ply minimax chess engine in 84,688 regular expressions', Carlini 2025"){.link-annotated-partial .id-not .include-annotation}** ## `“Solving Sudoku With Tmux”`{=html} {#_opXKfyMQ-section} **[`Solving Sudoku with tmux`{=html}](https://willhbr.net/2024/12/27/solving-sudoku-with-tmux/ "Solving Sudoku with tmux"){.link-annotated-partial .id-not .include-annotation}** ## `“Tokenization Is NP-Complete”, Whittington et al 2024`{=html} {#whittington-et-al-2024-section} **[`Tokenization is NP-Complete`{=html}](https://arxiv.org/abs/2412.15210 "'Tokenization is NP-Complete', Whittington et al 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Ask, and It Shall Be Given: Turing Completeness of Prompting”, Qiu et al 2024`{=html} {#qiu-et-al-2024-section} **[`Ask, and it shall be given: Turing completeness of prompting`{=html}](https://arxiv.org/abs/2411.01992 "'Ask, and it shall be given: Turing completeness of prompting', Qiu et al 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“ALTA: Compiler-Based Analysis of Transformers”, Shaw et al 2024`{=html} {#shaw-et-al-2024-section} **[`ALTA: Compiler-Based Analysis of Transformers`{=html}](https://arxiv.org/abs/2410.18077#deepmind "'ALTA: Compiler-Based Analysis of Transformers', Shaw et al 2024"){.link-annotated .id-not .include-annotation link-icon="deepmind" link-icon-type="svg" link-icon-color="#4185f4"}** ## `“Autoregressive Large Language Models Are Computationally Universal”, Schuurmans et al 2024`{=html} {#schuurmans-et-al-2024-section} **[`Autoregressive Large Language Models are Computationally Universal`{=html}](https://arxiv.org/abs/2410.03170#deepmind "'Autoregressive Large Language Models are Computationally Universal', Schuurmans et al 2024"){.link-annotated .id-not .include-annotation link-icon="deepmind" link-icon-type="svg" link-icon-color="#4185f4"}** ## `“Computer Scientists Combine Two ‘Beautiful’ Proof Methods [ZK + PCP]”`{=html} {#_Av9WuJPr-section} **[`Computer Scientists Combine Two ‘Beautiful’ Proof Methods [ZK + PCP]`{=html}](https://www.quantamagazine.org/computer-scientists-combine-two-beautiful-proof-methods-20241004/ "Computer Scientists Combine Two ‘Beautiful’ Proof Methods [ZK + PCP]"){.link-annotated-partial .id-not .include-annotation link-icon="quanta" link-icon-type="svg" link-icon-color="#ff8600"}** ## `“Hypercomputation without Bothering the Cactus People: Software Development for the DMT Headspace”, Flipper 2024`{=html} {#flipper-2024-section} **[`Hypercomputation without bothering the cactus people: Software development for the DMT headspace`{=html}](https://smoothbrains.net/posts/2024-09-26-hypercomputation-without-bothering-the-cactus-people.html "'Hypercomputation without bothering the cactus people: Software development for the DMT headspace', Flipper 2024"){.link-annotated-partial .id-not .include-annotation}** ## `“Tiling With 3 Polygons Is Undecidable”, Demaine & Langerman 2024`{=html} {#demaine-langerman-2024-section} **[`Tiling with 3 Polygons is Undecidable`{=html}](https://arxiv.org/abs/2409.11582 "'Tiling with 3 Polygons is Undecidable', Demaine & Langerman 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Fully Characterizing Lossy Catalytic Computation”, Folkertsma et al 2024`{=html} {#folkertsma-et-al-2024-section} **[`Fully Characterizing Lossy Catalytic Computation`{=html}](https://arxiv.org/abs/2409.05046 "'Fully Characterizing Lossy Catalytic Computation', Folkertsma et al 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“On the Complexity of Neural Computation in Superposition”, Adler & Shavit 2024`{=html} {#adler-shavit-2024-section} **[`On the Complexity of Neural Computation in Superposition`{=html}](https://arxiv.org/abs/2409.15318 "'On the Complexity of Neural Computation in Superposition', Adler & Shavit 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Lossy Catalytic Computation”, Gupta et al 2024`{=html} {#gupta-et-al-2024-lossy-section} **[`Lossy Catalytic Computation`{=html}](https://arxiv.org/abs/2408.14670 "'Lossy Catalytic Computation', Gupta et al 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Quantum Convolutional Neural Networks Are (Effectively) Classically Simulable”, Bermejo et al 2024`{=html} {#bermejo-et-al-2024-section} **[`Quantum Convolutional Neural Networks are (Effectively) Classically Simulable`{=html}](https://arxiv.org/abs/2408.12739 "'Quantum Convolutional Neural Networks are (Effectively) Classically Simulable', Bermejo et al 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Optimization by Decoded Quantum Interferometry”, Jordan et al 2024`{=html} {#jordan-et-al-2024-section} **[`Optimization by Decoded Quantum Interferometry`{=html}](https://arxiv.org/abs/2408.08292 "'Optimization by Decoded Quantum Interferometry', Jordan et al 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Mathematical Models of Computation in Superposition”, Hänni et al 2024`{=html} {#hänni-et-al-2024-section} **[`Mathematical Models of Computation in Superposition`{=html}](https://arxiv.org/abs/2408.05451 "'Mathematical Models of Computation in Superposition', Hänni et al 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Automata Extraction from Transformers”, Zhang et al 2024`{=html} {#zhang-et-al-2024-section} **[`Automata Extraction from Transformers`{=html}](https://arxiv.org/abs/2406.05564 "'Automata Extraction from Transformers', Zhang et al 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“A Programming Language Embedded in Magic: The Gathering”, Yin & Churchill 2024`{=html} {#yin-churchill-2024-section} **[`A Programming Language Embedded in Magic: The Gathering`{=html}](/doc/cs/computable/2024-yin.pdf "'A Programming Language Embedded in Magic: The Gathering', Yin & Churchill 2024"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“The Illusion of State in State-Space Models”, Merrill et al 2024`{=html} {#merrill-et-al-2024-section} **[`The Illusion of State in State-Space Models`{=html}](https://arxiv.org/abs/2404.08819 "'The Illusion of State in State-Space Models', Merrill et al 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Language Generation in the Limit”, Kleinberg & Mullainathan 2024`{=html} {#kleinberg-mullainathan-2024-section} **[`Language Generation in the Limit`{=html}](https://arxiv.org/abs/2404.06757 "'Language Generation in the Limit', Kleinberg & Mullainathan 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Chain-Of-Thought Empowers Transformers to Solve Inherently Serial Problems”, Li et al 2024`{=html} {#li-et-al-2024-09-section} **[`Chain-of-Thought Empowers Transformers to Solve Inherently Serial Problems`{=html}](https://arxiv.org/abs/2402.12875 "'Chain-of-Thought Empowers Transformers to Solve Inherently Serial Problems', Li et al 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Why Are Sensitive Functions Hard for Transformers?”, Hahn & Rofin 2024`{=html} {#hahn-rofin-2024-section} **[`Why are Sensitive Functions Hard for Transformers?`{=html}](https://arxiv.org/abs/2402.09963 "'Why are Sensitive Functions Hard for Transformers?', Hahn & Rofin 2024"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“FBSH: Font With Built-In Syntax Highlighting for Hand-Coded Websites”, Lotvonen 2024`{=html} {#lotvonen-2024-section} **[`FBSH: Font with Built-In Syntax Highlighting for Hand-Coded Websites`{=html}](https://blog.glyphdrawing.club/font-with-built-in-syntax-highlighting/ "'FBSH: Font with Built-In Syntax Highlighting for Hand-Coded Websites', Lotvonen 2024"){.link-annotated-partial .id-not .include-annotation}** ## `“Linux/4004: Slowly Booting Full Linux on the Intel 4004 CPU for Fun, Art, and Absolutely No Profit”, Grinberg 2024`{=html} {#grinberg-2024-section} **[`Linux/4004: Slowly booting full Linux on the Intel 4004 CPU for fun, art, and absolutely no profit`{=html}](https://dmitry.gr/?r=05.Projects&proj=35.%20Linux4004 "'Linux/4004: Slowly booting full Linux on the Intel 4004 CPU for fun, art, and absolutely no profit', Grinberg 2024"){.link-annotated-partial .id-not .include-annotation}** ## `“Can a Transformer Represent a Kalman Filter?”, Goel & Bartlett 2023`{=html} {#goel-bartlett-2023-section} **[`Can a Transformer Represent a Kalman Filter?`{=html}](https://arxiv.org/abs/2312.06937 "'Can a Transformer Represent a Kalman Filter?', Goel & Bartlett 2023"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly the Star-Free Languages”, Angluin et al 2023`{=html} {#angluin-et-al-2023-section} **[`Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly the Star-Free Languages`{=html}](https://arxiv.org/abs/2310.13897 "'Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly the Star-Free Languages', Angluin et al 2023"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“The Expressive Power of Transformers With Chain-Of-Thought”, Merrill & Sabharwal 2023`{=html} {#merrill-sabharwal-2023-section} **[`The Expressive Power of Transformers with Chain-of-Thought`{=html}](https://arxiv.org/abs/2310.07923 "'The Expressive Power of Transformers with Chain-of-Thought', Merrill & Sabharwal 2023"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“How to Build a Computer Using Origami”, Green 2023`{=html} {#green-2023-section} **[`How to build a computer using origami`{=html}](https://apieceofthepi.substack.com/p/how-to-build-a-computer-using-origami "'How to build a computer using origami', Green 2023"){.link-annotated-partial .id-not .include-annotation link-icon="substack" link-icon-type="svg" link-icon-color="#ff6719"}** ## `“Flat Origami Is Turing Complete”, Hull & Zakharevich 2023`{=html} {#hull-zakharevich-2023-section} **[`Flat origami is Turing Complete`{=html}](https://arxiv.org/abs/2309.07932 "'Flat origami is Turing Complete', Hull & Zakharevich 2023"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Learning Transformer Programs”, Friedman et al 2023`{=html} {#friedman-et-al-2023-section} **[`Learning Transformer Programs`{=html}](https://arxiv.org/abs/2306.01128 "'Learning Transformer Programs', Friedman et al 2023"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Universal Mechanical Polycomputation in Granular Matter”, Parsa et al 2023`{=html} {#parsa-et-al-2023-section} **[`Universal Mechanical Polycomputation in Granular Matter`{=html}](https://arxiv.org/abs/2305.17872 "'Universal Mechanical Polycomputation in Granular Matter', Parsa et al 2023"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Towards Revealing the Mystery behind Chain-Of-Thought: A Theoretical Perspective”, Feng et al 2023`{=html} {#feng-et-al-2023-2-section} **[`Towards Revealing the Mystery behind Chain-of-Thought: A Theoretical Perspective`{=html}](https://arxiv.org/abs/2305.15408 "'Towards Revealing the Mystery behind Chain-of-Thought: A Theoretical Perspective', Feng et al 2023"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Neural Oscillators Are Universal”, Lanthaler et al 2023`{=html} {#lanthaler-et-al-2023-section} **[`Neural Oscillators are Universal`{=html}](https://arxiv.org/abs/2305.08753 "'Neural Oscillators are Universal', Lanthaler et al 2023"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Looped Transformers As Programmable Computers”, Giannou et al 2023`{=html} {#giannou-et-al-2023-section} **[`Looped Transformers as Programmable Computers`{=html}](https://arxiv.org/abs/2301.13196 "'Looped Transformers as Programmable Computers', Giannou et al 2023"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Tighter Bounds on the Expressivity of Transformer Encoders”, Chiang et al 2023`{=html} {#chiang-et-al-2023-2-section} **[`Tighter Bounds on the Expressivity of Transformer Encoders`{=html}](https://arxiv.org/abs/2301.10743 "'Tighter Bounds on the Expressivity of Transformer Encoders', Chiang et al 2023"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Memory Augmented Large Language Models Are Computationally Universal”, Schuurmans 2023`{=html} {#schuurmans-2023-section} **[`Memory Augmented Large Language Models are Computationally Universal`{=html}](https://arxiv.org/abs/2301.04589#google "'Memory Augmented Large Language Models are Computationally Universal', Schuurmans 2023"){.link-annotated .id-not .include-annotation link-icon="alphabet" link-icon-type="svg" link-icon-color="#4285f4"}** ## `“Control of Cell Proliferation by Memories of Mitosis”, Meitinger et al 2022`{=html} {#meitinger-et-al-2022-section} **[`Control of cell proliferation by memories of mitosis`{=html}](https://www.biorxiv.org/content/10.1101/2022.11.14.515741.full "'Control of cell proliferation by memories of mitosis', Meitinger et al 2022"){.link-annotated .id-not .include-annotation link-icon="chi-dna" link-icon-type="svg" link-icon-color="#bd2736"}** ## `“Characterizing Intrinsic Compositionality in Transformers With Tree Projections”, Murty et al 2022`{=html} {#murty-et-al-2022-section} **[`Characterizing Intrinsic Compositionality in Transformers with Tree Projections`{=html}](https://arxiv.org/abs/2211.01288 "'Characterizing Intrinsic Compositionality in Transformers with Tree Projections', Murty et al 2022"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Transformers Learn Shortcuts to Automata”, Liu et al 2022`{=html} {#liu-et-al-2022-section} **[`Transformers Learn Shortcuts to Automata`{=html}](https://arxiv.org/abs/2210.10749#microsoft "'Transformers Learn Shortcuts to Automata', Liu et al 2022"){.link-annotated .id-not .include-annotation link-icon="MS" link-icon-type="text,sans,italic"}** ## `“Transformers Implement First-Order Logic With Majority Quantifiers”, Merrill & Sabharwal 2022`{=html} {#merrill-sabharwal-2022-1-section} **[`Transformers Implement First-Order Logic with Majority Quantifiers`{=html}](https://arxiv.org/abs/2210.02671 "'Transformers Implement First-Order Logic with Majority Quantifiers', Merrill & Sabharwal 2022"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Python Type Hints Are Turing Complete”, Roth 2022`{=html} {#roth-2022-section} **[`Python Type Hints are Turing Complete`{=html}](https://arxiv.org/abs/2208.14755 "'Python Type Hints are Turing Complete', Roth 2022"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“What Can Transformers Learn In-Context? A Case Study of Simple Function Classes”, Garg et al 2022`{=html} {#garg-et-al-2022-section} **[`What Can Transformers Learn In-Context? A Case Study of Simple Function Classes`{=html}](https://arxiv.org/abs/2208.01066 "'What Can Transformers Learn In-Context? A Case Study of Simple Function Classes', Garg et al 2022"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Perceptein: A Synthetic Protein-Level Neural Network in Mammalian Cells”, Chen et al 2022`{=html} {#chen-et-al-2022-02-section} **[`Perceptein: A synthetic protein-level neural network in mammalian cells`{=html}](https://www.biorxiv.org/content/10.1101/2022.07.10.499405.full "'Perceptein: A synthetic protein-level neural network in mammalian cells', Chen et al 2022"){.link-annotated .id-not .include-annotation link-icon="chi-dna" link-icon-type="svg" link-icon-color="#bd2736"}** ## `“Neural Networks and the Chomsky Hierarchy”, Delétang et al 2022`{=html} {#delétang-et-al-2022-section} **[`Neural Networks and the Chomsky Hierarchy`{=html}](https://arxiv.org/abs/2207.02098#deepmind "'Neural Networks and the Chomsky Hierarchy', Delétang et al 2022"){.link-annotated .id-not .include-annotation link-icon="deepmind" link-icon-type="svg" link-icon-color="#4185f4"}** ## `“Log-Precision Transformers Are Constant-Depth Uniform Threshold Circuits”, Merrill & Sabharwal 2022`{=html} {#merrill-sabharwal-2022-2-section} **[`Log-Precision Transformers are Constant-Depth Uniform Threshold Circuits`{=html}](https://arxiv.org/abs/2207.00729 "'Log-Precision Transformers are Constant-Depth Uniform Threshold Circuits', Merrill & Sabharwal 2022"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Verifiable Quantum Advantage without Structure”, Yamakawa & Zhandry 2022`{=html} {#yamakawa-zhandry-2022-section} **[`Verifiable Quantum Advantage without Structure`{=html}](https://arxiv.org/abs/2204.02063 "'Verifiable Quantum Advantage without Structure', Yamakawa & Zhandry 2022"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“An RNA-Based Theory of Natural Universal Computation”, Akhlaghpour 2022`{=html} {#akhlaghpour-2022-section} **[`An RNA-based theory of natural universal computation`{=html}](/doc/cs/computable/2022-akhlaghpour.pdf "'An RNA-based theory of natural universal computation', Akhlaghpour 2022"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Overcoming a Theoretical Limitation of Self-Attention”, Chiang & Cholak 2022`{=html} {#chiang-cholak-2022-section} **[`Overcoming a Theoretical Limitation of Self-Attention`{=html}](https://arxiv.org/abs/2202.12172 "'Overcoming a Theoretical Limitation of Self-Attention', Chiang & Cholak 2022"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“A Deep Dive into an NSO Zero-Click IMessage Exploit: Remote Code Execution”, Beer & Groß 2021`{=html} {#beer-groß-2021-section} **[`A deep dive into an NSO zero-click iMessage exploit: Remote Code Execution`{=html}](https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-into-nso-zero-click.html "'A deep dive into an NSO zero-click iMessage exploit: Remote Code Execution', Beer & Groß 2021"){.link-annotated .id-not .include-annotation link-icon="alphabet" link-icon-type="svg" link-icon-color="#4285f4"}** ## `“Quantum Advantage in Learning from Experiments”, Huang et al 2021`{=html} {#huang-et-al-2021-2-section} **[`Quantum advantage in learning from experiments`{=html}](https://arxiv.org/abs/2112.00778#google "'Quantum advantage in learning from experiments', Huang et al 2021"){.link-annotated .id-not .include-annotation link-icon="alphabet" link-icon-type="svg" link-icon-color="#4285f4"}** ## `“Minimum Description Length Recurrent Neural Networks”, Lan et al 2021`{=html} {#lan-et-al-2021-1-section} **[`Minimum Description Length Recurrent Neural Networks`{=html}](https://arxiv.org/abs/2111.00600 "'Minimum Description Length Recurrent Neural Networks', Lan et al 2021"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“JPEG XL Would Be Turing-Complete”, Bohdan 2021`{=html} {#bohdan-2021-section} **[`JPEG XL would be Turing-complete`{=html}](https://dbohdan.com/jpeg-xl "'JPEG XL would be Turing-complete', Bohdan 2021"){.link-annotated-partial .id-not .include-annotation}** ## `“RASP: Thinking Like Transformers”, Weiss et al 2021`{=html} {#weiss-et-al-2021-section} **[`RASP: Thinking Like Transformers`{=html}](https://arxiv.org/abs/2106.06981 "'RASP: Thinking Like Transformers', Weiss et al 2021"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Turing Completeness and Sid Meier’s Civilization”, Wynter 2021`{=html} {#wynter-2021-section} **[`Turing Completeness and Sid Meier’s Civilization`{=html}](https://arxiv.org/abs/2104.14647 "'Turing Completeness and Sid Meier’s Civilization', Wynter 2021"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine”, Johnson 2021`{=html} {#johnson-2021-section} **[`Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine`{=html}](https://arxiv.org/abs/2105.02124 "'Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine', Johnson 2021"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Sensitivity As a Complexity Measure for Sequence Classification Tasks”, Hahn et al 2021`{=html} {#hahn-et-al-2021-2-section} **[`Sensitivity as a Complexity Measure for Sequence Classification Tasks`{=html}](https://arxiv.org/abs/2104.10343 "'Sensitivity as a Complexity Measure for Sequence Classification Tasks', Hahn et al 2021"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Gene Regulatory Networks Exhibit Several Kinds of Memory: Quantification of Memory in Biological and Random Transcriptional Networks”, Biswas et al 2021`{=html} {#biswas-et-al-2021-section} **[`Gene regulatory networks exhibit several kinds of memory: quantification of memory in biological and random transcriptional networks`{=html}](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7970124/ "'Gene regulatory networks exhibit several kinds of memory: quantification of memory in biological and random transcriptional networks', Biswas et al 2021"){.link-annotated .id-not .include-annotation link-icon="nlm-ncbi" link-icon-type="svg" link-icon-color="#20558a"}** ## `“Constructing Turing Complete Euler Flows in Dimension 3”, Cardona et al 2020`{=html} {#cardona-et-al-2020-section} **[`Constructing Turing complete Euler flows in dimension 3`{=html}](https://arxiv.org/abs/2012.12828 "'Constructing Turing complete Euler flows in dimension 3', Cardona et al 2020"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“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`{=html} {#pavlus-2020-section} **[`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`{=html}](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', Pavlus 2020"){.link-annotated .id-not .include-annotation link-icon="quanta" link-icon-type="svg" link-icon-color="#ff8600"}** ## `“"Less Than One"-Shot Learning: Learning n Classes From M < N Samples”, Sucholutsky & Schonlau 2020`{=html} {#sucholutsky-schonlau-2020-section} **[`"Less Than One"-Shot Learning: Learning n Classes From M < N Samples`{=html}](https://arxiv.org/abs/2009.08449 "'"Less Than One"-Shot Learning: Learning n Classes From M < N Samples', Sucholutsky & Schonlau 2020"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Catalytic Approaches to the Tree Evaluation Problem”, Cook & Mertz 2020`{=html} {#cook-mertz-2020-section} **[`Catalytic Approaches to the Tree Evaluation Problem`{=html}](/doc/cs/computable/2020-cook.pdf "'Catalytic Approaches to the Tree Evaluation Problem', Cook & Mertz 2020"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Remembering John Conway’s FRACTRAN, a Ridiculous, yet Surprisingly Deep Language”, Braithwaite 2020`{=html} {#braithwaite-2020-section} **[`Remembering John Conway’s FRACTRAN, a ridiculous, yet surprisingly deep language`{=html}](https://raganwald.com/2020/05/03/fractran.html "'Remembering John Conway’s FRACTRAN, a ridiculous, yet surprisingly deep language', Braithwaite 2020"){.link-annotated .id-not .include-annotation}** ## `“Magic: the Gathering Is As Hard As Arithmetic”, Biderman 2020`{=html} {#biderman-2020-section} **[`Magic: the Gathering is as Hard as Arithmetic`{=html}](https://arxiv.org/abs/2003.05119 "'Magic: the Gathering is as Hard as Arithmetic', Biderman 2020"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Recursed Is Not Recursive: A Jarring Result”, Demaine et al 2020`{=html} {#demaine-et-al-2020-section} **[`Recursed is not Recursive: A Jarring Result`{=html}](https://arxiv.org/abs/2002.05131 "'Recursed is not Recursive: A Jarring Result', Demaine et al 2020"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Are Transformers Universal Approximators of Sequence-To-Sequence Functions?”, Yun et al 2019`{=html} {#yun-et-al-2019-section} **[`Are Transformers universal approximators of sequence-to-sequence functions?`{=html}](https://arxiv.org/abs/1912.10077 "'Are Transformers universal approximators of sequence-to-sequence functions?', Yun et al 2019"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“The Busy Beaver Frontier”, Aaronson 2019`{=html} {#aaronson-2019-section} **[`The Busy Beaver Frontier`{=html}](/doc/cs/computable/2019-aaronson.pdf "'The Busy Beaver Frontier', Aaronson 2019"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Universal Approximation With Deep Narrow Networks”, Kidger & Lyons 2019`{=html} {#kidger-lyons-2019-section} **[`Universal Approximation with Deep Narrow Networks`{=html}](https://arxiv.org/abs/1905.08539 "'Universal Approximation with Deep Narrow Networks', Kidger & Lyons 2019"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Magic: The Gathering Is Turing Complete”, Churchill et al 2019`{=html} {#churchill-et-al-2019-section} **[`Magic: The Gathering is Turing Complete`{=html}](https://arxiv.org/abs/1904.09828 "'Magic: The Gathering is Turing Complete', Churchill et al 2019"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“On the Turing Completeness of Modern Neural Network Architectures”, Pérez et al 2019`{=html} {#pérez-et-al-2019-section} **[`On the Turing Completeness of Modern Neural Network Architectures`{=html}](https://arxiv.org/abs/1901.03429 "'On the Turing Completeness of Modern Neural Network Architectures', Pérez et al 2019"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Mismorphism: The Heart of the Weird Machine”, Anantharaman et al 2019`{=html} {#anantharaman-et-al-2019-section} **[`Mismorphism: The Heart of the Weird Machine`{=html}](/doc/cs/security/2019-anantharaman.pdf "'Mismorphism: The Heart of the Weird Machine', Anantharaman et al 2019"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Deciphering the Molecular Mechanism Underpinning Phage Arbitrium Communication Systems”, Sol et al 2019`{=html} {#sol-et-al-2019-section} **[`Deciphering the Molecular Mechanism Underpinning Phage Arbitrium Communication Systems`{=html}](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6458997/ "'Deciphering the Molecular Mechanism Underpinning Phage Arbitrium Communication Systems', Sol et al 2019"){.link-annotated .id-not .include-annotation link-icon="nlm-ncbi" link-icon-type="svg" link-icon-color="#20558a"}** ## `“Mechanical Computing: The Computational Complexity of Physical Devices”, Reif 2018`{=html} {#reif-2018-section} **[`Mechanical Computing: The Computational Complexity of Physical Devices`{=html}](/doc/cs/computable/2018-reif.pdf "'Mechanical Computing: The Computational Complexity of Physical Devices', Reif 2018"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Adversarial Reprogramming of Neural Networks”, Elsayed et al 2018`{=html} {#elsayed-et-al-2018-adversarial-reprogramming-section} **[`Adversarial Reprogramming of Neural Networks`{=html}](https://arxiv.org/abs/1806.11146 "'Adversarial Reprogramming of Neural Networks', Elsayed et al 2018"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Mechanical Computing System Using Only One Physical Object-qb Cube”, Vučinović 2018`{=html} {#vučinović-2018-section} **[`Mechanical Computing System Using Only One Physical Object-qb cube`{=html}](/doc/cs/computable/2018-vucinovic.pdf "'Mechanical Computing System Using Only One Physical Object-qb cube', Vučinović 2018"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Go Experience Report: Generics in Kubernetes”, Schlesinger 2017`{=html} {#schlesinger-2017-section} **[`Go Experience Report: Generics in Kubernetes`{=html}](https://medium.com/@arschles/go-experience-report-generics-in-kubernetes-25da87430301 "'Go Experience Report: Generics in Kubernetes', Schlesinger 2017"){.link-annotated-partial .id-not .include-annotation link-icon="𝐌" link-icon-type="text"}** ## `“Weird Machines, Exploitability, and Provable Unexploitability”, Dullien 2017`{=html} {#dullien-2017-section} **[`Weird machines, exploitability, and provable unexploitability`{=html}](https://www.semanticscholar.org/paper/Weird-Machines%2C-Exploitability%2C-and-Provable-Dullien/758d648a1a7767a46d0901f3b8e1b65413275d29?pdf "'Weird machines, exploitability, and provable unexploitability', Dullien 2017"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“On the Glitch Phenomenon”, Lamport & Palais 2017`{=html} {#lamport-palais-2017-section} **[`On the Glitch Phenomenon`{=html}](https://arxiv.org/abs/1704.01154 "'On the Glitch Phenomenon', Lamport & Palais 2017"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Communication between Viruses Guides Lysis-Lysogeny Decisions”, Erez et al 2017`{=html} {#erez-et-al-2017-section} **[`Communication between viruses guides lysis-lysogeny decisions`{=html}](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5378303/ "'Communication between viruses guides lysis-lysogeny decisions', Erez et al 2017"){.link-annotated .id-not .include-annotation link-icon="nlm-ncbi" link-icon-type="svg" link-icon-color="#20558a"}** ## `“[0day Exploit] Compromising a Linux Desktop Using... 6502 Processor Opcodes on the NES‽”`{=html} {#_aBHu-Dq5-section} **[`[0day exploit] Compromising a Linux desktop using... 6502 processor opcodes on the NES‽`{=html}](https://scarybeastsecurity.blogspot.com/2016/11/0day-exploit-compromising-linux-desktop.html "[0day exploit] Compromising a Linux desktop using... 6502 processor opcodes on the NES‽"){.link-annotated-partial .id-not .include-annotation}** ## `“Why Does Deep and Cheap Learning Work so Well?”, Lin et al 2016`{=html} {#lin-et-al-2016-2-section} **[`Why does deep and cheap learning work so well?`{=html}](https://arxiv.org/abs/1608.08225 "'Why does deep and cheap learning work so well?', Lin et al 2016"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Java Generics Are Turing Complete”, Grigore 2016`{=html} {#grigore-2016-section} **[`Java Generics are Turing Complete`{=html}](https://arxiv.org/abs/1605.05274 "'Java Generics are Turing Complete', Grigore 2016"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory”, Yedidia & Aaronson 2016`{=html} {#yedidia-aaronson-2016-section} **[`A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory`{=html}](https://arxiv.org/abs/1605.04343 "'A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory', Yedidia & Aaronson 2016"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Open Games: Compositional Game Theory”, Ghani et al 2016`{=html} {#ghani-et-al-2016-section} **[`Open Games: Compositional game theory`{=html}](https://arxiv.org/abs/1603.04641 "'Open Games: Compositional game theory', Ghani et al 2016"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `Advances in Physarum Machines: Sensing and Computing With Slime Mould, Adamatzky 2016`{=html} {#adamatzky-2016-section} **[`Advances in Physarum Machines: Sensing and Computing with Slime Mould`{=html}](/doc/cs/computable/2016-adamatzky-advancesinphysarummachines.pdf "'Advances in Physarum Machines: Sensing and Computing with Slime Mould', Adamatzky 2016"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“On Having No Head: Cognition throughout Biological Systems”, Baluška & Levin 2016`{=html} {#baluška-levin-2016-section} **[`On Having No Head: Cognition throughout Biological Systems`{=html}](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4914563/ "'On Having No Head: Cognition throughout Biological Systems', Baluška & Levin 2016"){.link-annotated .id-not .include-annotation link-icon="nlm-ncbi" link-icon-type="svg" link-icon-color="#20558a"}** ## `“We Need Less Powerful Languages [Langsec]”, Plant 2015`{=html} {#plant-2015-section} **[`We need less powerful languages [langsec]`{=html}](https://lukeplant.me.uk/blog/posts/less-powerful-languages/ "'We need less powerful languages [langsec]', Plant 2015"){.link-annotated-partial .id-not .include-annotation}** ## `“Undecidability of the Spectral Gap”, Cubitt et al 2015`{=html} {#cubitt-et-al-2015-section} **[`Undecidability of the Spectral Gap`{=html}](https://arxiv.org/abs/1502.04573 "'Undecidability of the Spectral Gap', Cubitt et al 2015"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“What Are Weird Machines?”, Bratus 2015`{=html} {#bratus-2015-section} **[`What are Weird Machines?`{=html}](https://www.cs.dartmouth.edu/~sergey/wm/ "'What are Weird Machines?', Bratus 2015"){.link-annotated .id-not .include-annotation}** ## `“Braid Is Undecidable”, Hamilton 2014`{=html} {#hamilton-2014-section} **[`Braid is undecidable`{=html}](https://arxiv.org/abs/1412.0784 "'Braid is undecidable', Hamilton 2014"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Computing With a Full Memory: Catalytic Space”, Buhrman et al 2014`{=html} {#buhrman-et-al-2014-section} **[`Computing with a Full Memory: Catalytic Space`{=html}](/doc/cs/computable/2014-buhrman.pdf "'Computing with a Full Memory: Catalytic Space', Buhrman et al 2014"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Implementing a Web Server in a Single printf() Call”`{=html} {#_rKBsB5AD-section} **[`Implementing a web server in a single printf() call`{=html}](https://tinyhack.com/2014/03/12/implementing-a-web-server-in-a-single-printf-call/ "Implementing a web server in a single printf() call"){.link-annotated-partial .id-not .include-annotation}** ## `“Teaching Mario to Play Pong and Snake Through Innumerable Exploits”`{=html} {#_QuCyjhyS-section} **[`Teaching Mario to Play Pong and Snake Through Innumerable Exploits`{=html}](https://hackaday.com/2014/01/10/teaching-mario-to-play-pong-and-snake-through-innumerable-exploits/ "Teaching Mario to Play Pong and Snake Through Innumerable Exploits"){.id-not .include-annotation}** ## `“On the Complexity of Random Satisfiability Problems With Planted Solutions”, Feldman et al 2013`{=html} {#feldman-et-al-2013-section} **[`On the Complexity of Random Satisfiability Problems with Planted Solutions`{=html}](https://arxiv.org/abs/1311.4821 "'On the Complexity of Random Satisfiability Problems with Planted Solutions', Feldman et al 2013"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Converting Untrusted PDFs into Trusted Ones: The Qubes Way”`{=html} {#_eIE2EGi3-section} **[`Converting untrusted PDFs into trusted ones: The Qubes Way`{=html}](https://blog.invisiblethings.org/2013/02/21/converting-untrusted-pdfs-into-trusted.html "Converting untrusted PDFs into trusted ones: The Qubes Way"){.link-annotated-partial .id-not .include-annotation}** ## `“Mathematics in the Age of the Turing Machine”, Hales 2013`{=html} {#hales-2013-section} **[`Mathematics in the Age of the Turing Machine`{=html}](https://arxiv.org/abs/1302.2898 "'Mathematics in the Age of the Turing Machine', Hales 2013"){.link-annotated-partial .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“On Unsettleable Arithmetical Problems”, Conway 2013`{=html} {#conway-2013-section} **[`On Unsettleable Arithmetical Problems`{=html}](/doc/cs/computable/2013-conway.pdf "'On Unsettleable Arithmetical Problems', Conway 2013"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“The Page-Fault Weird Machine: Lessons in Instruction-Less Computation”, Bangert 2013`{=html} {#bangert-2013-section} **[`The Page-Fault Weird Machine: Lessons in Instruction-less Computation`{=html}](http://0b4af6cdc2f0c5998459-c0245c5c937c5dedcca3f1764ecc9b2f.r43.cf2.rackcdn.com/12061-woot13-bangert.pdf "'The Page-Fault Weird Machine: Lessons in Instruction-less Computation', Bangert 2013"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Using Routers to Build Logic Circuits: How Powerful Is BGP?”, Chiesa 2013`{=html} {#chiesa-2013-section} **[`Using routers to build logic circuits: How powerful is BGP?`{=html}](https://inl.info.ucl.ac.be/system/files/main_2.pdf "'Using routers to build logic circuits: How powerful is BGP?', Chiesa 2013"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Is the Network Turing-Complete? EPFL Technical Report 187131”, Peresini & Kostic 2013`{=html} {#peresini-kostic-2013-section} **[`Is the Network Turing-Complete? EPFL Technical Report 187131`{=html}](https://pdfs.semanticscholar.org/3069/80183fea8f0e6af98f520d8c8968f11c8eb1.pdf "'Is the Network Turing-Complete? EPFL Technical Report 187131', Peresini & Kostic 2013"){.id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}[  :]{.mobile-not}** ::: aux-links-transclude-file ::: collapse **View PDF**: [`https://pdfs.semanticscholar.org/3069/80183fea8f0e6af98f520d8c8968f11c8eb1.pdf`](https://pdfs.semanticscholar.org/3069/80183fea8f0e6af98f520d8c8968f11c8eb1.pdf){.id-not .link-annotated-not .include-content .include-lazy link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"} ::: ::: ## `“Turning Oscillations into Opportunities: Lessons from a Bacterial Decision Gate”, Schultz et al 2013`{=html} {#schultz-et-al-2013-section} **[`Turning oscillations into opportunities: lessons from a bacterial decision gate`{=html}](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3627974/ "'Turning oscillations into opportunities: lessons from a bacterial decision gate', Schultz et al 2013"){.link-annotated .id-not .include-annotation link-icon="nlm-ncbi" link-icon-type="svg" link-icon-color="#20558a"}** ## `“The Configuration Complexity Clock”, Hadlow 2012`{=html} {#hadlow-2012-section} **[`The Configuration Complexity Clock`{=html}](https://mikehadlow.blogspot.com/2012/05/configuration-complexity-clock.html "'The Configuration Complexity Clock', Hadlow 2012"){.link-annotated-partial .id-not .include-annotation}** ## `“Buridan’s Principle”, Lamport 2012`{=html} {#lamport-2012-section} **[`Buridan’s Principle`{=html}](/doc/cs/computable/2012-lamport.pdf "'Buridan’s Principle', Lamport 2012"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Robust Soldier Crab Ball Gate”, Gunji et al 2012`{=html} {#gunji-et-al-2012-section} **[`Robust Soldier Crab Ball Gate`{=html}](https://arxiv.org/abs/1204.1749 "'Robust Soldier Crab Ball Gate', Gunji et al 2012"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Buridan’s Principle [Publication Problems Delaying 1984 → 2012]”, Lamport 2012`{=html} {#lamport-2012-section} **[`Buridan’s Principle [publication problems delaying 1984 → 2012]`{=html}](https://www.microsoft.com/en-us/research/publication/buridans-principle/ "'Buridan’s Principle [publication problems delaying 1984 → 2012]', Lamport 2012"){.link-annotated-partial .id-not .include-annotation link-icon="MS" link-icon-type="text,sans,italic"}** ## `“Exploitation and State Machines: Programming the ‘Weird Machine’ Revisited”, Flake 2011`{=html} {#flake-2011-section} **[`Exploitation and State Machines: Programming the ‘Weird Machine’ Revisited`{=html}](/doc/cs/security/2011-dullien.pdf "'Exploitation and State Machines: Programming the ‘Weird Machine’ Revisited', Flake 2011"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Quantum Computation With Devices Whose Contents Are Never Read”, Yakaryilmaz et al 2010`{=html} {#yakaryilmaz-et-al-2010-section} **[`Quantum computation with devices whose contents are never read`{=html}](https://arxiv.org/abs/1011.1201 "'Quantum computation with devices whose contents are never read', Yakaryilmaz et al 2010"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Ant-Based Computing”, Michael 2009`{=html} {#michael-2009-section} **[`Ant-Based Computing`{=html}](/doc/cs/computable/2009-michael.pdf "'Ant-Based Computing', Michael 2009"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Physics, Topology, Logic and Computation: A Rosetta Stone”, Baez & Stay 2009`{=html} {#baez-stay-2009-section} **[`Physics, Topology, Logic and Computation: A Rosetta Stone`{=html}](https://arxiv.org/abs/0903.0340 "'Physics, Topology, Logic and Computation: A Rosetta Stone', Baez & Stay 2009"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“High Performance SQL With PostgreSQL 8.4: Lists and Recursion and Trees, Oh My!”, Fetter 2009`{=html} {#fetter-2009-section} **[`High Performance SQL with PostgreSQL 8.4: Lists and Recursion and Trees, Oh My!`{=html}](https://cdn.oreillystatic.com/en/assets/1/event/27/High%20Performance%20SQL%20with%20PostgreSQL%20Presentation.pdf "'High Performance SQL with PostgreSQL 8.4: Lists and Recursion and Trees, Oh My!', Fetter 2009"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Deciding Fate in Adverse Times: Sporulation and Competence in Bacillus Subtilis”, Schultz et al 2009`{=html} {#schultz-et-al-2009-section} **[`Deciding fate in adverse times: sporulation and competence in Bacillus subtilis`{=html}](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2795487/ "'Deciding fate in adverse times: sporulation and competence in Bacillus subtilis', Schultz et al 2009"){.link-annotated .id-not .include-annotation link-icon="nlm-ncbi" link-icon-type="svg" link-icon-color="#20558a"}** ## `“Small Universal Turing Machines”, Neary 2008`{=html} {#neary-2008-section} **[`Small universal Turing machines`{=html}](/doc/cs/computable/2008-neary.pdf "'Small universal Turing machines', Neary 2008"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Closed Timelike Curves Make Quantum and Classical Computing Equivalent”, Aaronson & Watrous 2008`{=html} {#aaronson-watrous-2008-section} **[`Closed Timelike Curves Make Quantum and Classical Computing Equivalent`{=html}](https://arxiv.org/abs/0808.2669 "'Closed Timelike Curves Make Quantum and Classical Computing Equivalent', Aaronson & Watrous 2008"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Omega Monad: Enumerating a Context-Free Language”, Palmer 2008`{=html} {#palmer-2008-section} **[`Omega Monad: Enumerating a context-free language`{=html}](/doc/cs/haskell/2008-05-02-lukepalmer-omegamonadenumeratingacontextfreelanguage.html "'Omega Monad: Enumerating a context-free language', Palmer 2008"){.link-annotated-partial .id-not .include-annotation link-icon="internet-archive" link-icon-type="svg"}** ## `“Perl Cannot Be Parsed: A Formal Proof”, Kegler 2008`{=html} {#kegler-2008-section} **[`Perl Cannot Be Parsed: A Formal Proof`{=html}](https://perlmonks.org/?node_id=663393 "'Perl Cannot Be Parsed: A Formal Proof', Kegler 2008"){.link-annotated-partial .id-not .include-annotation}** ## `“Algorithmic Self-Assembly of DNA”, Winfree 2008`{=html} {#winfree-2008-section} **[`Algorithmic self-assembly of DNA`{=html}](https://www.dna.caltech.edu/Papers/winfree_thesis.pdf "'Algorithmic self-assembly of DNA', Winfree 2008"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“On Universal Prediction and Bayesian Confirmation”, Hutter 2007`{=html} {#hutter-2007-section} **[`On Universal Prediction and Bayesian Confirmation`{=html}](https://arxiv.org/abs/0709.1516 "'On Universal Prediction and Bayesian Confirmation', Hutter 2007"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Infinite Sets That Admit Fast Exhaustive Search”, Escardo 2007`{=html} {#escardo-2007-section} **[`Infinite sets that admit fast exhaustive search`{=html}](/doc/cs/haskell/2007-escardo.pdf "'Infinite sets that admit fast exhaustive search', Escardo 2007"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Can Newtonian Systems, Bounded in Space, Time, Mass and Energy Compute All Functions?”, Beggs & Tucker 2007`{=html} {#beggs-tucker-2007-section} **[`Can Newtonian systems, bounded in space, time, mass and energy compute all functions?`{=html}](/doc/cs/computable/2007-beggs.pdf "'Can Newtonian systems, bounded in space, time, mass and energy compute all functions?', Beggs & Tucker 2007"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Infinite Versions of Minesweeper Are Turing Complete”, Kate 2007`{=html} {#kate-2007-section} **[`Infinite versions of minesweeper are Turing complete`{=html}](https://web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf "'Infinite versions of minesweeper are Turing complete', Kate 2007"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“On the Computational Power of Threshold Circuits With Sparse Activity”, Uchizawa et al 2006`{=html} {#uchizawa-et-al-2006-section} **[`On the Computational Power of Threshold Circuits with Sparse Activity`{=html}](/doc/ai/nn/sparsity/2006-uchizawa.pdf "'On the Computational Power of Threshold Circuits with Sparse Activity', Uchizawa et al 2006"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“No Quantum Advantage for Nonlocal Computation”, Linden et al 2006`{=html} {#linden-et-al-2006-section} **[`No quantum advantage for nonlocal computation`{=html}](https://arxiv.org/abs/quant-ph/0610097 "'No quantum advantage for nonlocal computation', Linden et al 2006"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Static Typing for a Faulty Lambda Calculus”, Walker et al 2006`{=html} {#walker-et-al-2006-section} **[`Static typing for a faulty lambda calculus`{=html}](/doc/cs/computable/2006-walker.pdf "'Static typing for a faulty lambda calculus', Walker et al 2006"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Is There an Elegant Universal Theory of Prediction?”, Legg 2006`{=html} {#legg-2006-section} **[`Is there an Elegant Universal Theory of Prediction?`{=html}](https://arxiv.org/abs/cs/0606070 "'Is there an Elegant Universal Theory of Prediction?', Legg 2006"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `Good and Real: Demystifying Paradoxes from Physics to Ethics, Drescher 2006`{=html} {#drescher-2006-section} **[`Good and Real: Demystifying Paradoxes from Physics to Ethics`{=html}](/doc/statistics/decision/2006-drescher-goodandreal.pdf "'Good and Real: Demystifying Paradoxes from Physics to Ethics', Drescher 2006"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“A Box, Darkly: Obfuscation, Weird Languages, and Code Esthetics”, Mateas & Montfort 2005`{=html} {#mateas-montfort-2005-section} **[`A Box, Darkly: Obfuscation, Weird Languages, and Code esthetics`{=html}](/doc/cs/computable/2005-mateas.pdf "'A Box, Darkly: Obfuscation, Weird Languages, and Code esthetics', Mateas & Montfort 2005"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“The Halting Problem Is Decidable on a Set of Asymptotic Probability One”, Hamkins & Miasnikov 2005`{=html} {#hamkins-miasnikov-2005-section} **[`The halting problem is decidable on a set of asymptotic probability one`{=html}](https://arxiv.org/abs/math/0504351 "'The halting problem is decidable on a set of asymptotic probability one', Hamkins & Miasnikov 2005"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“A Theory of Quantum Gravity Based on Quantum Computation”, Lloyd 2005`{=html} {#lloyd-2005-section} **[`A theory of quantum gravity based on quantum computation`{=html}](https://arxiv.org/abs/quant-ph/0501135 "'A theory of quantum gravity based on quantum computation', Lloyd 2005"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“A Simple Proof for the Turing-Completeness of XSLT and XQuery”, Kepser 2004`{=html} {#kepser-2004-section} **[`A Simple Proof for the Turing-Completeness of XSLT and XQuery`{=html}](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.8846&rep=rep1&type=pdf "'A Simple Proof for the Turing-Completeness of XSLT and XQuery', Kepser 2004"){.id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Gödel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements”, Schmidhuber 2003`{=html} {#schmidhuber-2003-section} **[`Gödel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements`{=html}](https://arxiv.org/abs/cs/0309048 "'Gödel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements', Schmidhuber 2003"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Philosophical Problems in Logic § Ultrafinitism”, Friedman 2002 (page 4)`{=html} {#friedman-2002-page-4-section} **[`Philosophical Problems in Logic § Ultrafinitism`{=html}](/doc/math/2002-friedman.pdf#page=4 "'Philosophical Problems in Logic § Ultrafinitism', Friedman 2002 (page 4)"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Analytic and Algorithmic Solution of Random Satisfiability Problems”, Mezard et al 2002`{=html} {#mezard-et-al-2002-section} **[`Analytic and Algorithmic Solution of Random Satisfiability Problems`{=html}](/doc/cs/computable/2002-mezard.pdf "'Analytic and Algorithmic Solution of Random Satisfiability Problems', Mezard et al 2002"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“The Fastest and Shortest Algorithm for All Well-Defined Problems”, Hutter 2002`{=html} {#hutter-2002-section} **[`The Fastest and Shortest Algorithm for All Well-Defined Problems`{=html}](https://arxiv.org/abs/cs/0206022 "'The Fastest and Shortest Algorithm for All Well-Defined Problems', Hutter 2002"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Forbidden Information”, Levin 2002`{=html} {#levin-2002-section} **[`Forbidden Information`{=html}](https://arxiv.org/abs/cs/0203029 "'Forbidden Information', Levin 2002"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“Sendmail As a Turing Machine”, Kiselyov 2000`{=html} {#kiselyov-2000-section} **[`Sendmail as a Turing machine`{=html}](https://okmij.org/ftp/Computation/sendmail-as-turing-machine.txt "'Sendmail as a Turing machine', Kiselyov 2000"){.id-not .include-annotation link-icon="txt" link-icon-type="svg"}** ::: aux-links-transclude-file ::: collapse **View text**: [`https://okmij.org/ftp/Computation/sendmail-as-turing-machine.txt`](https://okmij.org/ftp/Computation/sendmail-as-turing-machine.txt){.id-not .link-annotated-not .include-content .include-lazy link-icon="txt" link-icon-type="svg"} ::: ::: ## `“Counterfactual Computation”, Mitchison & Jozsa 1999`{=html} {#mitchison-jozsa-1999-section} **[`Counterfactual Computation`{=html}](https://arxiv.org/abs/quant-ph/9907007 "'Counterfactual Computation', Mitchison & Jozsa 1999"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“P/NP, and the Quantum Field Computer”, Freedman 1998`{=html} {#freedman-1998-section} **[`P/NP, and the quantum field computer`{=html}](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC18139/ "'P/NP, and the quantum field computer', Freedman 1998"){.link-annotated .id-not .include-annotation link-icon="nlm-ncbi" link-icon-type="svg" link-icon-color="#20558a"}** ## `“Limitations of Noisy Reversible Computation”, Aharonov et al 1996`{=html} {#aharonov-et-al-1996-section} **[`Limitations of Noisy Reversible Computation`{=html}](https://arxiv.org/abs/quant-ph/9611028 "'Limitations of Noisy Reversible Computation', Aharonov et al 1996"){.link-annotated .id-not .include-annotation link-icon="𝛘" link-icon-type="text" link-icon-color="#b31b1b"}** ## `“A Personal View of Average-Case Complexity”, Impagliazzo 1995`{=html} {#impagliazzo-1995-section} **[`A Personal View of Average-Case Complexity`{=html}](/doc/cs/cryptography/1995-impagliazzo.pdf "'A Personal View of Average-Case Complexity', Impagliazzo 1995"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“On Feasible Numbers”, Sazonov 1995`{=html} {#sazonov-1995-section} **[`On feasible numbers`{=html}](/doc/philosophy/logic/1995-sazonov.pdf "'On feasible numbers', Sazonov 1995"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Threshold Circuits of Bounded Depth”, Hajnal et al 1993`{=html} {#hajnal-et-al-1993-section} **[`Threshold circuits of bounded depth`{=html}](https://www.sciencedirect.com/science/article/pii/002200009390001D "'Threshold circuits of bounded depth', Hajnal et al 1993"){.link-annotated .id-not .include-annotation link-icon="E" link-icon-type="text" link-icon-color="#eb6500"}** ## `“The Complexity of N-Body Simulation”, Reif & Tate 1993`{=html} {#reif-tate-1993-section} **[`The complexity of N-body simulation`{=html}](/doc/cs/computable/1993-reif.pdf "'The complexity of N-body simulation', Reif & Tate 1993"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Average Case Complexity under the Universal Distribution Equals Worst-Case Complexity”, Li & Vitányi 1992`{=html} {#li-vitányi-1992-section} **[`Average case complexity under the universal distribution equals worst-case complexity`{=html}](/doc/cs/algorithm/information/1992-li.pdf "'Average case complexity under the universal distribution equals worst-case complexity', Li & Vitányi 1992"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Time Travel and Computing”, Moravec 1991`{=html} {#moravec-1991-section} **[`Time Travel and Computing`{=html}](https://web.archive.org/web/20230525085828/https://www.frc.ri.cmu.edu/~hpm/project.archive/general.articles/1991/TempComp.html "'Time Travel and Computing', Moravec 1991"){.link-annotated-partial .id-not .include-annotation link-icon="internet-archive" link-icon-type="svg"}** ## `“Unpredictability and Undecidability in Dynamical Systems”, Moore 1990`{=html} {#moore-1990-section} **[`Unpredictability and undecidability in dynamical systems`{=html}](/doc/cs/computable/1990-moore.pdf "'Unpredictability and undecidability in dynamical systems', Moore 1990"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“A Differentiation Primitive for Extended Λ–calculus”, Flaherty 1988`{=html} {#flaherty-1988-section} **[`A differentiation primitive for extended λ–calculus`{=html}](/doc/cs/computable/1988-flaherty.pdf "'A differentiation primitive for extended λ–calculus', Flaherty 1988"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“FRACTRAN: A Simple Universal Programming Language for Arithmetic”, Conway 1987`{=html} {#conway-1987-section} **[`FRACTRAN: A Simple Universal Programming Language for Arithmetic`{=html}](/doc/cs/computable/1987-conway.pdf "'FRACTRAN: A Simple Universal Programming Language for Arithmetic', Conway 1987"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Conservative Logic”, Fredkin & Toffoli 1982`{=html} {#fredkin-toffoli-1982-section} **[`Conservative logic`{=html}](/doc/cs/hardware/1982-fredkin.pdf "'Conservative logic', Fredkin & Toffoli 1982"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Bi-Continuous Extensions of Invertible Combinatorial Functions”, Toffoli 1981`{=html} {#toffoli-1981-section} **[`Bi-continuous extensions of invertible combinatorial functions`{=html}](/doc/cs/hardware/1981-toffoli.pdf "'Bi-continuous extensions of invertible combinatorial functions', Toffoli 1981"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Unpredictable Iterations”, Conway 1972`{=html} {#conway-1972-section} **[`Unpredictable Iterations`{=html}](/doc/cs/computable/1972-conway.pdf "'Unpredictable Iterations', Conway 1972"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“О Невозможности Элиминации Полного Перебора При Вычислении Функций Относительно Их Графиков”, Дехтярь 1969`{=html} {#дехтярь-1969-section} **[`О невозможности элиминации полного перебора при вычислении функций относительно их графиков`{=html}](/doc/cs/computable/1969-dekhtiar.pdf "'О невозможности элиминации полного перебора при вычислении функций относительно их графиков', Дехтярь 1969"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“FLODAC—A Pure Fluid Digital Computer”, Gluskin et al 1964`{=html} {#gluskin-et-al-1964-section} **[`FLODAC—A Pure Fluid Digital Computer`{=html}](/doc/cs/computable/1964-gluskin.pdf "'FLODAC—A Pure Fluid Digital Computer', Gluskin et al 1964"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Tag Systems and Lag Systems”, Wang 1963`{=html} {#wang-1963-section} **[`Tag systems and lag systems`{=html}](/doc/cs/computable/1963-wang.pdf "'Tag systems and lag systems', Wang 1963"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“On Non-Computable Functions”, Rado 1962`{=html} {#rado-1962-section} **[`On Non-Computable Functions`{=html}](/doc/cs/computable/1962-rado.pdf "'On Non-Computable Functions', Rado 1962"){.link-annotated .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Representation of Events in Nerve Nets and Finite Automata”, Kleene 1951`{=html} {#kleene-1951-section} **[`Representation of Events in Nerve Nets and Finite Automata`{=html}](/doc/ai/nn/1951-kleene.pdf "'Representation of Events in Nerve Nets and Finite Automata', Kleene 1951"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“‘Computational Complexity of Air Travel Planning’, De Marcken 2003 [ITA Software]”`{=html} {#_t-2kZqMw-section} **[`‘Computational Complexity of Air Travel Planning’, de Marcken 2003 [ITA Software]`{=html}](http://www.demarcken.org/carl/papers/ITA-software-travel-complexity/ITA-software-travel-complexity.pdf "‘Computational Complexity of Air Travel Planning’, de Marcken 2003 [ITA Software]"){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** ## `“Universal Search § OOPS and Other Incremental Variations”`{=html} {#_tqDAza02-section} **[`Universal search § OOPS and other incremental variations`{=html}](http://www.scholarpedia.org/article/Universal_search#OOPS_and_other_incremental_variations "Universal search § OOPS and other incremental variations"){.id-not .include-annotation link-icon="scholarpedia" link-icon-type="svg"}** ## `“Computing With Time: Microarchitectural Weird Machines”`{=html} {#_YrZB7O1T-section} **[`Computing with Time: Microarchitectural Weird Machines`{=html}](https://cacm.acm.org/research-highlights/computing-with-time-microarchitectural-weird-machines/ "Computing with Time: Microarchitectural Weird Machines"){.link-annotated-partial .id-not .include-annotation link-icon="acm" link-icon-type="text,tri,sans" link-icon-color="#3795c4"}** ## `“How Exploits Impact Computer Science Theory”`{=html} {#_OE3sww3H-section} **[`How Exploits Impact Computer Science Theory`{=html}](https://cacm.acm.org/research-highlights/technical-perspective-how-exploits-impact-computer-science-theory/ "How Exploits Impact Computer Science Theory"){.link-annotated-partial .id-not .include-annotation link-icon="acm" link-icon-type="text,tri,sans" link-icon-color="#3795c4"}** ## `“The Dhall Configuration Language”`{=html} {#_cOf4ffrZ-section} **[`The Dhall configuration language`{=html}](https://dhall-lang.org/ "The Dhall configuration language"){.link-annotated-partial .id-not .include-annotation}** ## `“ByteByteJump”, Wiki 2026`{=html} {#_0z48JnGx-section} **[`ByteByteJump`{=html}](https://esolangs.org/wiki/ByteByteJump "'ByteByteJump', Wiki 2026"){.link-annotated .id-not .include-annotation}** ## `“Linear Bounded Automaton”`{=html} {#_WzXa_oXJ-section} **[`Linear bounded automaton`{=html}](https://esolangs.org/wiki/Linear_bounded_automaton "Linear bounded automaton"){.link-annotated-partial .id-not .include-annotation}** ## `“OISC”`{=html} {#_Jgq-Xdxt-section} **[`OISC`{=html}](https://esolangs.org/wiki/OISC "OISC"){.link-annotated-partial .id-not .include-annotation}** ## `“Ttf-Doom: A 3D Raycasting Engine Running inside a TrueType Font’s Hinting Virtual Machine”, Lytkin 2026`{=html} {#_y2Oa9s2h-section} **[`ttf-doom: A 3D raycasting engine running inside a TrueType font’s hinting virtual machine`{=html}](https://github.com/4RH1T3CT0R7/ttf-doom#readme "'ttf-doom: A 3D raycasting engine running inside a TrueType font’s hinting virtual machine', Lytkin 2026"){.link-annotated-partial .id-not .include-annotation link-icon="github" link-icon-type="svg"}** ## `“HexHive/printbf: Brainfuck Interpreter inside Printf”`{=html} {#_KgDyH5nr-section} **[`HexHive/printbf: Brainfuck interpreter inside printf`{=html}](https://github.com/HexHive/printbf "HexHive/printbf: Brainfuck interpreter inside printf"){.id-not .include-annotation link-icon="github" link-icon-type="svg"}** ## `“InkboxSoftware/excelCPU: 16-Bit CPU for Excel, and Related Files”`{=html} {#_wBuJzDhi-section} **[`InkboxSoftware/excelCPU: 16-bit CPU for Excel, and related files`{=html}](https://github.com/InkboxSoftware/excelCPU "InkboxSoftware/excelCPU: 16-bit CPU for Excel, and related files"){.link-annotated-partial .id-not .include-annotation link-icon="github" link-icon-type="svg"}** ## `“A WebAssembly Runtime Implemented in TypeScript Types [Which Runs Doom]”`{=html} {#_hxfY0q2z-section} **[`A WebAssembly runtime implemented in TypeScript types [which runs Doom]`{=html}](https://github.com/MichiganTypeScript/typescript-types-only-wasm-runtime "A WebAssembly runtime implemented in TypeScript types [which runs Doom]"){.link-annotated-partial .id-not .include-annotation link-icon="github" link-icon-type="svg"}** ## `“roguetype: The First Ever Rogue-Like Written in the OCaml Type System”, Octachron 2026`{=html} {#_fjIUm589-section} **[`roguetype: The first ever rogue-like written in the OCaml type system`{=html}](https://github.com/Octachron/roguetype "'roguetype: The first ever rogue-like written in the OCaml type system', Octachron 2026"){.link-annotated-partial .id-not .include-annotation link-icon="github" link-icon-type="svg"}** ## `“Linux Running inside a PDF File via a RISC-V Emulator”`{=html} {#_23PeO1P9-section} **[`Linux running inside a PDF file via a RISC-V emulator`{=html}](https://github.com/ading2210/linuxpdf "Linux running inside a PDF file via a RISC-V emulator"){.link-annotated-partial .id-not .include-annotation link-icon="github" link-icon-type="svg"}** ## `“Sudoku Solving in Python Packaging”`{=html} {#_MXylii2k-section} **[`Sudoku solving in python packaging`{=html}](https://github.com/konstin/sudoku-in-python-packaging "Sudoku solving in python packaging"){.link-annotated-partial .id-not .include-annotation link-icon="github" link-icon-type="svg"}** ## `“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…).”`{=html} {#_gzzDeFyr-section} **[`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…).`{=html}](https://github.com/kspalaiologos/malbolge-lisp "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…)."){.link-annotated-partial .id-not .include-annotation link-icon="github" link-icon-type="svg"}** ## `“ebpf-For-Windows: EBPF Implementation That Runs on top of Microsoft Windows”, Microsoft 2026`{=html} {#_vPKqqnso-section} **[`ebpf-for-windows: eBPF implementation that runs on top of Microsoft Windows`{=html}](https://github.com/microsoft/ebpf-for-windows "'ebpf-for-windows: eBPF implementation that runs on top of Microsoft Windows', Microsoft 2026"){.link-annotated-partial .id-not .include-annotation link-icon="MS" link-icon-type="text,sans,italic"}** ## `“How I Did Relay Quine”`{=html} {#_A0v5082l-section} **[`How I Did Relay Quine`{=html}](https://github.com/mmulet/code-relay/blob/main/markdown/HowIDidIt.md "How I Did Relay Quine"){.link-annotated-partial .id-not .include-annotation link-icon="github" link-icon-type="svg"}** ## `“Using SQL’s Turing Completeness to Build Tetris”`{=html} {#_EtvXTt0C-section} **[`Using SQL’s Turing Completeness to Build Tetris`{=html}](https://github.com/nuno-faria/tetris-sql "Using SQL’s Turing Completeness to Build Tetris"){.link-annotated-partial .id-not .include-annotation link-icon="github" link-icon-type="svg"}** ## `“C99 Doesn’t Need Function Bodies, Or, ‘VLAs Are Turing Complete’”`{=html} {#_7YS2GNoW-section} **[`C99 doesn’t need function bodies, or, ‘VLAs are Turing complete’`{=html}](https://lemon.rip/w/c99-vla-tricks/ "C99 doesn’t need function bodies, or, ‘VLAs are Turing complete’"){.link-annotated-partial .id-not .include-annotation}** ## `“X86CSS”`{=html} {#_WXg6cMCY-section} **[`x86CSS`{=html}](https://lyra.horse/x86css/ "x86CSS"){.id-not .include-annotation}** ## `“McCulloch and Pitts [Re-Evaluating Neuroscientifically]”`{=html} {#_8EPD131B-section} **[`McCulloch and Pitts [re-evaluating neuroscientifically]`{=html}](https://marlin.life.utsa.edu/mcculloch-and-pitts.html "McCulloch and Pitts [re-evaluating neuroscientifically]"){.link-annotated-partial .id-not .include-annotation}** ## `“Another New Record in Self-Cleaning Turing Machines”`{=html} {#_OC_98Qy5-section} **[`Another New Record in Self-Cleaning Turing Machines`{=html}](https://nickdrozd.github.io/2022/01/10/another-self-cleaning-turing-machine.html "Another New Record in Self-Cleaning Turing Machines"){.link-annotated-partial .id-not .include-annotation}** ## `“find + mkdir Is Turing Complete (Retracted)”, Kako 2026`{=html} {#_3uuL8eQJ-section} **[`find + mkdir is Turing complete (retracted)`{=html}](https://ogiekako.vercel.app/blog/find_mkdir_tc "'find + mkdir is Turing complete (retracted)', Kako 2026"){.link-annotated-partial .id-not .include-annotation}** ## `“Doom, Compiled into a Transformer”`{=html} {#_l0fIa5_T-section} **[`Doom, compiled into a transformer`{=html}](https://ood.dev/posts/doom/ "Doom, compiled into a transformer"){.link-modified-recently .link-annotated-partial .id-not .include-annotation}** ## `“Predicting the Tide With an Analog Computer Made from Lego”`{=html} {#_HBGd3aoJ-section} **[`Predicting the tide with an analog computer made from Lego`{=html}](https://pepijndevos.nl/2022/01/30/predicting-the-tide-with-an-analog-computer-made-from-lego.html "Predicting the tide with an analog computer made from Lego"){.id-not .include-annotation}** ## `“PEP 611: The One Million Limit”`{=html} {#_rnMdEaG4-section} **[`PEP 611: The one million limit`{=html}](https://peps.python.org/pep-0611/ "PEP 611: The one million limit"){.link-annotated-partial .id-not .include-annotation}** ## `“Choon Programming Language”`{=html} {#_1doLXYbr-section} **[`Choon Programming Language`{=html}](https://sange.fi/esoteric/essie2/download/choon/choon.html "Choon Programming Language"){.id-not .include-annotation}** ## `“Rosser’s Theorem via Turing Machines”`{=html} {#_vxIdlgFx-section} **[`Rosser’s Theorem via Turing machines`{=html}](https://scottaaronson.blog/?p=710 "Rosser’s Theorem via Turing machines"){.link-annotated-partial .id-not .include-annotation link-icon="SA" link-icon-type="text,sans" link-icon-color="#4181b7"}** ## `“Busy Beaver(5) Is Now Proven to Be 47,176,870”`{=html} {#_VAXQPvE5-section} **[`Busy Beaver(5) is now proven to be 47,176,870`{=html}](https://scottaaronson.blog/?p=8088 "Busy Beaver(5) is now proven to be 47,176,870"){.link-annotated-partial .id-not .include-annotation link-icon="SA" link-icon-type="text,sans" link-icon-color="#4181b7"}** ## `“Rust’s Type System Is Turing-Complete”, Leffler 2026`{=html} {#_ckt-t3Xk-section} **[`Rust’s Type System is Turing-Complete`{=html}](https://sdleffler.github.io/RustTypeSystemTuringComplete/ "'Rust’s Type System is Turing-Complete', Leffler 2026"){.link-annotated-partial .id-not .include-annotation}** ## `“OpenTTD Logic”`{=html} {#_Miw1X4B6-section} **[`OpenTTD Logic`{=html}](https://web.archive.org/web/20241225050720/https://wiki.openttdcoop.org/Logic "OpenTTD Logic"){.link-annotated-partial .id-not .include-annotation link-icon="internet-archive" link-icon-type="svg"}** ## `“Weird Machines HQ”`{=html} {#_h6WAaveV-section} **[`Weird Machines HQ`{=html}](https://weirdmachines.gitlab.io/ "Weird Machines HQ"){.id-not .include-annotation}** ## `“The Infinity Machine”`{=html} {#_CsaEKAXI-section} **[`The Infinity Machine`{=html}](https://www.chiark.greenend.org.uk/~sgtatham/infinity.html "The Infinity Machine"){.link-annotated-partial .id-not .include-annotation}** ## `Fontemon`{=html} {#_WGnVCH6B-section} **[`Fontemon`{=html}](https://www.coderelay.io/fontemon.html "Fontemon"){.link-annotated-partial .id-not .include-annotation}** ## `“A Computational No-Coincidence Principle”`{=html} {#_98_lWGCP-section} **[`A computational no-coincidence principle`{=html}](https://www.lesswrong.com/posts/Xt9r4SNNuYxW83tmo/a-computational-no-coincidence-principle "A computational no-coincidence principle"){.link-annotated-partial .id-not .include-annotation link-icon="LW" link-icon-type="text" link-icon-color="#7faf83"}** ## `“LLMs As Giant Lookup-Tables of Shallow Circuits”, niplav 2026`{=html} {#_ne7BWIoa-section} **[`LLMs as Giant Lookup-Tables of Shallow Circuits`{=html}](https://www.lesswrong.com/posts/a9KqqgjN8gc3Mzzkh/llms-as-giant-lookup-tables-of-shallow-circuits "'LLMs as Giant Lookup-Tables of Shallow Circuits', niplav 2026"){.link-annotated-partial .id-not .include-annotation link-icon="LW" link-icon-type="text" link-icon-color="#7faf83"}** ## `“(Maybe) A Bag of Heuristics Is All There Is & A Bag of Heuristics Is All You Need”`{=html} {#_dnQ_opit-section} **[`(Maybe) A Bag of Heuristics is All There Is & A Bag of Heuristics is All You Need`{=html}](https://www.lesswrong.com/posts/azCuKGJTecCDLBEEj/maybe-a-bag-of-heuristics-is-all-there-is-and-a-bag-of "(Maybe) A Bag of Heuristics is All There Is & A Bag of Heuristics is All You Need"){.link-annotated-partial .id-not .include-annotation link-icon="LW" link-icon-type="text" link-icon-color="#7faf83"}** ## `“A Brief History of Liquid Computers”`{=html} {#_BvzSeDau-section} **[`A brief history of liquid computers`{=html}](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6553589/ "A brief history of liquid computers"){.id-not .include-annotation link-icon="nlm-ncbi" link-icon-type="svg" link-icon-color="#20558a"}** ## `“Rule 110 Train Turing Machine Explained”`{=html} {#_MxSdmW5G-section} **[`Rule 110 Train Turing Machine Explained`{=html}](https://www.youtube.com/watch?v=Ubc7iNZ7MV8 "Rule 110 Train Turing Machine Explained"){.id-not .include-annotation link-icon="youtube" link-icon-type="svg" link-icon-color="#ff0033"}** ::: aux-links-transclude-file [`https://www.youtube.com/watch?v=Ubc7iNZ7MV8`](https://www.youtube.com/watch?v=Ubc7iNZ7MV8){.link-annotated-not .include-content .width-full} ::: ## `“I Built ChatGPT With Minecraft Redstone!”`{=html} {#_o3VC0S9p-section} **[`I built ChatGPT with Minecraft redstone!`{=html}](https://www.youtube.com/watch?v=VaeI9YgE1o8 "I built ChatGPT with Minecraft redstone!"){.id-not .include-annotation link-icon="youtube" link-icon-type="svg" link-icon-color="#ff0033"}** ::: aux-links-transclude-file [`https://www.youtube.com/watch?v=VaeI9YgE1o8`](https://www.youtube.com/watch?v=VaeI9YgE1o8){.link-annotated-not .include-content .width-full} ::: ## `“Turing Machine Busy Beaver 5 Champ–47,176,870 Steps–Perfect Pixel Binning”`{=html} {#_Wp3zpzQn-section} **[`Turing Machine Busy Beaver 5 Champ–47,176,870 Steps–Perfect Pixel Binning`{=html}](https://www.youtube.com/watch?v=fPGg4kwwkGg "Turing Machine Busy Beaver 5 Champ–47,176,870 Steps–Perfect Pixel Binning"){.id-not .include-annotation link-icon="youtube" link-icon-type="svg" link-icon-color="#ff0033"}** ::: aux-links-transclude-file [`https://www.youtube.com/watch?v=fPGg4kwwkGg`](https://www.youtube.com/watch?v=fPGg4kwwkGg){.link-annotated-not .include-content .width-full} ::: ## `“On The Turing Completeness of PowerPoint”`{=html} {#_3vvBb5_Z-section} **[`On The Turing Completeness of PowerPoint`{=html}](https://www.youtube.com/watch?v=uNjxe8ShM-8 "On The Turing Completeness of PowerPoint"){.id-not .include-annotation link-icon="youtube" link-icon-type="svg" link-icon-color="#ff0033"}** ::: aux-links-transclude-file [`https://www.youtube.com/watch?v=uNjxe8ShM-8`](https://www.youtube.com/watch?v=uNjxe8ShM-8){.link-annotated-not .include-content .width-full} ::: ## Sort By Magic ::: {demo-type="sort-by-magic-preface"} Annotations sorted by machine learning into [inferred \'tags\'](/design#future-tag-features){#gwern-design--future-tag-features .link-annotated-partial}. 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. ::: ### `mitosis-memory` {.collapse title="Machine-generated tag name for the following cluster of links."} [\[see previous entry\]](#meitinger-et-al-2022-section){.include .include-even-when-collapsed} ### `open-games` {.collapse title="Machine-generated tag name for the following cluster of links."} [\[see previous entry\]](#ghani-et-al-2016-section){.include .include-even-when-collapsed} [\[see previous entry\]](#schlesinger-2017-section){.include .include-even-when-collapsed} ### `random-satisfiability` {.collapse title="Machine-generated tag name for the following cluster of links."} [\[see previous entry\]](#feldman-et-al-2013-section){.include .include-even-when-collapsed} [\[see previous entry\]](#mezard-et-al-2002-section){.include .include-even-when-collapsed} ### `tokenization np-complete` {.collapse title="Machine-generated tag name for the following cluster of links."} [\[see previous entry\]](#whittington-et-al-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#murty-et-al-2022-section){.include .include-even-when-collapsed} [\[see previous entry\]](#chen-et-al-2022-02-section){.include .include-even-when-collapsed} [\[see previous entry\]](#gardner-et-al-2025-section){.include .include-even-when-collapsed} ### `type-hints` {.collapse title="Machine-generated tag name for the following cluster of links."} [\[see previous entry\]](#grigore-2016-section){.include .include-even-when-collapsed} [\[see previous entry\]](#roth-2022-section){.include .include-even-when-collapsed} ### `undecidable-problems` {.collapse title="Machine-generated tag name for the following cluster of links."} [\[see previous entry\]](#hamkins-miasnikov-2005-section){.include .include-even-when-collapsed} [\[see previous entry\]](#cubitt-et-al-2015-section){.include .include-even-when-collapsed} [\[see previous entry\]](#demaine-langerman-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#demaine-et-al-2020-section){.include .include-even-when-collapsed} [\[see previous entry\]](#hamilton-2014-section){.include .include-even-when-collapsed} ### `non-computability` {.collapse title="Machine-generated tag name for the following cluster of links."} [\[see previous entry\]](#rado-1962-section){.include .include-even-when-collapsed} [\[see previous entry\]](#escardo-2007-section){.include .include-even-when-collapsed} [\[see previous entry\]](#friedman-2002-page-4-section){.include .include-even-when-collapsed} ### `universal-tm` {.collapse title="Machine-generated tag name for the following cluster of links."} [\[see previous entry\]](#reif-tate-1993-section){.include .include-even-when-collapsed} [\[see previous entry\]](#williams-2025-section){.include .include-even-when-collapsed} [\[see previous entry\]](#neary-2008-section){.include .include-even-when-collapsed} [\[see previous entry\]](#wang-1963-section){.include .include-even-when-collapsed} ### `obfuscation-techniques` {.collapse title="Machine-generated tag name for the following cluster of links."} [\[see previous entry\]](#mateas-montfort-2005-section){.include .include-even-when-collapsed} [\[see previous entry\]](#beer-groß-2021-section){.include .include-even-when-collapsed} [\[see previous entry\]](#hearn-2025-section){.include .include-even-when-collapsed} ### `turing-completeness` {.collapse title="Machine-generated tag name for the following cluster of links."} [\[see previous entry\]](#_0z48JnGx-section){.include .include-even-when-collapsed} [\[see previous entry\]](#aaronson-2019-section){.include .include-even-when-collapsed} [\[see previous entry\]](#pavlus-2020-section){.include .include-even-when-collapsed} [\[see previous entry\]](#yedidia-aaronson-2016-section){.include .include-even-when-collapsed} [\[see previous entry\]](#conway-2013-section){.include .include-even-when-collapsed} [\[see previous entry\]](#braithwaite-2020-section){.include .include-even-when-collapsed} [\[see previous entry\]](#conway-1987-section){.include .include-even-when-collapsed} [\[see previous entry\]](#yin-churchill-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#churchill-et-al-2019-section){.include .include-even-when-collapsed} [\[see previous entry\]](#biderman-2020-section){.include .include-even-when-collapsed} [\[see previous entry\]](#wynter-2021-section){.include .include-even-when-collapsed} [\[see previous entry\]](#wynter-2026-section){.include .include-even-when-collapsed} [\[see previous entry\]](#kleinberg-mullainathan-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#schuurmans-et-al-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#schuurmans-2023-section){.include .include-even-when-collapsed} [\[see previous entry\]](#pérez-et-al-2019-section){.include .include-even-when-collapsed} [\[see previous entry\]](#yun-et-al-2019-section){.include .include-even-when-collapsed} [\[see previous entry\]](#bergsträßer-et-al-2025-section){.include .include-even-when-collapsed} [\[see previous entry\]](#chiang-et-al-2023-2-section){.include .include-even-when-collapsed} [\[see previous entry\]](#merrill-sabharwal-2022-2-section){.include .include-even-when-collapsed} [\[see previous entry\]](#merrill-sabharwal-2022-1-section){.include .include-even-when-collapsed} [\[see previous entry\]](#liu-et-al-2022-section){.include .include-even-when-collapsed} [\[see previous entry\]](#zhang-et-al-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#friedman-et-al-2023-section){.include .include-even-when-collapsed} [\[see previous entry\]](#weiss-et-al-2021-section){.include .include-even-when-collapsed} [\[see previous entry\]](#angluin-et-al-2023-section){.include .include-even-when-collapsed} [\[see previous entry\]](#chiang-cholak-2022-section){.include .include-even-when-collapsed} [\[see previous entry\]](#hahn-rofin-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#garg-et-al-2022-section){.include .include-even-when-collapsed} [\[see previous entry\]](#li-et-al-2024-09-section){.include .include-even-when-collapsed} [\[see previous entry\]](#feng-et-al-2023-2-section){.include .include-even-when-collapsed} [\[see previous entry\]](#merrill-sabharwal-2023-section){.include .include-even-when-collapsed} [\[see previous entry\]](#qiu-et-al-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#giannou-et-al-2023-section){.include .include-even-when-collapsed} [\[see previous entry\]](#shaw-et-al-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#goel-bartlett-2023-section){.include .include-even-when-collapsed} [\[see previous entry\]](#merrill-et-al-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#hänni-et-al-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#adler-shavit-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#uchizawa-et-al-2006-section){.include .include-even-when-collapsed} [\[see previous entry\]](#hajnal-et-al-1993-section){.include .include-even-when-collapsed} [\[see previous entry\]](#aharonov-et-al-1996-section){.include .include-even-when-collapsed} [\[see previous entry\]](#yamakawa-zhandry-2022-section){.include .include-even-when-collapsed} [\[see previous entry\]](#jordan-et-al-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#huang-et-al-2021-2-section){.include .include-even-when-collapsed} [\[see previous entry\]](#bermejo-et-al-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#lin-et-al-2016-2-section){.include .include-even-when-collapsed} [\[see previous entry\]](#kidger-lyons-2019-section){.include .include-even-when-collapsed} [\[see previous entry\]](#kratsios-et-al-2026-section){.include .include-even-when-collapsed} [\[see previous entry\]](#delétang-et-al-2022-section){.include .include-even-when-collapsed} [\[see previous entry\]](#lan-et-al-2021-1-section){.include .include-even-when-collapsed} [\[see previous entry\]](#hahn-et-al-2021-2-section){.include .include-even-when-collapsed} [\[see previous entry\]](#sucholutsky-schonlau-2020-section){.include .include-even-when-collapsed} [\[see previous entry\]](#elsayed-et-al-2018-adversarial-reprogramming-section){.include .include-even-when-collapsed} [\[see previous entry\]](#anantharaman-et-al-2019-section){.include .include-even-when-collapsed} [\[see previous entry\]](#dullien-2017-section){.include .include-even-when-collapsed} [\[see previous entry\]](#bratus-2015-section){.include .include-even-when-collapsed} [\[see previous entry\]](#johnson-2021-section){.include .include-even-when-collapsed} [\[see previous entry\]](#hales-2013-section){.include .include-even-when-collapsed} [\[see previous entry\]](#schmidhuber-2003-section){.include .include-even-when-collapsed} [\[see previous entry\]](#hutter-2002-section){.include .include-even-when-collapsed} [\[see previous entry\]](#legg-2006-section){.include .include-even-when-collapsed} [\[see previous entry\]](#hutter-2007-section){.include .include-even-when-collapsed} [\[see previous entry\]](#levin-2002-section){.include .include-even-when-collapsed} [\[see previous entry\]](#moore-1990-section){.include .include-even-when-collapsed} [\[see previous entry\]](#miranda-ramos-2025-section){.include .include-even-when-collapsed} [\[see previous entry\]](#beggs-tucker-2007-section){.include .include-even-when-collapsed} [\[see previous entry\]](#cardona-et-al-2020-section){.include .include-even-when-collapsed} [\[see previous entry\]](#freedman-1998-section){.include .include-even-when-collapsed} [\[see previous entry\]](#aaronson-watrous-2008-section){.include .include-even-when-collapsed} [\[see previous entry\]](#mitchison-jozsa-1999-section){.include .include-even-when-collapsed} [\[see previous entry\]](#yakaryilmaz-et-al-2010-section){.include .include-even-when-collapsed} [\[see previous entry\]](#linden-et-al-2006-section){.include .include-even-when-collapsed} [\[see previous entry\]](#impagliazzo-1995-section){.include .include-even-when-collapsed} [\[see previous entry\]](#li-vitányi-1992-section){.include .include-even-when-collapsed} [\[see previous entry\]](#buhrman-et-al-2014-section){.include .include-even-when-collapsed} [\[see previous entry\]](#folkertsma-et-al-2024-section){.include .include-even-when-collapsed} [\[see previous entry\]](#gupta-et-al-2024-lossy-section){.include .include-even-when-collapsed} [\[see previous entry\]](#akhlaghpour-2022-section){.include .include-even-when-collapsed} [\[see previous entry\]](#parsa-et-al-2023-section){.include .include-even-when-collapsed} [\[see previous entry\]](#vučinović-2018-section){.include .include-even-when-collapsed} [\[see previous entry\]](#hull-zakharevich-2023-section){.include .include-even-when-collapsed} [\[see previous entry\]](#gonzález-prieto-et-al-2025-section){.include .include-even-when-collapsed} [\[see previous entry\]](#baez-stay-2009-section){.include .include-even-when-collapsed} [\[see previous entry\]](#lloyd-2005-section){.include .include-even-when-collapsed} [\[see previous entry\]](#drescher-2006-section){.include .include-even-when-collapsed} [\[see previous entry\]](#lamport-2012-section){.include .include-even-when-collapsed} [\[see previous entry\]](#lamport-palais-2017-section){.include .include-even-when-collapsed} [\[see previous entry\]](#walker-et-al-2006-section){.include .include-even-when-collapsed} [\[see previous entry\]](#fredkin-toffoli-1982-section){.include .include-even-when-collapsed} [\[see previous entry\]](#toffoli-1981-section){.include .include-even-when-collapsed} [\[see previous entry\]](#flaherty-1988-section){.include .include-even-when-collapsed} [\[see previous entry\]](#odrzywołek-2026-section){.include .include-even-when-collapsed} [\[see previous entry\]](#lanthaler-et-al-2023-section){.include .include-even-when-collapsed} [\[see previous entry\]](#schultz-et-al-2013-section){.include .include-even-when-collapsed} [\[see previous entry\]](#schultz-et-al-2009-section){.include .include-even-when-collapsed} [\[see previous entry\]](#sol-et-al-2019-section){.include .include-even-when-collapsed} [\[see previous entry\]](#erez-et-al-2017-section){.include .include-even-when-collapsed} [\[see previous entry\]](#biswas-et-al-2021-section){.include .include-even-when-collapsed} [\[see previous entry\]](#baluška-levin-2016-section){.include .include-even-when-collapsed} [\[see previous entry\]](#adamatzky-2016-section){.include .include-even-when-collapsed} [\[see previous entry\]](#michael-2009-section){.include .include-even-when-collapsed} [\[see previous entry\]](#gunji-et-al-2012-section){.include .include-even-when-collapsed} ## Wikipedia (48) {#titled-links-wikipedia .collapse} 1. **[`Artificial immune system`{=html}](https://en.wikipedia.org/wiki/Artificial_immune_system "Artificial immune system"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Artificial_immune_system`](https://en.wikipedia.org/wiki/Artificial_immune_system "Artificial immune system"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 2. **[`Büchi arithmetic`{=html}](https://en.wikipedia.org/wiki/B%C3%BCchi_arithmetic "Büchi arithmetic"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/B%C3%BCchi_arithmetic`](https://en.wikipedia.org/wiki/B%C3%BCchi_arithmetic "Büchi arithmetic"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 3. **[`Billiard-ball computer`{=html}](https://en.wikipedia.org/wiki/Billiard-ball_computer "Billiard-ball computer"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 4. **[`Blum’s speedup theorem`{=html}](https://en.wikipedia.org/wiki/Blum%27s_speedup_theorem "Blum’s speedup theorem"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 5. **[`Chris Langton`{=html}](https://en.wikipedia.org/wiki/Christopher_Langton "Chris Langton"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 6. **[`Circuit complexity`{=html}](https://en.wikipedia.org/wiki/Circuit_complexity "Circuit complexity"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 7. **[`Common Lisp`{=html}](https://en.wikipedia.org/wiki/Common_Lisp "Common Lisp"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 8. **[`Common Lisp Object System`{=html}](https://en.wikipedia.org/wiki/Common_Lisp_Object_System "Common Lisp Object System"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Common_Lisp_Object_System`](https://en.wikipedia.org/wiki/Common_Lisp_Object_System "Common Lisp Object System"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 9. **[`Continuation`{=html}](https://en.wikipedia.org/wiki/Continuation "Continuation"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 10. **[`Counterfactual quantum computation`{=html}](https://en.wikipedia.org/wiki/Counterfactual_quantum_computation "Counterfactual quantum computation"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Counterfactual_quantum_computation`](https://en.wikipedia.org/wiki/Counterfactual_quantum_computation "Counterfactual quantum computation"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 11. **[`David Deutsch`{=html}](https://en.wikipedia.org/wiki/David_Deutsch "David Deutsch"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/David_Deutsch`](https://en.wikipedia.org/wiki/David_Deutsch "David Deutsch"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 12. **[`Emacs`{=html}](https://en.wikipedia.org/wiki/Emacs "Emacs"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 13. **[`Flavors (programming language)`{=html}](https://en.wikipedia.org/wiki/Flavors_(programming_language) "Flavors (programming language)"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Flavors_(programming_language)`](https://en.wikipedia.org/wiki/Flavors_(programming_language) "Flavors (programming language)"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 14. **[`Gödel’s speed-up theorem`{=html}](https://en.wikipedia.org/wiki/G%C3%B6del%27s_speed-up_theorem "Gödel’s speed-up theorem"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/G%C3%B6del%27s_speed-up_theorem`](https://en.wikipedia.org/wiki/G%C3%B6del%27s_speed-up_theorem "Gödel’s speed-up theorem"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 15. **[`Gödel machine`{=html}](https://en.wikipedia.org/wiki/G%C3%B6del_machine "Gödel machine"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 16. **[`GNU Emacs`{=html}](https://en.wikipedia.org/wiki/GNU_Emacs "GNU Emacs"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/GNU_Emacs`](https://en.wikipedia.org/wiki/GNU_Emacs "GNU Emacs"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 17. **[`Open Genera`{=html}](https://en.wikipedia.org/wiki/Genera_(operating_system) "Open Genera"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 18. **[`Goodstein’s theorem`{=html}](https://en.wikipedia.org/wiki/Goodstein%27s_theorem "Goodstein’s theorem"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Goodstein%27s_theorem`](https://en.wikipedia.org/wiki/Goodstein%27s_theorem "Goodstein’s theorem"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 19. **[`Greenspun’s tenth rule`{=html}](https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule "Greenspun’s tenth rule"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 20. **[`Hao Wang (academic)`{=html}](https://en.wikipedia.org/wiki/Hao_Wang_(academic) "Hao Wang (academic)"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 21. **[`International Obfuscated C Code Contest (IOCCC)`{=html}](https://en.wikipedia.org/wiki/International_Obfuscated_C_Code_Contest "International Obfuscated C Code Contest (IOCCC)"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 22. **[`Iota and Jot`{=html}](https://en.wikipedia.org/wiki/Iota_and_Jot "Iota and Jot"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Iota_and_Jot`](https://en.wikipedia.org/wiki/Iota_and_Jot "Iota and Jot"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 23. **[`JSFuck`{=html}](https://en.wikipedia.org/wiki/JSFuck "JSFuck"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 24. **[`Kleene’s recursion theorem`{=html}](https://en.wikipedia.org/wiki/Kleene's_recursion_theorem "Kleene’s recursion theorem"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Kleene's_recursion_theorem`](https://en.wikipedia.org/wiki/Kleene's_recursion_theorem "Kleene’s recursion theorem"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 25. **[`Kolmogorov complexity § Chaitin’s incompleteness theorem`{=html}](https://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin%27s_incompleteness_theorem "Kolmogorov complexity § Chaitin’s incompleteness theorem"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin%27s_incompleteness_theorem`](https://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin%27s_incompleteness_theorem "Kolmogorov complexity § Chaitin’s incompleteness theorem"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 26. **[`Langton’s ant`{=html}](https://en.wikipedia.org/wiki/Langton%27s_ant "Langton’s ant"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 27. **[`Language identification in the limit`{=html}](https://en.wikipedia.org/wiki/Language_identification_in_the_limit "Language identification in the limit"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 28. **[`Lisp Machine Lisp`{=html}](https://en.wikipedia.org/wiki/Lisp_Machine_Lisp "Lisp Machine Lisp"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Lisp_Machine_Lisp`](https://en.wikipedia.org/wiki/Lisp_Machine_Lisp "Lisp Machine Lisp"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 29. **[`Lisp Machines`{=html}](https://en.wikipedia.org/wiki/Lisp_Machines "Lisp Machines"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Lisp_Machines`](https://en.wikipedia.org/wiki/Lisp_Machines "Lisp Machines"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 30. **[`Lisp machine`{=html}](https://en.wikipedia.org/wiki/Lisp_machine "Lisp machine"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 31. **[`Macsyma`{=html}](https://en.wikipedia.org/wiki/Macsyma "Macsyma"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Macsyma`](https://en.wikipedia.org/wiki/Macsyma "Macsyma"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 32. **[`Metaobject`{=html}](https://en.wikipedia.org/wiki/Metaobject "Metaobject"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Metaobject`](https://en.wikipedia.org/wiki/Metaobject "Metaobject"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 33. **[`Partial evaluation`{=html}](https://en.wikipedia.org/wiki/Partial_evaluation "Partial evaluation"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 34. **[`Pushdown automaton`{=html}](https://en.wikipedia.org/wiki/Pushdown_automaton "Pushdown automaton"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Pushdown_automaton`](https://en.wikipedia.org/wiki/Pushdown_automaton "Pushdown automaton"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 35. **[`Quorum sensing`{=html}](https://en.wikipedia.org/wiki/Quorum_sensing "Quorum sensing"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 36. **[`Reservoir computing`{=html}](https://en.wikipedia.org/wiki/Reservoir_computing "Reservoir computing"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 37. **[`Scott Aaronson`{=html}](https://en.wikipedia.org/wiki/Scott_Aaronson "Scott Aaronson"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 38. **[`Solomonoff’s theory of inductive inference`{=html}](https://en.wikipedia.org/wiki/Solomonoff%27s_theory_of_inductive_inference "Solomonoff’s theory of inductive inference"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 39. **[`Straight-line program`{=html}](https://en.wikipedia.org/wiki/Straight-line_program "Straight-line program"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Straight-line_program`](https://en.wikipedia.org/wiki/Straight-line_program "Straight-line program"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 40. **[`Symbolics`{=html}](https://en.wikipedia.org/wiki/Symbolics "Symbolics"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 41. **[`Symbolics Document Examiner`{=html}](https://en.wikipedia.org/wiki/Symbolics_Document_Examiner "Symbolics Document Examiner"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Symbolics_Document_Examiner`](https://en.wikipedia.org/wiki/Symbolics_Document_Examiner "Symbolics Document Examiner"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 42. **[`TC0`{=html}](https://en.wikipedia.org/wiki/TC0 "TC0"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 43. **[`Toffoli gate`{=html}](https://en.wikipedia.org/wiki/Toffoli_gate "Toffoli gate"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Toffoli_gate`](https://en.wikipedia.org/wiki/Toffoli_gate "Toffoli gate"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 44. **[`‘Trojan Source’ Unicode attack`{=html}](https://en.wikipedia.org/wiki/Trojan_Source "‘Trojan Source’ Unicode attack"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 45. **[`Turmite`{=html}](https://en.wikipedia.org/wiki/Turmite "Turmite"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Turmite`](https://en.wikipedia.org/wiki/Turmite "Turmite"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 46. **[`Ultrafinitism`{=html}](https://en.wikipedia.org/wiki/Ultrafinitism "Ultrafinitism"){.link-annotated-partial .id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** 47. **[`Yao’s de-randomization principle`{=html}](https://en.wikipedia.org/wiki/Yao%27s_principle "Yao’s de-randomization principle"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Yao%27s_principle`](https://en.wikipedia.org/wiki/Yao%27s_principle "Yao’s de-randomization principle"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: 48. **[`Zmacs`{=html}](https://en.wikipedia.org/wiki/Zmacs "Zmacs"){.id-not .include-annotation link-icon="wikipedia" link-icon-type="svg"}** ::: aux-links-transclude-file [`https://en.wikipedia.org/wiki/Zmacs`](https://en.wikipedia.org/wiki/Zmacs "Zmacs"){.id-not .include-content include-template="$annotationFileIncludeTemplate"} ::: # Miscellaneous - **[`https://x.com/GrantSlatton/status/1600388425651453953`{=html}](https://x.com/GrantSlatton/status/1600388425651453953 "Slatton 2022"){.link-annotated-partial .id-not .include-annotation link-icon="twitter" link-icon-type="svg" link-icon-color="#1da1f2"}** - **[`/doc/cs/computable/2022-garg-figure5b-transformersbeatxgboostatfittingsmalldecisiontrees.png`{=html}](/doc/cs/computable/2022-garg-figure5b-transformersbeatxgboostatfittingsmalldecisiontrees.png){.link-annotated-partial .id-not .include-annotation link-icon="image" link-icon-type="svg"}** - **[`/doc/cs/computable/2008-neary-figure111-spacetimetradeoffinminimalturingmachines.jpg`{=html}](/doc/cs/computable/2008-neary-figure111-spacetimetradeoffinminimalturingmachines.jpg){.link-annotated-partial .id-not .include-annotation link-icon="image" link-icon-type="svg"}** - **[`http://pepijndevos.nl/2022/01/30/predicting-the-tide-with-an-analog-computer-made-from-lego.html`{=html}](http://pepijndevos.nl/2022/01/30/predicting-the-tide-with-an-analog-computer-made-from-lego.html){.link-annotated-partial .id-not .include-annotation}** - **[`http://tom7.org/abc/paper.pdf`{=html}](http://tom7.org/abc/paper.pdf){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** - **[`http://tunes.org/~iepos/befreak.html`{=html}](http://tunes.org/~iepos/befreak.html){.link-annotated-partial .id-not .include-annotation}** - **[`http://weblog.raganwald.com/2004/10/beware-of-turing-tar-pit.html`{=html}](http://weblog.raganwald.com/2004/10/beware-of-turing-tar-pit.html){.id-not .include-annotation}** - **[`http://www.cr31.co.uk/stagecast/trains/tt3_univ.html`{=html}](http://www.cr31.co.uk/stagecast/trains/tt3_univ.html){.id-not .include-annotation}** - **[`http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html`{=html}](http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html){.id-not .include-annotation}** - **[`https://bernsteinbear.com/blog/weval/`{=html}](https://bernsteinbear.com/blog/weval/){.link-annotated-partial .id-not .include-annotation}** - **[`https://blog.computationalcomplexity.org/2023/12/where-do-non-primitive-recursive.html`{=html}](https://blog.computationalcomplexity.org/2023/12/where-do-non-primitive-recursive.html){.link-annotated-partial .id-not .include-annotation}** - **[`https://blog.cryptographyengineering.com/2017/07/02/beyond-public-key-encryption/`{=html}](https://blog.cryptographyengineering.com/2017/07/02/beyond-public-key-encryption/){.link-annotated-partial .id-not .include-annotation}** - **[`https://chemlambda.github.io/index.html`{=html}](https://chemlambda.github.io/index.html){.link-annotated-partial .id-not .include-annotation}** - **[`https://codegolf.stackexchange.com/a/100785/98955`{=html}](https://codegolf.stackexchange.com/a/100785/98955){.id-not .include-annotation link-icon="stack-exchange" link-icon-type="svg" link-icon-color="#f48024"}** - **[`https://dev.to/grahamthedev/bubble-sortin-pure-css-no-js-3bb1`{=html}](https://dev.to/grahamthedev/bubble-sortin-pure-css-no-js-3bb1){.id-not .include-annotation}** - **[`https://dev.to/grahamthedev/pure-css-neural-network-aiits-easier-that-you-think-f02`{=html}](https://dev.to/grahamthedev/pure-css-neural-network-aiits-easier-that-you-think-f02){.id-not .include-annotation}** - **[`https://doompdf.pages.dev/doom.pdf`{=html}](https://doompdf.pages.dev/doom.pdf){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** - **[`https://dspace.mit.edu/bitstream/handle/1721.1/6486/AIM-1026a.pdf?sequence=2`{=html}](https://dspace.mit.edu/bitstream/handle/1721.1/6486/AIM-1026a.pdf?sequence=2){.id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** - **[`https://dwarffortresswiki.org/index.php/v0.31:Creature_logic`{=html}](https://dwarffortresswiki.org/index.php/v0.31:Creature_logic){.id-not .include-annotation}** ::: aux-links-transclude-file ::: collapse **View External Link**: [`https://dwarffortresswiki.org/index.php/v0.31:Creature_logic`](https://dwarffortresswiki.org/index.php/v0.31:Creature_logic){.id-not .link-annotated-not .include-content .include-lazy} ::: ::: - **[`https://eli.thegreenplace.net/2023/demystifying-tuppers-formula/`{=html}](https://eli.thegreenplace.net/2023/demystifying-tuppers-formula/){.id-not .include-annotation}** ::: aux-links-transclude-file ::: collapse **View External Link**: [`https://eli.thegreenplace.net/2023/demystifying-tuppers-formula/`](https://eli.thegreenplace.net/2023/demystifying-tuppers-formula/){.id-not .link-annotated-not .include-content .include-lazy} ::: ::: - **[`https://eprints.soton.ac.uk/339763/1/chap40.pdf`{=html}](https://eprints.soton.ac.uk/339763/1/chap40.pdf){.link-annotated-partial .id-not .include-annotation link-icon="pdf" link-icon-type="svg" link-icon-color="#f40f02"}** - **[`https://esolangs.org/wiki/Folders`{=html}](https://esolangs.org/wiki/Folders){.link-annotated-partial .id-not .include-annotation}** - **[`https://github.com/MattCozendey/doom-console-log`{=html}](https://github.com/MattCozendey/doom-console-log){.id-not .include-annotation link-icon="github" link-icon-type="svg"}** - **[`https://github.com/harfbuzz/harfbuzz-wasm-examples?tab=readme-ov-file#hieroglyphs`{=html}](https://github.com/harfbuzz/harfbuzz-wasm-examples?tab=readme-ov-file#hieroglyphs){.id-not .include-annotation link-icon="github" link-icon-type="svg"}** ::: aux-links-transclude-file ::: collapse **View HTML**: [`/doc/www/github.com/2421208aea4b9b17d14bc06492a8e6a2b8b19bd1.html#hieroglyphs`](/doc/www/github.com/2421208aea4b9b17d14bc06492a8e6a2b8b19bd1.html#hieroglyphs){.id-not .link-annotated-not .include-content .include-lazy link-icon="github" link-icon-type="svg"} ::: ::: - **[`https://github.com/mame/radiation-hardened-quine`{=html}](https://github.com/mame/radiation-hardened-quine){.id-not .include-annotation link-icon="github" link-icon-type="svg"}** - **[`https://github.com/mgarciaisaia/JavaScript-Is-Weird-as-a-compressor`{=html}](https://github.com/mgarciaisaia/JavaScript-Is-Weird-as-a-compressor){.id-not .include-annotation link-icon="github" link-icon-type="svg"}** - **[`https://iter.ca/post/gh-sig-pwn/`{=html}](https://iter.ca/post/gh-sig-pwn/){.link-annotated-partial .id-not .include-annotation}** - **[`https://linusakesson.net/programming/symlinks/index.php`{=html}](https://linusakesson.net/programming/symlinks/index.php){.id-not .include-annotation}** - **[`https://meatfighter.com/tetromino-computer/index.html`{=html}](https://meatfighter.com/tetromino-computer/index.html){.link-annotated-partial .id-not .include-annotation}** - **[`https://nlp.stanford.edu/~johnhew/rnns-hierarchy.html`{=html}](https://nlp.stanford.edu/~johnhew/rnns-hierarchy.html){.link-annotated-partial .id-not .include-annotation}** - **[`https://nostalgebraist.tumblr.com/post/740164510909890560/information-flow-in-transformers`{=html}](https://nostalgebraist.tumblr.com/post/740164510909890560/information-flow-in-transformers){.link-annotated-partial .id-not .include-annotation link-icon="tumblr" link-icon-type="svg" link-icon-color="#001935"}** - **[`https://portswigger.net/blog/tic-tac-toe-in-html`{=html}](https://portswigger.net/blog/tic-tac-toe-in-html){.id-not .include-annotation}** - **[`https://scottaaronson.blog/?p=9979`{=html}](https://scottaaronson.blog/?p=9979 "Aaronson 2026"){.link-modified-recently .link-annotated-partial .id-not .include-annotation link-icon="SA" link-icon-type="text,sans" link-icon-color="#4181b7"}** - **[`https://srush.github.io/raspy/`{=html}](https://srush.github.io/raspy/){.link-annotated-partial .id-not .include-annotation}** - **[`https://thaliaarchi.github.io/coq-turing-typeclass/`{=html}](https://thaliaarchi.github.io/coq-turing-typeclass/){.id-not .include-annotation}** ::: aux-links-transclude-file ::: collapse **View External Link**: [`https://thaliaarchi.github.io/coq-turing-typeclass/`](https://thaliaarchi.github.io/coq-turing-typeclass/){.id-not .link-annotated-not .include-content .include-lazy} ::: ::: - **[`https://tromp.github.io/cl/diagrams.html`{=html}](https://tromp.github.io/cl/diagrams.html){.link-annotated-partial .id-not .include-annotation}** - **[`https://web.archive.org/web/20170815022856/http://acarol.woz.org/LegoDifferenceEngine.html`{=html}](https://web.archive.org/web/20170815022856/http://acarol.woz.org/LegoDifferenceEngine.html){.link-annotated-partial .id-not .include-annotation link-icon="internet-archive" link-icon-type="svg"}** - **[`https://willhbr.net/2024/03/15/making-a-compiler-to-prove-tmux-is-turing-complete/`{=html}](https://willhbr.net/2024/03/15/making-a-compiler-to-prove-tmux-is-turing-complete/){.id-not .include-annotation}** - **[`https://www.amirrorclear.net/academic/ideas/simulation/index.html`{=html}](https://www.amirrorclear.net/academic/ideas/simulation/index.html){.id-not .include-annotation}** - **[`https://www.bamsoftware.com/hacks/deflate.html`{=html}](https://www.bamsoftware.com/hacks/deflate.html){.id-not .include-annotation}** - **[`https://www.drmoron.org/posts/mechanical-computer/`{=html}](https://www.drmoron.org/posts/mechanical-computer/){.link-annotated-partial .id-not .include-annotation}** - **[`https://www.lesswrong.com/posts/HkghiK6Rt35nbgwKA/hard-coding-neural-computation`{=html}](https://www.lesswrong.com/posts/HkghiK6Rt35nbgwKA/hard-coding-neural-computation){.id-not .include-annotation link-icon="LW" link-icon-type="text" link-icon-color="#7faf83"}** ::: aux-links-transclude-file ::: collapse **View External Link**: [`https://www.lesswrong.com/posts/HkghiK6Rt35nbgwKA/hard-coding-neural-computation`](https://www.lesswrong.com/posts/HkghiK6Rt35nbgwKA/hard-coding-neural-computation){.id-not .link-annotated-not .include-content .include-lazy link-icon="LW" link-icon-type="text" link-icon-color="#7faf83"} ::: ::: - **[`https://www.lesswrong.com/posts/K7AyY8LMrcKhwfbyj/no-really-attention-is-all-you-need-attention-can-do`{=html}](https://www.lesswrong.com/posts/K7AyY8LMrcKhwfbyj/no-really-attention-is-all-you-need-attention-can-do){.link-annotated-partial .id-not .include-annotation link-icon="LW" link-icon-type="text" link-icon-color="#7faf83"}** - **[`https://www.lesswrong.com/posts/QNQuWB3hS5FrGp5yZ/programmatic-backdoors-dnns-can-use-sgd-to-run-arbitrary`{=html}](https://www.lesswrong.com/posts/QNQuWB3hS5FrGp5yZ/programmatic-backdoors-dnns-can-use-sgd-to-run-arbitrary){.link-annotated-partial .id-not .include-annotation link-icon="LW" link-icon-type="text" link-icon-color="#7faf83"}** - **[`https://www.lesswrong.com/posts/bC5xd7wQCnTDw7Kyx/getting-up-to-speed-on-the-speed-prior-in-2022`{=html}](https://www.lesswrong.com/posts/bC5xd7wQCnTDw7Kyx/getting-up-to-speed-on-the-speed-prior-in-2022){.id-not .include-annotation link-icon="LW" link-icon-type="text" link-icon-color="#7faf83"}** ::: aux-links-transclude-file ::: collapse **View External Link**: [`https://www.lesswrong.com/posts/bC5xd7wQCnTDw7Kyx/getting-up-to-speed-on-the-speed-prior-in-2022`](https://www.lesswrong.com/posts/bC5xd7wQCnTDw7Kyx/getting-up-to-speed-on-the-speed-prior-in-2022){.id-not .link-annotated-not .include-content .include-lazy link-icon="LW" link-icon-type="text" link-icon-color="#7faf83"} ::: ::: - **[`https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4585175/`{=html}](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4585175/){.id-not .include-annotation link-icon="nlm-ncbi" link-icon-type="svg" link-icon-color="#20558a"}** - **[`https://www.pypy.org/posts/2018/09/the-first-15-years-of-pypy-3412615975376972020.html#why-did-we-abandon-partial-evaluation`{=html}](https://www.pypy.org/posts/2018/09/the-first-15-years-of-pypy-3412615975376972020.html#why-did-we-abandon-partial-evaluation){.id-not .include-annotation}** ::: aux-links-transclude-file ::: collapse **View HTML**: [`/doc/www/www.pypy.org/99ddb5cdb94272b117d779153234a77b05980897.html#why-did-we-abandon-partial-evaluation`](/doc/www/www.pypy.org/99ddb5cdb94272b117d779153234a77b05980897.html#why-did-we-abandon-partial-evaluation){.id-not .link-annotated-not .include-content .include-lazy link-icon="internet-archive" link-icon-type="svg"} ::: ::: - **[`https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/`{=html}](https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/){.link-annotated-partial .id-not .include-annotation link-icon="quanta" link-icon-type="svg" link-icon-color="#ff8600"}** - **[`https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/`{=html}](https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/){.id-not .include-annotation link-icon="quanta" link-icon-type="svg" link-icon-color="#ff8600"}** - **[`https://www.quantamagazine.org/in-new-paradox-black-holes-appear-to-evade-heat-death-20230606/`{=html}](https://www.quantamagazine.org/in-new-paradox-black-holes-appear-to-evade-heat-death-20230606/){.id-not .include-annotation link-icon="quanta" link-icon-type="svg" link-icon-color="#ff8600"}** - **[`https://www.quantamagazine.org/the-beautiful-intelligence-of-bacteria-and-other-microbes-20171113/`{=html}](https://www.quantamagazine.org/the-beautiful-intelligence-of-bacteria-and-other-microbes-20171113/){.id-not .include-annotation link-icon="quanta" link-icon-type="svg" link-icon-color="#ff8600"}** - **[`https://www.quantamagazine.org/the-mysterious-math-of-billiards-tables-20240215/`{=html}](https://www.quantamagazine.org/the-mysterious-math-of-billiards-tables-20240215/){.link-annotated-partial .id-not .include-annotation link-icon="quanta" link-icon-type="svg" link-icon-color="#ff8600"}** - **[`https://www.reddit.com/r/programming/comments/1tjznwf/how_to_call_an_api_from_an_email/`{=html}](https://www.reddit.com/r/programming/comments/1tjznwf/how_to_call_an_api_from_an_email/){.link-annotated-partial .id-not .include-annotation link-icon="reddit" link-icon-type="svg" link-icon-color="#ff4500"}** - **[`https://www.reenigne.org/blog/8088-pc-speaker-mod-player-how-its-done/`{=html}](https://www.reenigne.org/blog/8088-pc-speaker-mod-player-how-its-done/){.link-annotated-partial .id-not .include-annotation}** - **[`https://x.com/CFGeek/status/1768024040487453169`{=html}](https://x.com/CFGeek/status/1768024040487453169 "Foster 2026"){.link-annotated-partial .id-not .include-annotation link-icon="twitter" link-icon-type="svg" link-icon-color="#1da1f2"}** - **[`https://x.com/prerationalist/status/1612872812414308403`{=html}](https://x.com/prerationalist/status/1612872812414308403 "prerationalist 2026"){.link-annotated-partial .id-not .include-annotation link-icon="twitter" link-icon-type="svg" link-icon-color="#1da1f2"}** - **[`https://xorshammer.com/2010/02/17/quantish-physics-a-discrete-model-of-quantum-physics/`{=html}](https://xorshammer.com/2010/02/17/quantish-physics-a-discrete-model-of-quantum-physics/){.id-not .include-annotation}** # Bibliography {#link-bibliography-section} 1. `https://arxiv.org/abs/2503.24187`: [`“NeuRaLaTeX: A Machine Learning Library Written in Pure LaTeX”`{=html}](https://arxiv.org/abs/2503.24187 "'NeuRaLaTeX: A machine learning library written in pure LaTeX', Gardner et al 2025"){#gardner-et-al-2025 .link-annotated}, [James A. D. Gardner, Will Rowan, William A. P. Smith]{.author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Farxiv.org%252Fabs%252F2503.24187.html "Directory-tag link-bibliography for link https://arxiv.org/abs/2503.24187"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 2. `https://arxiv.org/abs/2502.17779`: [`“Simulating Time With Square-Root Space”`{=html}](https://arxiv.org/abs/2502.17779 "'Simulating Time With Square-Root Space', Williams 2025"){#williams-2025 .link-annotated}, [R. Ryan Williams]{.author .cite-author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Farxiv.org%252Fabs%252F2502.17779.html "Directory-tag link-bibliography for link https://arxiv.org/abs/2502.17779"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 3. `https://arxiv.org/abs/2410.18077#deepmind`: [`“ALTA: Compiler-Based Analysis of Transformers”`{=html}](https://arxiv.org/abs/2410.18077#deepmind "'ALTA: Compiler-Based Analysis of Transformers', Shaw et al 2024"){#shaw-et-al-2024 .link-annotated}, [Peter Shaw, James Cohan, Jacob Eisenstein[, Kenton Lee, [Jonathan Berant](https://www.cs.tau.ac.il//~joberant/ "Jonathan Berant"){.link-annotated-partial .id-not}, Kristina Toutanova]{.collapse}]{.author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Farxiv.org%252Fabs%252F2410.18077%2523deepmind.html "Directory-tag link-bibliography for link https://arxiv.org/abs/2410.18077#deepmind"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 4. `https://arxiv.org/abs/2410.03170#deepmind`: [`“Autoregressive Large Language Models Are Computationally Universal”`{=html}](https://arxiv.org/abs/2410.03170#deepmind "'Autoregressive Large Language Models are Computationally Universal', Schuurmans et al 2024"){#schuurmans-et-al-2024 .link-annotated}, [Dale Schuurmans, Hanjun Dai, Francesco Zanini]{.author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Farxiv.org%252Fabs%252F2410.03170%2523deepmind.html "Directory-tag link-bibliography for link https://arxiv.org/abs/2410.03170#deepmind"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 5. `https://arxiv.org/abs/2408.08292`: [`“Optimization by Decoded Quantum Interferometry”`{=html}](https://arxiv.org/abs/2408.08292 "'Optimization by Decoded Quantum Interferometry', Jordan et al 2024"){#jordan-et-al-2024 .link-annotated}, [Stephen P. Jordan, Noah Shutty, Mary Wootters[, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Ryan Babbush]{.collapse}]{.author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Farxiv.org%252Fabs%252F2408.08292.html "Directory-tag link-bibliography for link https://arxiv.org/abs/2408.08292"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 6. `https://arxiv.org/abs/2406.05564`: [`“Automata Extraction from Transformers”`{=html}](https://arxiv.org/abs/2406.05564 "'Automata Extraction from Transformers', Zhang et al 2024"){#zhang-et-al-2024 .link-annotated}, [Yihao Zhang, Zeming Wei, Meng Sun]{.author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Farxiv.org%252Fabs%252F2406.05564.html "Directory-tag link-bibliography for link https://arxiv.org/abs/2406.05564"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 7. `https://arxiv.org/abs/2402.09963`: [`“Why Are Sensitive Functions Hard for Transformers?”`{=html}](https://arxiv.org/abs/2402.09963 "'Why are Sensitive Functions Hard for Transformers?', Hahn & Rofin 2024"){#hahn-rofin-2024 .link-annotated}, [[Michael Hahn](https://en.wikipedia.org/wiki/Michael_Hahn "Michael Hahn"){.id-not}, Mark Rofin]{.author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Farxiv.org%252Fabs%252F2402.09963.html "Directory-tag link-bibliography for link https://arxiv.org/abs/2402.09963"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 8. `https://arxiv.org/abs/2305.17872`: [`“Universal Mechanical Polycomputation in Granular Matter”`{=html}](https://arxiv.org/abs/2305.17872 "'Universal Mechanical Polycomputation in Granular Matter', Parsa et al 2023"){#parsa-et-al-2023 .link-annotated}, [Atoosa Parsa, Sven Witthaus, Nidhi Pashine[, Corey S. O'Hern, Rebecca Kramer-Bottiglio, [Josh Bongard](https://en.wikipedia.org/wiki/Josh_Bongard "Josh Bongard"){.id-not}]{.collapse}]{.author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Farxiv.org%252Fabs%252F2305.17872.html "Directory-tag link-bibliography for link https://arxiv.org/abs/2305.17872"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 9. `https://arxiv.org/abs/2208.01066`: [`“What Can Transformers Learn In-Context? A Case Study of Simple Function Classes”`{=html}](https://arxiv.org/abs/2208.01066 "'What Can Transformers Learn In-Context? A Case Study of Simple Function Classes', Garg et al 2022"){#garg-et-al-2022 .link-annotated}, [Shivam Garg, Dimitris Tsipras, [Percy Liang](https://cs.stanford.edu/~pliang/ "Percy Liang"){.link-annotated-partial .id-not}, Gregory Valiant]{.author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Farxiv.org%252Fabs%252F2208.01066.html "Directory-tag link-bibliography for link https://arxiv.org/abs/2208.01066"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 10. `https://arxiv.org/abs/2106.06981`: [`“RASP: Thinking Like Transformers”`{=html}](https://arxiv.org/abs/2106.06981 "'RASP: Thinking Like Transformers', Weiss et al 2021"){#weiss-et-al-2021 .link-annotated}, [Gail Weiss, [Yoav Goldberg](https://scholar.google.com/citations?user=0rskDKgAAAAJ "Yoav Goldberg"){.id-not}, Eran Yahav]{.author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Farxiv.org%252Fabs%252F2106.06981.html "Directory-tag link-bibliography for link https://arxiv.org/abs/2106.06981"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 11. `https://arxiv.org/abs/2012.12828`: [`“Constructing Turing Complete Euler Flows in Dimension 3”`{=html}](https://arxiv.org/abs/2012.12828 "'Constructing Turing complete Euler flows in dimension 3', Cardona et al 2020"){#cardona-et-al-2020 .link-annotated}, [[Robert Cardona](https://en.wikipedia.org/wiki/Robert_Cardona "Robert Cardona"){.id-not}, [Eva Miranda](https://en.wikipedia.org/wiki/Eva_Miranda "Eva Miranda"){.id-not}, Daniel Peralta-Salas, Francisco Presas]{.author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Farxiv.org%252Fabs%252F2012.12828.html "Directory-tag link-bibliography for link https://arxiv.org/abs/2012.12828"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 12. `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”`{=html}](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', Pavlus 2020"){#pavlus-2020 .link-annotated}, [John Pavlus]{.author .cite-author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Fwww.quantamagazine.org%252Fhow-the-slowest-computer-programs-illuminate-maths-fundamental-limits-20201210%252F.html "Directory-tag link-bibliography for link https://www.quantamagazine.org/how-the-slowest-computer-programs-illuminate-maths-fundamental-limits-20201210/"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 13. `2019-aaronson.pdf`: [`“The Busy Beaver Frontier”`{=html}](/doc/cs/computable/2019-aaronson.pdf "'The Busy Beaver Frontier', Aaronson 2019"){#aaronson-2019 .link-annotated}, [[Scott Aaronson](https://en.wikipedia.org/wiki/Scott_Aaronson "Scott Aaronson"){.link-annotated-partial .id-not}]{.author .cite-author} [[link-bibliography](/metadata/annotation/link-bibliography/%252Fdoc%252Fcs%252Fcomputable%252F2019-aaronson.pdf.html "Directory-tag link-bibliography for link /doc/cs/computable/2019-aaronson.pdf"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 14. `https://www.cs.dartmouth.edu/~sergey/wm/`: [`“What Are Weird Machines?”`{=html}](https://www.cs.dartmouth.edu/~sergey/wm/ "'What are Weird Machines?', Bratus 2015"){#bratus-2015 .link-annotated}, [Sergey Bratus]{.author .cite-author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Fwww.cs.dartmouth.edu%252F~sergey%252Fwm%252F.html "Directory-tag link-bibliography for link https://www.cs.dartmouth.edu/~sergey/wm/"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 15. `2013-conway.pdf`: [`“On Unsettleable Arithmetical Problems”`{=html}](/doc/cs/computable/2013-conway.pdf "'On Unsettleable Arithmetical Problems', Conway 2013"){#conway-2013 .link-annotated}, [[John H. Conway](https://en.wikipedia.org/wiki/John_H._Conway "John H. Conway"){.id-not}]{.author .cite-author} [[link-bibliography](/metadata/annotation/link-bibliography/%252Fdoc%252Fcs%252Fcomputable%252F2013-conway.pdf.html "Directory-tag link-bibliography for link /doc/cs/computable/2013-conway.pdf"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 16. `2006-walker.pdf`: [`“Static Typing for a Faulty Lambda Calculus”`{=html}](/doc/cs/computable/2006-walker.pdf "'Static typing for a faulty lambda calculus', Walker et al 2006"){#walker-et-al-2006 .link-annotated}, [David Walker, [Lester Mackey](https://en.wikipedia.org/wiki/Lester_Mackey "Lester Mackey"){.id-not}, Jay Ligatti[, George A. Reis, David I. August]{.collapse}]{.author} [[link-bibliography](/metadata/annotation/link-bibliography/%252Fdoc%252Fcs%252Fcomputable%252F2006-walker.pdf.html "Directory-tag link-bibliography for link /doc/cs/computable/2006-walker.pdf"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 17. `https://www.ncbi.nlm.nih.gov/pmc/articles/PMC18139/`: [`“P/NP, and the Quantum Field Computer”`{=html}](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC18139/ "'P/NP, and the quantum field computer', Freedman 1998"){#freedman-1998 .link-annotated}, [M H. Freedman]{.author .cite-author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Fwww.ncbi.nlm.nih.gov%252Fpmc%252Farticles%252FPMC18139%252F.html "Directory-tag link-bibliography for link https://www.ncbi.nlm.nih.gov/pmc/articles/PMC18139/"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 18. `https://www.sciencedirect.com/science/article/pii/002200009390001D`: [`“Threshold Circuits of Bounded Depth”`{=html}](https://www.sciencedirect.com/science/article/pii/002200009390001D "'Threshold circuits of bounded depth', Hajnal et al 1993"){#hajnal-et-al-1993 .link-annotated}, [[András Hajnal](https://en.wikipedia.org/wiki/Andr%C3%A1s_Hajnal "András Hajnal"){.id-not}, Wolfgang Maass, Pavel Pudlák[, [Mario Szegedy](https://en.wikipedia.org/wiki/Mario_Szegedy "Mario Szegedy"){.id-not}, György Turán]{.collapse}]{.author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Fwww.sciencedirect.com%252Fscience%252Farticle%252Fpii%252F002200009390001D.html "Directory-tag link-bibliography for link https://www.sciencedirect.com/science/article/pii/002200009390001D"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 19. `1990-moore.pdf`: [`“Unpredictability and Undecidability in Dynamical Systems”`{=html}](/doc/cs/computable/1990-moore.pdf "'Unpredictability and undecidability in dynamical systems', Moore 1990"){#moore-1990 .link-annotated}, [[Cristopher Moore](https://en.wikipedia.org/wiki/Cristopher_Moore "Cristopher Moore"){.id-not}]{.author .cite-author} [[link-bibliography](/metadata/annotation/link-bibliography/%252Fdoc%252Fcs%252Fcomputable%252F1990-moore.pdf.html "Directory-tag link-bibliography for link /doc/cs/computable/1990-moore.pdf"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block} 20. `https://esolangs.org/wiki/ByteByteJump`: [`“ByteByteJump”`{=html}](https://esolangs.org/wiki/ByteByteJump "'ByteByteJump', Wiki 2026"){#_0z48JnGx .link-annotated}, [Esolang Wiki]{.author .cite-author} [[link-bibliography](/metadata/annotation/link-bibliography/https%253A%252F%252Fesolangs.org%252Fwiki%252FByteByteJump.html "Directory-tag link-bibliography for link https://esolangs.org/wiki/ByteByteJump"){.id-not .include-even-when-collapsed}]{.collapse .tag-index-link-bibliography-block}