8 ms·
A collection of things that are Turing-complete by accident (2013)
- Asdfbla 9y agoIt's very cool how such a level of computational power is so seemingly easy to reach. I guess it's not surprising if you consider how simple Turing machines themselves are, but I'm always amazed that this is really enough.
- vog 9y agoThe problem is exactly reverse: From a security and anaysis point of view, you want languages that do the job with the least possible power. And those are surprisingly hard to find. You start with simple and not too-powerful languages (rules systems, regexes, parsing stuff), note they are insufficient for some real-word use case, add one or two features, and bam!, that mess becomes turing complete.
- willtim 9y agoStrongly agree. With more constraints in the language, one gains greater power to reason. This is what the Ethereum creators are learning the hard way. I also think folks would be surprised with how much can be accomplished without Turing completeness. For example, merge sort can be implemented as a simple functional unfold, or "primitive corecursion" in a total language.
- vog 9y ago> With more constraints in the language, one gains greater power to reason. Not only that, but you can also apply more tools onto it, treating the code as data and having a chance to use that as input data for totally different purposes. Another classic example is structured text. If you want to aggregate facts from that, this is totally easy when the data is available in a simple JSON structure. If it is a simple HTML site, this is slightly more involved: you need to scrape the site and recognize irrelevant stuff ( navigation bars, tables only used for layouting, etc.). But if it is a blob of Flash code that happens to display the text in some shiny way, you are essentially becoming a reverse engineer, and your tool will almost certainly break apart with every change / new version of that structured text.
- cdancette 9y agoBecause the number of operations in a sort is bounded. You can perform any sorting algorithm without turning completeness because you don't need the while loop basically.
- pron 9y agoThis applies to virtually any algorithm with a known bound. Any such algorithm can be carried out by primitive recursive functions. However, contrary to folklore, this makes absolutely no difference in verification complexity (see my other comment https://news.ycombinator.com/item?id=16383436 https://news.ycombinator.com/item?id=16383436). This can be easily shown by noting that we can assume -- with no loss of generality -- that any program is primitive recursive by implicitly adding a counter to each and every loop/recursive call, that counts down from, say, 2^500, and halts the program if it ever reaches zero (in fact, this is much more limited than primitive recursive as we're happy with a constant bound). As the counter will never reach zero in our physical universe, there is no change in program semantics, and therefore we can assume that all programs are written in non-Turing-complete languages if that were to help us in any way. Alas, as my other comment shows, it doesn't in the least.
- pron 9y agoThis is a very common misconception. While Turing complete computational models "suffer" from the halting problem that makes arbitrary "reasoning" uncomputable, that is 1. not quite the problem that makes reasoning hard, and 2. that does not mean that reasoning in weaker models is feasible. 1. What makes reasoning hard is not quite the halting theorem as normally stated, but a generalization of it that's sometimes called "bounded halting", and was used in the proof of the time-hierarchy theorem, possibly the most important theorem in theoretical computer science. Bounded halting roughly states that it's impossible to know in under N steps whether an arbitrary program P would halt when operating on input X in fewer than N steps. A simple corollary also shows the impossibility of generalizing the program's operation from one input to another. In short, this theorem means that it's impossible to know what a program would do for any input any faster than running it for every input. It can roughly be stated as saying that the verification or "reasoning" complexity for a program with a state space S of size |S| is θ(|S|) (where theta is like big-O, except it roughly means "no more and no less than", whereas big-O means "no more than"). Most importantly, this theorem does not require the programming model to be Turing complete. For example, it applies directly -- using the same proof -- to programming models that only allow primitive recursive functions. 2. Even the simplest computational model -- the barely useful finite-state machine -- is already too complicated for arbitrary reasoning. Its verification complexity also happens to be θ(|S|) (but with a different proof than that of the bounded halting theorem), where |S| is usually at least exponential in the size of the program. In general it can very easily be shown that if your programming languages has nothing more than boolean variables and the ability to write loops of length of no more than 2 or, alternatively, it has subroutines even if they cannot be recursive and there are no first-class subroutines -- reasoning is also infeasible (it's PSPACE-complete) and you might as well be Turing complete, as that won't make the worst-case any harder in practice (it makes no difference if the worst case is truly infinite or "just" much longer than the expected lifespan of the universe). The above fact means it is provably impossible to create a programming language -- no matter how limited -- where every program would be easily verifiable. To make a language feasibly verifiable in all/most cases, its state space must grow slowly (polynomially) with program size; this means that not only must the programming model be weak (basically just FSM), but the language exceptionally inexpressive. Regular expressions are pretty much the farthest we can go, and even then some simple questions about regexps are infeasible (such as whether two regexps are equivalent; I believe that problem is PSPACE complete, even though there are heuristic algorithms that work in many instances). For further discussion and complete results, see my post: https://pron.github.io/posts/correctness-and-complexity https://pron.github.io/posts/correctness-and-complexity
- Gormisdomai 9y agoA nice reminder that not all Turing-Complete things were created equal. Programming anything using these is a nightmare. (Except maybe the template / type system examples - I hear that's a lot like programming in Haskell)
- trentmb 9y agohttps://en.wikipedia.org/wiki/Turing_tarpit?wprov=sfla1 https://en.wikipedia.org/wiki/Turing_tarpit?wprov=sfla1
- MaxBarraclough 9y agoIf you treat these things as source languages, sure. Surely the point is that this stuff is possible at all. If you really wanted to program something meaningful using BGP hacks, you could build a compiler.
- lmm 9y agoC++ templates are like programming in Haskell without a type system - all of the pain, none of the gain.
- crdoconnor 9y agoI consider this a reflection of https://en.wikipedia.org/wiki/Rule_of_least_power https://en.wikipedia.org/wiki/Rule_of_least_power
- joejev 9y agoWith enough wrapping, the templates can be okay to write. For example https://github.com/llllllllll/wired https://github.com/llllllllll/wired looks like a shitty lisp.
- BLanen 9y agoI want a Powerpoint LLVM compilation target.
- carlsborg 9y agoThe paper where they build logic gates with BGP is fascinating. Thanks for posting this. "In this paper, we answer computational complexity questions by unveiling a fundamental mapping between BGP configurations and logic circuits. Namely, we describe simple networks containing routers with elementary BGP configurations that simulate logic gates, clocks, and flip-flops, and we show how to interconnect them to simulate arbitrary logic circuits."
- nothis 9y ago>Super Mario World Okay, with some script... >Here is a video, where a human (not a script!) creates a playable Flappy Bird clone this way. Wait, what?!
- teamhappy 9y agoThe StarCraft community created a level editor and a scripting language around a buffer overflow in the game: http://0xeb.net/wp-content/uploads/2018/02/StarCraft_EUD_Emulator.pdf http://0xeb.net/wp-content/uploads/2018/02/StarCraft_EUD_Emu...
- kiwidrew 9y agoThat was fascinating. The amount of effort that Blizzard went through to "emulate" the original buffer overflow is ridiculous. Also the mod community's epScript compiler is itself a very clever feat, especially its use of self-modifying "code".
- userbinator 9y agoIt's a human following a script... which is still impressive nonetheless, even if for nothing other than the patience and planning required to do something like this.
- oneeyedpigeon 9y agoI can't even begin to fathom how someone would be able to do this. Wouldn't they have to perform many (100s?) pixel-perfect actions in order to get everything exactly as intended?
- lifthrasiir 9y agoHe starts by writing dozens of bytes to check if the written bytes are correct or not (along with other side effects for bootstrapping), and some more to see the exact bytes to be written before applying them. And then finally 300+ actual bytes are written. Not as difficult overall, but initial steps would still require extreme patience.
- 0xdada 9y agoIsn't the bug in Super Mario just exposing the underlying system's Turing Completeness?
- bena 9y agoYeah, I don't think arbitrary code execution counts as the game itself being "Turing complete".
- OscarCunningham 9y agoOn the other hand, what is "Super Mario World" if not the game as it runs on the SNES?
- euyyn 9y agoYeah but it's a different kind of fuckup, designing a system with a vulnerability that lets you "escape" into the underlying machine, and designing a system that, per-se, turns out to be Turing-complete.
- guelo 9y agoSame with pokemon, they just found a bug that lets them write to arbitrary memory.
- toomanybeersies 9y agoMissing from the list is Dwarf Fortress: http://dwarffortresswiki.org/index.php/DF2014:Computing http://dwarffortresswiki.org/index.php/DF2014:Computing Great when you want to try and create a computer while trying to fend off goblin attacks and zombies. Technically, it's not Turing Complete, as the "tape" is not unlimited, but other Turing Complete games have the same issue.
- simias 9y agoIf you limit Turing Complete strictly to systems with unlimited "tape" then no computer would qualify except arguably if you stream data in and out, but even then it's only acceptable if the universe is infinite.
- egeozcan 9y agoAlso TypeScript Type System: https://github.com/Microsoft/TypeScript/issues/14833 https://github.com/Microsoft/TypeScript/issues/14833
- catnaroek 9y agoIt would actually be more interesting if someone made a list of useful systems that cannot perform general computation. Some examples: (0) Parsers for context-free grammars (1) Relational algebra, and the subset of SQL that maps to it (2) Hindley-Milner type inference
- j_m_b 9y agoSomeone wrote an article demonstrating that Magic: The Gathering is Turing Complete: https://www.toothycat.net/~hologram/Turing/HowItWorks.html https://www.toothycat.net/~hologram/Turing/HowItWorks.html
- blubb-fish 9y agolooks like a really cool - yet expensive - hobby!
- chengiz 9y ago> The C preprocessor is only Turing-complete, if executed in a loop, which feeds the output to the input ad infinitum. I was momentarily confused by this until I realized there shouldnt be any commas in that sentence.
- xucheng 9y agoAnother missing is the X86 mov instructor. https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator
- unit91 9y agoThat Minecraft CPU video from the article was amazing. It never would have even occurred to me to make such a thing.
- etskinner 9y agoWith the advent of pistons in the game, people have even added hard drives[0] by using a loop of glass (non conductive) and other blocks (conductive). [0] https://youtu.be/q7clz1TPK8o https://youtu.be/q7clz1TPK8o
- mrguyorama 9y agoMore accurately, delay line memory
- Doxin 9y agoIt's not a delay line though. It's linear access, sure, but you can decide when and if to step it.
- mrguyorama 9y agoShame on me for not watching the video then. I (rather short sightedly) though you were referring to a separate implementation that WAS delay line. That's a significant improvement then
- Solarsail 9y agoAs an aside, when I played that game I once made an octal data tape, capable of reading 3 bits of state from a single block in the tape (the "loop"). Used three read circuits next to the tape, which allowed it to detect an additional three states; Namely the block could be non conductor, simple conductor, or a piston block facing up / sideways / down. From there, timing data is enough to distinguish a "sticky piston" from a regular one, allowing for 8 different states distinguishable to the read head. (Apologies if this is me-too ism)
- godelski 9y agoHere is the current world record for Super Mario World (Kill Bowser) that was recently set. He does reprogram the game (includes explanation) https://www.youtube.com/watch?v=YZZhbTtsTts https://www.youtube.com/watch?v=YZZhbTtsTts
- virtualfudge 9y agoRedstone in Minecraft could be added to the list.