“‘Computability’ Tag”,2019-11-13 ():
![]()
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”, et al 2024
- “Computer Scientists Combine Two ‘Beautiful’ Proof Methods [ZK + PCP]”
- “Hypercomputation without Bothering the Cactus People: Software Development for the DMT Headspace”, 2024
- “Tiling With 3 Polygons Is Undecidable”, 2024
- “On the Complexity of Neural Computation in Superposition”, 2024
- “Quantum Convolutional Neural Networks Are (Effectively) Classically Simulable”, et al 2024
- “Optimization by Decoded Quantum Interferometry”, et al 2024
- “The Illusion of State in State-Space Models”, et al 2024
- “Chain-Of-Thought Empowers Transformers to Solve Inherently Serial Problems”, et al 2024
- “Why Are Sensitive Functions Hard for Transformers?”, 2024
- “Linux/4004: Slowly Booting Full Linux on the Intel 4004 CPU for Fun, Art, and Absolutely No Profit”, 2024
- “Can a Transformer Represent a Kalman Filter?”, 2023
- “Masked Hard-Attention Transformers and Boolean RASP Recognize Exactly the Star-Free Languages”, et al 2023
- “The Expressive Power of Transformers With Chain-Of-Thought”, 2023
- “Learning Transformer Programs”, et al 2023
- “Universal Mechanical Polycomputation in Granular Matter”, et al 2023
- “Towards Revealing the Mystery behind Chain-Of-Thought: A Theoretical Perspective”, et al 2023
- “Looped Transformers As Programmable Computers”, et al 2023
- “Tighter Bounds on the Expressivity of Transformer Encoders”, et al 2023
- “Memory Augmented Large Language Models Are Computationally Universal”, 2023
- “Control of Cell Proliferation by Memories of Mitosis”, et al 2022
- “Characterizing Intrinsic Compositionality in Transformers With Tree Projections”, et al 2022
- “Transformers Learn Shortcuts to Automata”, et al 2022
- “Transformers Implement First-Order Logic With Majority Quantifiers”, 2022
- “Python Type Hints Are Turing Complete”, 2022
- “What Can Transformers Learn In-Context? A Case Study of Simple Function Classes”, et al 2022
- “Perceptein: A Synthetic Protein-Level Neural Network in Mammalian Cells”, et al 2022
- “Neural Networks and the Chomsky Hierarchy”, et al 2022
- “Log-Precision Transformers Are Constant-Depth Uniform Threshold Circuits”, 2022
- “Verifiable Quantum Advantage without Structure”, 2022
- “An RNA-Based Theory of Natural Universal Computation”, 2022
- “Overcoming a Theoretical Limitation of Self-Attention”, 2022
- “A Deep Dive into an NSO Zero-Click IMessage Exploit: Remote Code Execution”, Beer & Groß 2021
- “Minimum Description Length Recurrent Neural Networks”, et al 2021
- “RASP: Thinking Like Transformers”, et al 2021
- “Turing Completeness and Sid Meier’s Civilization”, 2021
- “Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine”, 2021
- “Sensitivity As a Complexity Measure for Sequence Classification Tasks”, et al 2021
- “Gene Regulatory Networks Exhibit Several Kinds of Memory: Quantification of Memory in Biological and Random Transcriptional Networks”, et al 2021
- “Constructing Turing Complete Euler Flows in Dimension 3”, 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”, 2020
- “Remembering John Conway’s FRACTRAN, a Ridiculous, yet Surprisingly Deep Language”, 2020
- “Magic: the Gathering Is As Hard As Arithmetic”, 2020
- “Recursed Is Not Recursive: A Jarring Result”, et al 2020
- “The Busy Beaver Frontier”, 2019
- “Magic: The Gathering Is Turing Complete”, et al 2019
- “On the Turing Completeness of Modern Neural Network Architectures”, et al 2019
- “Deciphering the Molecular Mechanism Underpinning Phage Arbitrium Communication Systems”, et al 2019
- “Adversarial Reprogramming of Neural Networks”, et al 2018
- “Mechanical Computing System Using Only One Physical Object-qb Cube”, 2018
- “Weird Machines, Exploitability, and Provable Unexploitability”, 2017
- “Communication between Viruses Guides Lysis-Lysogeny Decisions”, et al 2017
- “Java Generics Are Turing Complete”, 2016
- “A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory”, 2016
- Advances in Physarum Machines: Sensing and Computing With Slime Mould, 2016
- “On Having No Head: Cognition throughout Biological Systems”, 2016
- “Undecidability of the Spectral Gap”, et al 2015
- “What Are Weird Machines?”, 2015
- “Braid Is Undecidable”, 2014
- “Teaching Mario to Play Pong and Snake Through Innumerable Exploits”
- “Mathematics in the Age of the Turing Machine”, 2013
- “On Unsettleable Arithmetical Problems”, 2013
- “The Page-Fault Weird Machine: Lessons in Instruction-Less Computation”, 2013
- “Using Routers to Build Logic Circuits: How Powerful Is BGP?”, 2013
- “Is the Network Turing-Complete? EPFL Technical 187131”, 2013
- “Turning Oscillations into Opportunities: Lessons from a Bacterial Decision Gate”, et al 2013
- “The Configuration Complexity Clock”, 2012
- “Robust Soldier Crab Ball Gate”, et al 2012
- “Exploitation and State Machines: Programming the ‘Weird Machine’ Revisited”, 2011
- “Quantum Computation With Devices Whose Contents Are Never Read”, et al 2010
- “Ant-Based Computing”, 2009
- “Physics, Topology, Logic and Computation: A Rosetta Stone”, 2009
- “High Performance SQL With PostgreSQL 8.4: Lists and Recursion and Trees, Oh My!”, 2009
- “Deciding Fate in Adverse Times: Sporulation and Competence in Bacillus Subtilis”, et al 2009
- “Small Universal Turing Machines”, 2008
- “Omega Monad: Enumerating a Context-Free Language”, 2008
- “Perl Cannot Be Parsed: A Formal Proof”, 2008
- “Algorithmic Self-Assembly of DNA”, 2008
- “On Universal Prediction and Bayesian Confirmation”, 2007
- “Infinite Sets That Admit Fast Exhaustive Search”, 2007
- “Infinite Versions of Minesweeper Are Turing Complete”, 2007
- “On the Computational Power of Threshold Circuits With Sparse Activity”, et al 2006
- “No Quantum Advantage for Nonlocal Computation”, et al 2006
- “Static Typing for a Faulty Lambda Calculus”, et al 2006
- Good and Real: Demystifying Paradoxes from Physics to Ethics, 2006
- “A Box, Darkly: Obfuscation, Weird Languages, and Code Esthetics”, 2005
- “The Halting Problem Is Decidable on a Set of Asymptotic Probability One”, 2005
- “A Simple Proof for the Turing-Completeness of XSLT and XQuery”, 2004
- “Philosophical Problems in Logic § Ultrafinitism”, 2002 (page 4)
- “Analytic and Algorithmic Solution of Random Satisfiability Problems”, et al 2002
- “The Fastest and Shortest Algorithm for All Well-Defined Problems”, 2002
- “Sendmail As a Turing Machine”, 2000
- “P/NP, and the Quantum Field Computer”, 1998
- “Limitations of Noisy Reversible Computation”, et al 1996
- “A Personal View of Average-Case Complexity”, 1995
- “Threshold Circuits of Bounded Depth”, et al 1993
- “Time Travel and Computing”, 1991
- “A Differentiation Primitive for Extended Λ–calculus”, 1988
- “FRACTRAN: A Simple Universal Programming Language for Arithmetic”, 1987
- “Conservative Logic”, 1982
- “Bi-Continuous Extensions of Invertible Combinatorial Functions”, 1981
- “Unpredictable Iterations”, 1972
- “FLODAC—A Pure Fluid Digital Computer”, et al 1964
- “On Non-Computable Functions”, 1962
- “‘Computational Complexity of Air Travel Planning’, De 2003 [ITA Software]”
- “Universal Search § OOPS and Other Incremental Variations”
- “Computing With Time: Microarchitectural Weird Machines”
- “How Exploits Impact Computer Science Theory”
- “ByteByteJump”, 2024
- “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+mkdirIs Turing Complete (retracted)”, 2024- “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
- Wikipedia
- Miscellaneous
- Bibliography