5 ms·
Since the de Bruijn indices are limited (and presumably still Turing complete), I wonder how limited you can make them and still be Turing complete.
by reuben364 1y ago
Since the de Bruijn indices are limited (and presumably still Turing complete), I wonder how limited you can make them and still be Turing complete.
- jorkingit 1y agoI suspect the answer is 3: SKI combinator calculus is Turing complete and you need 3 de Bruijn indices to define S. Good call! I got rid of all numbers above 2, I can't count that high anyway ;-)