GUgus_massa·Jan 28, 2014
From a previous article of the same author: http://theorangeduck.com/page/c-preprocessor-turing-complete
> This is a fairly clear distinction and a compelling argument. Clearly there are languages where you can effectively express unbounded recursion function() { function() } and the C preprocessor is not one of them.
>* But there are a number of subtleties going on here. For example, if we consider the set of macros I created to be the "machinery", and the "language" to be the Brainfuck input to my system, then it is indeed Turing complete. That is - I have created machinery which can simulate Turing complete languages. Taking all the above definitions into account, consider how odd it is that Turing complete machinery can be expressed in a non Turing complete language.*
And from the “Brainfuck interpreter written in the C preprocessor”:
Read the rest
https://github.com/orangeduck/CPP_COMPLETE
> Currently the maximum recursion depth is set to around 1000 and the data array size around 100. These can be easily extended but for now, as a general rule of thumb computations exceeding 1000 steps may not run.
Here is the problem. We can consider the one-step-interpreter: it’s a function that has as arguments a program, the current instruction index and the whole memory state, and this function computes the next instruction index and the next whole memory state. This one-step-interpreter is primitive recursive.
He put that function inside a bounded loop, which is also implementable as a primitive recursive function.
So essentially he created an interpreter that runs a program for at most a fixed number of steps, where this number is an argument of the function (or worse, in this case a constant). Interpreter(Program, Memory, MaxSteps) is a recursive primitive function. To be Turing complete, he needs to write InterpreterForEverIfNecesary(Program, Memory).
With a fixed MaXSteps value, it can’t compute all recursive primitive function.