Accidentally Turing-Complete

Summary

Some things were not supposed to be Turing-complete. This is a collection of such accidents. Stuff which is somehow limited (stack overflows, arbitrary configuration, etc) is still considered Turing complete, since all "physical" Turing machines are resource limited. C++ Templates Although they were initially not supposed to, C++ templates are Turing-complete. For proof look at this paper (pdf). TypeScript Type System In a very similar fashion to C++, the type system of TypeScript can be used to implement a prime check. Java Generics Although Java set out to fix the errors of C++, it also fell into Turing-completeness eventually. Radu Grigore built a parser generator for fluent interfaces. X86 Mov The paper mov is Turing-complete starts as this: It is well-known that the x86 instruction set is baroque, overcomplicated, and redundantly redundant. We show just how much fluff it has by demonstrating that it remains Turing-complete when reduced to just one instruction. It inspired movfuscator, the single instruction C compiler. Building on this, there is a branchless, mov-only version of the classic DOOM video game. This is thought to be entirely secure against the Meltdown and Spectre CPU vulnerabilities, which require speculative execution on branch instructions. The mov-only DOOM renders approximately one frame every 7 hours, so playing this version requires somewhat increased patience. X86 MMU The page fault handling in X86 can be used to implement a simple machine. Basically, a page fault pushes a word to the stack, which might underflow generating another trap. This mechanism provides a "subtract and branch if less than or equal to zero" instruction. Enough to implement a Turing machine. VIDEO Also see the talk. Magic: The Gathering Magic is a card game. Apparently, the rules are complex enough to reach Turing-completeness. There is even a paper about it: Magic: The Gathering is Turing Complete Magic: The Gathering is a popular and famously complicated trading car...