Re:Brainfuck interpreter written in the C preprocessor
by asynchrony on Friday November 16, 2012 @06:17PM
(#4796374)
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.
[ Parent
| on HN ]
Re:Brainfuck interpreter written in the C preprocessor
by mistercow on Friday November 16, 2012 @06:55PM
(#4796492)
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
by tjgq on Saturday November 17, 2012 @01:36PM
(#4798706)
How is a "limit to how much memory [one] can address" not a physical, rather than logical, constraint?
Really, the crux of the matter is that you can have a function call itself an unbounded number of times in C (i.e. unbounded recursion). That you eventually run into a stack overflow is a limitation of the machine, not of the language; the definition of C does not prescribe a maximum number of recursive calls. This, together with conditionals, makes the C language Turing-complete.
Re:Brainfuck interpreter written in the C preprocessor
by asynchrony on Friday November 16, 2012 @08:01PM
(#4796689)
The system will just spontaneously update to the next power-of-two bits when address space gets short. Problem solved.
Re:Brainfuck interpreter written in the C preprocessor
by mistercow on Saturday November 17, 2012 @01:46AM
(#4797455)
That would break binary compatibility with all existing programs, though. So I guess the claim should be that it's impossible to implement a practically useful system without a de-facto recursion depth limit.