5 ms·
Brainfuck interpreter written in the C preprocessor
- JulianMorrison 14y agoNow all you need to do is implement COBOL in it, and the gate to hell will open.
- jrajav 14y agoHe said it doesn't use any gcc extensions, but this still doesn't seem to work with llvm-gcc or clang. :(
- JoachimSchipper 14y agoI haven't tried this, but did you compile with the equivalent of -std=c99?
- kibwen 14y ago"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 kind?
- CJefferson 14y agoNo. It is well known that the C preprocessor is not turing complete. Looking in https://github.com/orangeduck/CPP_COMPLETE/blob/master/RECR.h 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.
- krenoten 14y agoIt is impossible to implement a system without a de-facto recursion depth limit.
- asynchrony 14y agoRecursion 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.
- mistercow 14y agoEven 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.
- asynchrony 14y agoThe system will just spontaneously update to the next power-of-two bits when address space gets short. Problem solved.
- mistercow 14y agoThat 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.
- tjgq 14y agoHow 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.
- 14y ago
- mistercow 14y agoI'm not sure how that disqualifies this from Turing completeness any more than finite pointer sizes disqualify every other language from Turing completeness.
- evincarofautumn 14y agoThe 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.
- mistercow 14y agoCan 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?
- scott_s 14y agoYou 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.
- tsewlliw 14y agoIf there's a recursion limit, can you not write a program that fails to terminate?
- jrajav 14y agoU,F,F,R,U,B,U,B
- mistercow 14y agoWell sure, but there's always a recursion limit of one kind or another.
- JulianMorrison 14y agoAll programs terminate at the heat death of the universe.
- wheaties 14y agoImpressive. Massively impressive. Does this count towards your thesis in any way? I'd hate the kind of effort this required to go to waste when PhDs sucks the life out of your for 6-8 years (at least in the US.)
- angeladur 14y agoHas anybody checked out [http://www.ioccc.org/2001/herrmann1.hint http://www.ioccc.org/2001/herrmann1.hint