Brainfuck interpreter written in the C preprocessor • Hacker News Board

Re: Brainfuck interpreter written in the C preprocessor

#21

Post by vidarh » Sat, Nov 17, 2012, 3:10 AM UTC

krenoten wrote: post #9

CJefferson wrote: post #8

Earlier 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.

But this is not a de facto recursion limit of the system - the limit is encoded in the program itself, in the macros used to implement the limited recursion.

void f() { f(); } is only limited by the system, and if compiled on a system that automatically expands the stack to fill all available memory, you could in theory keep adding memory, and the system could handle more recursions. The recursion limit is external to the program.

But the linked c-preprocessor programs would have to be explicitly modified by adding more lines of code to achieve the same thing.

Re: Brainfuck interpreter written in the C preprocessor

#22

Post by caf » Sat, Nov 17, 2012, 3:55 AM UTC

mistercow wrote: post #13

CJefferson wrote: post #8

Earlier 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.

One simple reason that the C Preprocessor language is not Turing complete - the answer to the halting problem for any CPP input is "yes".

Re: Brainfuck interpreter written in the C preprocessor

#23

Post by mistercow » Sat, Nov 17, 2012, 6:06 AM UTC

scott_s wrote: post #19

mistercow wrote: post #17

Earlier quoted context omitted.

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.

Are you saying that C with neither pointers nor arrays would still be Turing complete? I am skeptical.

Re: Brainfuck interpreter written in the C preprocessor

#24

Post by mistercow » Sat, Nov 17, 2012, 6:46 AM UTC

asynchrony wrote: post #20

mistercow wrote: post #12

Earlier quoted context omitted.

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.

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.

Re: Brainfuck interpreter written in the C preprocessor

#25

Post by finitocom » Sat, Nov 17, 2012, 7:25 AM UTC

krenoten wrote: post #9

CJefferson wrote: post #8

Earlier 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.

How does tail-recursion fit into this discussion of infinite recursion?

Re: Brainfuck interpreter written in the C preprocessor

#26

Post by JoachimSchipper » Sat, Nov 17, 2012, 10:15 AM UTC

jrajav wrote: post #3

He said it doesn't use any gcc extensions, but this still doesn't seem to work with llvm-gcc or clang. :(

I haven't tried this, but did you compile with the equivalent of -std=c99?

Re: Brainfuck interpreter written in the C preprocessor

#27

Post by mistercow » Sat, Nov 17, 2012, 1:48 PM UTC

caf wrote: post #22

mistercow wrote: post #13

Earlier 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.

One simple reason that the C Preprocessor language is not Turing complete - the answer to the halting problem for any CPP input is "yes".

Ah now, that is an interesting point. Any language that only supports looping by recursion could, in principle, avoid that problem regardless of stack size by transforming recursion into iteration. But CPP can't do that.

Thanks, that's the first clear distinction I've seen for why this is "more" Turing incomplete than C.

Re: Brainfuck interpreter written in the C preprocessor

#28

Post by angeladur » Sat, Nov 17, 2012, 6:22 PM UTC

Has anybody checked out [http://www.ioccc.org/2001/herrmann1.hint

Re: Brainfuck interpreter written in the C preprocessor

#29

Post by tjgq » Sat, Nov 17, 2012, 6:36 PM UTC

mistercow wrote: post #12

asynchrony wrote: post #10

Earlier 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.

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

#30

Post by tjgq » Sat, Nov 17, 2012, 6:43 PM UTC

evincarofautumn wrote: post #15

mistercow wrote: post #13

Earlier 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.

Interestingly, any physical, finite machine can be modelled as a finite state automaton (which is even more limited than a pushdown automaton) with a large enough state space. The distinction only comes up when you consider idealized infinite machines.

Theory of computation is weird.