If there's a recursion limit, can you not write a program that fails to terminate?
Well sure, but there's always a recursion limit of one kind or another.
Brainfuck interpreter written in the C preprocessor
11–20 of 36 posts
Re: Brainfuck interpreter written in the C preprocessor
#12Earlier quoted context omitted.
It is impossible to implement a system without a de-facto recursion depth limit.
Recursion depth limit is really a memory limit, so you just need someone to come and install more RAM when you run out in order to obtain de facto infinite memory, hence infinite recursion depth.
Even that is not infinite because there is a limit to how much memory you can address. You don't have to bring physical realities into it.
Re: Brainfuck interpreter written in the C preprocessor
#13"There has been much speculation on the turing completeness of the C Preprocessor, but I believe this is the first demonstrative proof that the C preprocessor is turing complete. This uses no GCC extensions and other than the rules for macro evaluation the only 'features' it takes advantage of are token pasting and variable argument macros." Can anyone confirm that this is really the first demonstrative proof of this…
No. It is well known that the C preprocessor is not turing complete. Looking in https://github.com/orangeduck/CPP_COMPLETE/blob/master/RECR.... shows us this technique is not turing complete, as these functions define a maximum recursion depth.
I'm not sure how that disqualifies this from Turing completeness any more than finite pointer sizes disqualify every other language from Turing completeness.
Re: Brainfuck interpreter written in the C preprocessor
#14Re: Brainfuck interpreter written in the C preprocessor
#15Earlier quoted context omitted.
No. It is well known that the C preprocessor is not turing complete. Looking in https://github.com/orangeduck/CPP_COMPLETE/blob/master/RECR.... shows us this technique is not turing complete, as these functions define a maximum recursion depth.
I'm not sure how that disqualifies this from Turing completeness any more than finite pointer sizes disqualify every other language from Turing completeness.
The C preprocessor is a pushdown automaton, which if you add fixpoints (unbounded recursion) becomes a bounded storage machine. Our actual computers are such machines, which if you give them an infinite amount of memory are Turing machines. A language can be Turing-complete even if the implementation of that language is not.
Re: Brainfuck interpreter written in the C preprocessor
#16Earlier quoted context omitted.
No. It is well known that the C preprocessor is not turing complete. Looking in https://github.com/orangeduck/CPP_COMPLETE/blob/master/RECR.... shows us this technique is not turing complete, as these functions define a maximum recursion depth.
I'm not sure how that disqualifies this from Turing completeness any more than finite pointer sizes disqualify every other language from Turing completeness.
There's some subtlety going on here, but I'm going to agree with CJefferson.
Turing completeness is about separating the expression of a computation from the machinery that carries out the computation. If your expression language can be mapped to the idealized Turing machine, then your expression language can express all computations that can be computed. (That is, it is Turing Complete.) This allows us to reason about the expression of computation outside of the machinery that carries it out - because the machinery will always have limits.
The subtlety is: where do we draw the line between the expression and the machinery?
That is, assuming the question is "is the C preprocessor Turing Complete?" I answer no. Because implied in that question is that the C preprocessor language is the expression language we are interested in, and the C preprocessor is the machinery. The reason why I say that the C preprocessor expression language is not Turing complete is simple: you cannot actually express recursion or unbounded loops. No, the above is not a counter example. Why? Because the simulated loops are bounded, always. If you can't express arbitrary loops or recursion, then you can't compute everything that can be computed.
Note that I stressed express. Yes, an actual C program is clearly limited in how much it can recurse, but the language itself can express unbounded recursion.
And that can make our reasoning a bit more interesting: what if rather than asking the question about the C preprocessor, we instead ask it about the implied functional language that the author defined? This implied functional language is implemented in the macros the author defined. If we assume that his implied functional language is the expression language, and the machinery is both the C preprocessor language and the by-hand macros that CJefferson pointed out, then yes, that implied functional language is turing complete. That is, we could take the semantics behind his top-level macros, and go implement a fully Turing Complete language with those semantics. That's what you are getting at when you consider those macros the same as physical memory. We can do that, but now we're reasoning about the author's implied functional language, not the C preprocessor itself.
If you still don't agree, consider that the author's macro language is essentially the same as BlooP: http://en.wikipedia.org/wiki/BlooP_and_FlooP
Re: Brainfuck interpreter written in the C preprocessor
#17Earlier quoted context omitted.
I'm not sure how that disqualifies this from Turing completeness any more than finite pointer sizes disqualify every other language from Turing completeness.
The C preprocessor is a pushdown automaton, which if you add fixpoints (unbounded recursion) becomes a bounded storage machine. Our actual computers are such machines, which if you give them an infinite amount of memory are Turing machines. A language can be Turing-complete even if the implementation of that language is not.
Can C be implemented such that pointers do not have a fixed size? That is to say, suppose you have a hypothetical machine that uses bignum memory addresses. Can C be implemented to run on that machine without cheating and using a fixed pointer size?
Re: Brainfuck interpreter written in the C preprocessor
#18Earlier quoted context omitted.
No. It is well known that the C preprocessor is not turing complete. Looking in https://github.com/orangeduck/CPP_COMPLETE/blob/master/RECR.... shows us this technique is not turing complete, as these functions define a maximum recursion depth.
It is impossible to implement a system without a de-facto recursion depth limit.
Yes, but as I point out elsewhere, Turing Completeness separates the expression from the machine. Machines will always have limits. But the expression of computation does not have to have limits.
Re: Brainfuck interpreter written in the C preprocessor
#19Earlier quoted context omitted.
The C preprocessor is a pushdown automaton, which if you add fixpoints (unbounded recursion) becomes a bounded storage machine. Our actual computers are such machines, which if you give them an infinite amount of memory are Turing machines. A language can be Turing-complete even if the implementation of that language is not.
Can C be implemented such that pointers do not have a fixed size? That is to say, suppose you have a hypothetical machine that uses bignum memory addresses. Can C be implemented to run on that machine without cheating and using a fixed pointer size?
You don't need to reason about C's pointers to consider its Turing Complete. That it allows arbitrary storage, it has conditionals and allows full looping (either unbounded loops or full recursion) is enough. That is, a language that had C's semantics sans pointers would still be Turing Complete.
Re: Brainfuck interpreter written in the C preprocessor
#20Earlier quoted context omitted.
Recursion depth limit is really a memory limit, so you just need someone to come and install more RAM when you run out in order to obtain de facto infinite memory, hence infinite recursion depth.
Even that is not infinite because there is a limit to how much memory you can address. You don't have to bring physical realities into it.
The system will just spontaneously update to the next power-of-two bits when address space gets short. Problem solved.