“‘Computability’ Tag”,2019-11-13 (math)⁠:

Bibliography for tag cs/computable, most recent first: 128 annotations & 54 links (parent).

• See Also
• Links
  • “Ask, and It Shall Be Given: Turing Completeness of Prompting”, Qiu et al 2024
  • “Computer Scientists Combine Two ‘Beautiful’ Proof Methods [ZK + PCP]”
  • “Hypercomputation without Bothering the Cactus People: Software Development for the DMT Headspace”, Flipper2024
  • “Tiling With 3 Polygons Is Undecidable”, Demaine & Langerman2024
  • “On the Complexity of Neural Computation in Superposition”, Adler & Shavit2024
  • “Quantum Convolutional Neural Networks Are (Effectively) Classically Simulable”, Bermejo et al 2024
  • “Optimization by Decoded Quantum Interferometry”, Jordan et al 2024
  • “The Illusion of State in State-Space Models”, Merrill et al 2024
  • “Chain-Of-Thought Empowers Transformers to Solve Inherently Serial Problems”, Li et al 2024
  • “Why Are Sensitive Functions Hard for Transformers?”, Hahn & Rofin2024
  • “Linux/4004: Slowly Booting Full Linux on the Intel 4004 CPU for Fun, Art, and Absolutely No Profit”, Grinberg2024
  • “Can a Transformer Represent a Kalman Filter?”, Goel & Bartlett2023
  • “Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly the Star-Free Languages”, Angluin et al 2023
  • “The Expressive Power of Transformers With Chain-Of-Thought”, Merrill & Sabharwal2023
  • “Learning Transformer Programs”, Friedman et al 2023
  • “Universal Mechanical Polycomputation in Granular Matter”, Parsa et al 2023
  • “Towards Revealing the Mystery behind Chain-Of-Thought: A Theoretical Perspective”, Feng et al 2023
  • “Looped Transformers As Programmable Computers”, Giannou et al 2023
  • “Tighter Bounds on the Expressivity of Transformer Encoders”, Chiang et al 2023
  • “Memory Augmented Large Language Models Are Computationally Universal”, Schuurmans2023
  • “Control of Cell Proliferation by Memories of Mitosis”, Meitinger et al 2022
  • “Characterizing Intrinsic Compositionality in Transformers With Tree Projections”, Murty et al 2022
  • “Transformers Learn Shortcuts to Automata”, Liu et al 2022
  • “Transformers Implement First-Order Logic With Majority Quantifiers”, Merrill & Sabharwal2022
  • “Python Type Hints Are Turing Complete”, Roth2022
  • “What Can Transformers Learn In-Context? A Case Study of Simple Function Classes”, Garg et al 2022
  • “Perceptein: A Synthetic Protein-Level Neural Network in Mammalian Cells”, Chen et al 2022
  • “Neural Networks and the Chomsky Hierarchy”, Delétang et al 2022
  • “Log-Precision Transformers Are Constant-Depth Uniform Threshold Circuits”, Merrill & Sabharwal2022
  • “Verifiable Quantum Advantage without Structure”, Yamakawa & Zhandry2022
  • “An RNA-Based Theory of Natural Universal Computation”, Akhlaghpour2022
  • “Overcoming a Theoretical Limitation of Self-Attention”, Chiang & Cholak2022
  • “A Deep Dive into an NSO Zero-Click IMessage Exploit: Remote Code Execution”, Beer & Groß 2021
  • “Minimum Description Length Recurrent Neural Networks”, Lan et al 2021
  • “RASP: Thinking Like Transformers”, Weiss et al 2021
  • “Turing Completeness and Sid Meier’s Civilization”, Wynter2021
  • “Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine”, Johnson2021
  • “Sensitivity As a Complexity Measure for Sequence Classification Tasks”, Hahn et al 2021
  • “Gene Regulatory Networks Exhibit Several Kinds of Memory: Quantification of Memory in Biological and Random Transcriptional Networks”, Biswas et al 2021
  • “Constructing Turing Complete Euler Flows in Dimension 3”, Cardona et al 2020
  • “How the Slowest Computer Programs Illuminate Math’s Fundamental Limits: The Goal of the ‘Busy Beaver’ Game Is to Find the Longest-Running Computer Program. Its Pursuit Has Surprising Connections to Some of the Most Profound Questions and Concepts in Mathematics”, Pavlus2020
  • “Remembering John Conway’s FRACTRAN, a Ridiculous, yet Surprisingly Deep Language”, Braithwaite2020
  • “Magic: the Gathering Is As Hard As Arithmetic”, Biderman2020
  • “Recursed Is Not Recursive: A Jarring Result”, Demaine et al 2020
  • “The Busy Beaver Frontier”, Aaronson2019
  • “Magic: The Gathering Is Turing Complete”, Churchill et al 2019
  • “On the Turing Completeness of Modern Neural Network Architectures”, Pérez et al 2019
  • “Deciphering the Molecular Mechanism Underpinning Phage Arbitrium Communication Systems”, Sol et al 2019
  • “Adversarial Reprogramming of Neural Networks”, Elsayed et al 2018
  • “Mechanical Computing System Using Only One Physical Object-qb Cube”, Vučinović2018
  • “Weird Machines, Exploitability, and Provable Unexploitability”, Dullien2017
  • “Communication between Viruses Guides Lysis-Lysogeny Decisions”, Erez et al 2017
  • “Java Generics Are Turing Complete”, Grigore2016
  • “A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory”, Yedidia & Aaronson2016
  • Advances in Physarum Machines: Sensing and Computing With Slime Mould, Adamatzky2016
  • “On Having No Head: Cognition throughout Biological Systems”, Baluška & Levin2016
  • “Undecidability of the Spectral Gap”, Cubitt et al 2015
  • “What Are Weird Machines?”, Bratus2015
  • “Braid Is Undecidable”, Hamilton2014
  • “Teaching Mario to Play Pong and Snake Through Innumerable Exploits”
  • “Mathematics in the Age of the Turing Machine”, Hales2013
  • “On Unsettleable Arithmetical Problems”, Conway2013
  • “The Page-Fault Weird Machine: Lessons in Instruction-Less Computation”, Bangert2013
  • “Using Routers to Build Logic Circuits: How Powerful Is BGP?”, Chiesa2013
  • “Is the Network Turing-Complete? EPFL Technical Report187131”, Peresini & Kostic2013
  • “Turning Oscillations into Opportunities: Lessons from a Bacterial Decision Gate”, Schultz et al 2013
  • “The Configuration Complexity Clock”, Hadlow2012
  • “Robust Soldier Crab Ball Gate”, Gunji et al 2012
  • “Exploitation and State Machines: Programming the ‘Weird Machine’ Revisited”, Flake2011
  • “Quantum Computation With Devices Whose Contents Are Never Read”, Yakaryilmaz et al 2010
  • “Ant-Based Computing”, Michael2009
  • “Physics, Topology, Logic and Computation: A Rosetta Stone”, Baez & Stay2009
  • “High Performance SQL With PostgreSQL 8.4: Lists and Recursion and Trees, Oh My!”, Fetter2009
  • “Deciding Fate in Adverse Times: Sporulation and Competence in Bacillus Subtilis”, Schultz et al 2009
  • “Small Universal Turing Machines”, Neary2008
  • “Omega Monad: Enumerating a Context-Free Language”, Palmer2008
  • “Perl Cannot Be Parsed: A Formal Proof”, Kegler2008
  • “Algorithmic Self-Assembly of DNA”, Winfree2008
  • “On Universal Prediction and Bayesian Confirmation”, Hutter2007
  • “Infinite Sets That Admit Fast Exhaustive Search”, Escardo2007
  • “Infinite Versions of Minesweeper Are Turing Complete”, Kate2007
  • “On the Computational Power of Threshold Circuits With Sparse Activity”, Uchizawa et al 2006
  • “No Quantum Advantage for Nonlocal Computation”, Linden et al 2006
  • “Static Typing for a Faulty Lambda Calculus”, Walker et al 2006
  • Good and Real: Demystifying Paradoxes from Physics to Ethics, Drescher2006
  • “A Box, Darkly: Obfuscation, Weird Languages, and Code Esthetics”, Mateas & Montfort2005
  • “The Halting Problem Is Decidable on a Set of Asymptotic Probability One”, Hamkins & Miasnikov2005
  • “A Simple Proof for the Turing-Completeness of XSLT and XQuery”, Kepser2004
  • “Philosophical Problems in Logic § Ultrafinitism”, Friedman2002 (page 4)
  • “Analytic and Algorithmic Solution of Random Satisfiability Problems”, Mezard et al 2002
  • “The Fastest and Shortest Algorithm for All Well-Defined Problems”, Hutter2002
  • “Sendmail As a Turing Machine”, Oleg2000
  • “P/NP, and the Quantum Field Computer”, Freedman1998
  • “Limitations of Noisy Reversible Computation”, Aharonov et al 1996
  • “A Personal View of Average-Case Complexity”, Impagliazzo1995
  • “Threshold Circuits of Bounded Depth”, Hajnal et al 1993
  • “Time Travel and Computing”, Moravec1991
  • “A Differentiation Primitive for Extended Λ–calculus”, Flaherty1988
  • “FRACTRAN: A Simple Universal Programming Language for Arithmetic”, Conway1987
  • “Conservative Logic”, Fredkin & Toffoli1982
  • “Bi-Continuous Extensions of Invertible Combinatorial Functions”, Toffoli1981
  • “Unpredictable Iterations”, Conway1972
  • “FLODAC—A Pure Fluid Digital Computer”, Gluskin et al 1964
  • “On Non-Computable Functions”, Rado1962
  • “‘Computational Complexity of Air Travel Planning’, De Marcken2003 [ITA Software]”
  • “Universal Search § OOPS and Other Incremental Variations”
  • “Computing With Time: Microarchitectural Weird Machines”
  • “How Exploits Impact Computer Science Theory”
  • “ByteByteJump”, Wiki2024
  • “Linear Bounded Automaton”
  • “OISC”
  • “Sudoku Solving in Python Packaging”
  • “MalbolgeLisp Is a LISP Interpreter Written in Malbolge. It’s (as of 2020 and 2021), the Most Advanced, Usable Malbolge Program Ever Created. It Supports Everything Lisps Generally Tend to Support (like cond, let, lambda, Etc…).”
  • “How I Did Relay Quine”
  • “Using SQL’s Turing Completeness to Build Tetris”
  • “C99 Doesn’t Need Function Bodies, Or, ‘VLAs Are Turing Complete’”
  • “Another New Record in Self-Cleaning Turing Machines”
  • “find + mkdir Is Turing Complete (retracted)”, Kako2024
  • “PEP 611: The One Million Limit”
  • “Choon Programming Language”
  • “Rosser’s Theorem via Turing Machines”
  • “Busy Beaver(5) Is Now Proven to Be 47,176,870”
  • “Weird Machines HQ”
  • “OpenTTD Logic”
  • “The Infinity Machine”
  • Fontemon
  • “A Brief History of Liquid Computers”
  • “On The Turing Completeness of PowerPoint”
  • Sort By Magic
    • turing-completeness
    • viral-communication
    • computability
  • Wikipedia
• Miscellaneous
• Bibliography