News for hackers. Stuff that matters.
Re:What type of Machine is the C Preprocessor? by gus_massa on Monday January 27, 2014 @07:50PM (#7134492)
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”: 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.

Re:What type of Machine is the C Preprocessor? by chriswarbo on Tuesday January 28, 2014 @06:19AM (#7136457)
This situation crops up in total languages like Coq. For any iterative process, like the stepping of a Turing Machine, we can create an infinite stream of iterations, eg.

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.