> 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”: 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.
Cons (tape, head, state) (Cons (tape, head, state), (Cons ...)))
But since our program is total, we can only extract the first N states, for some finite N. Compare this to a Turing Complete language like Haskell, where we can also define an infinite stream of iterations, but we can also traverse this stream indefinitely.
> The main argument against Turing completeness was that my implementation did not support unbounded recursion.
I’m almost sure they are Primitive recursive function, but I didn’t have time to write the complete proof. http://en.wikipedia.org/wiki/Primitive_recursive_function#Li...