4 ms·
I always considered Rule 110 the simplest system (code complexity wise) that is turing complete: https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.or
by mg 3y ago
I always considered Rule 110 the simplest system (code complexity wise) that is turing complete:
https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.org/wiki/Rule_110
I wonder if the Langton's ant algorithm (say in Javascript) is shorter.
My gut feeling is that it's about the same size. But maybe Langton's ant is shorter because it only needs a single loop.
In pseudo-code it is super simple:
10 INVERT(X,Y)
20 IF GETCOL(X,Y): TURNLEFT()
30 ELSE : TURNRIGHT()
40 STEPFORWARD()
50 GOTO 10
But an actual implementation would be quite a few more lines.
- 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 ;) )