3 ms·
> I always considered Rule 110 the simplest system (code complexity wise) that is turing complete It can get a bit subjective, when trying to compare really si
by chriswarbo 3y ago
> I always considered Rule 110 the simplest system (code complexity wise) that is turing complete
It can get a bit subjective, when trying to compare really simple systems.
> an actual implementation would be quite a few more lines
The simplest Turing-complete system to implement that I've come across is FlipJump ( https://esolangs.org/wiki/FlipJump https://esolangs.org/wiki/FlipJump ).
The easiest Turing-complete system I've implemented is BitBitJump, which is older than FlipJump and slightly more complex ( https://esolangs.org/wiki/BitBitJump https://esolangs.org/wiki/BitBitJump ). I used it as a simple way to enumerate the output of all programs: implementation at http://www.chriswarbo.net/js/optimisation/levin_bbj.js http://www.chriswarbo.net/js/optimisation/levin_bbj.js and visualisation/explanation here http://www.chriswarbo.net/projects/optimisation/levin.html http://www.chriswarbo.net/projects/optimisation/levin.html
(Technically these aren't Turing-complete, in the same way that C isn't Turing complete: the amount of memory they can reference is bounded by their word size. This can be fixed by allowing I/O to external storage. My program enumeration loops through all word sizes ;) )