Brainfuck interpreter written in the C preprocessor • Hacker News Board

Re: Brainfuck interpreter written in the C preprocessor

#31

Post by orangeduck » Sat, Nov 17, 2012, 7:37 PM UTC

scott_s wrote: post #16

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.

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 abo…

This is an excellent explanation.

As you say, if we assume that my set of macros are the machinery, then truly my "BRAINFUCK()" macro is Turing complete.

Using this distinction between language and machine, how peculiar that a Turing Complete thing can be expressed using a language which is not Turing Complete itself.

The question is really - are these distinctions between machine and language always meaningful and without contradiction.

Re: Brainfuck interpreter written in the C preprocessor

#32

Post by pfultz2 » Sat, Nov 17, 2012, 9:18 PM UTC

scott_s wrote: post #16

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.

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 abo…

So the expression of unbounded recursion can be expressed like this:

    #define EMPTY()
    #define DEFER(id) id EMPTY()

    #define FOREVER() \
        ? \
        DEFER(FOREVER_INDIRECT) () ()
    #define FOREVER_INDIRECT() FOREVER

This will print out `?` infinitely. Here is the machinery to evaluate the expression:

    #define EVAL(...) A(A(A(__VA_ARGS__)))
    #define A(...) B(B(B(__VA_ARGS__)))
    #define B(...) C(C(C(__VA_ARGS__)))
    #define C(...) D(D(D(__VA_ARGS__)))
    #define D(...) E(E(E(__VA_ARGS__)))
    #define E(...) __VA_ARGS__

    EVAL(FOREVER())

Which will expand to something like this:

    ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? FOREVER_INDIRECT () ()

Well at the end we see `FOREVER_INDIRECT () ()` which means the algorithm can expand further, so we could just apply more scans:

    EVAL(EVAL(FOREVER()))

And we get more `?`. And we didn't have to change the expression of the algorithm just the machinery to evaluate it.

This is why I say the C preprocessor can act as Turing-complete, because the expression and machinery, while separate, is both in the language itself. This is different than BlooP, which the only possible way to express Turing completeness is through an external source(such as an input file).

Of course, for all practical purposes, the C preprocessor is near Turing-complete enough. The whole goal of the preprocessor is to output a file, we don't need it run indefinitely. We can express almost any useful algorithm, and if it reaches the recursion limit, we just simply apply more scans.

Re: Brainfuck interpreter written in the C preprocessor

#33

Post by scott_s » Sat, Nov 17, 2012, 10:51 PM UTC

pfultz2 wrote: post #32

scott_s wrote: post #16

Earlier quoted context omitted.

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 abo…

So the expression of unbounded recursion can be expressed like this: #define EMPTY() #define DEFER(id) id EMPTY() #define FOREVER() \ ? \ DEFER(FOREVER_INDIRECT) () () #define FOREVER_INDIRECT() FOREVER This will print out `?` infinitely. Here is the machinery to evaluate the expression: #define EVAL(...) A(A(A(__VA_ARGS__))) #define A(...) B(B(B(__VA_ARGS__))) #define B(...) C(C(C(__VA_ARGS__))) #define C(...) D(D(D…

This is why I say the C preprocessor can act as Turing-complete, because the expression and machinery, while separate, is both in the language itself.

Unfortunately, "can act as Turing-complete" is not a well defined concept. It is clearly not the same thing, and the distinction is important. Consider, as pointed out elsewhere in this thread, that we can always solve the halting problem for a C preprocessor program. We're in danger of violent agreement, though: I think we agree on the main points, just perhaps not on their relevance.

Since we've gone this far down the rabbit hole, I'd like to point out that C++ templates are Turing complete: http://netvor.sk/~umage/docs/3rdparty/C++%20Templates%20are%...

Re: Brainfuck interpreter written in the C preprocessor

#34

Post by scott_s » Sat, Nov 17, 2012, 10:53 PM UTC

orangeduck wrote: post #31

scott_s wrote: post #16

Earlier quoted context omitted.

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 abo…

This is an excellent explanation. As you say, if we assume that my set of macros are the machinery, then truly my "BRAINFUCK()" macro is Turing complete. Using this distinction between language and machine, how peculiar that a Turing Complete thing can be expressed using a language which is not Turing Complete itself. The question is really - are these distinctions between machine and language always meaningful and w…

Using this distinction between language and machine, how peculiar that a Turing Complete thing can be expressed using a language which is not Turing Complete itself.

Ah, but that's the rub: we can't, and we didn't. You are imparting semantics on your macros that the C preprocessor has not. That is, the semantics that you imagine the macros to have are solely in your mind. They are not implied by the semantics of the C preprocessor.

Re: Brainfuck interpreter written in the C preprocessor

#35

Post by knz42 » Sun, Nov 18, 2012, 2:30 PM UTC

mistercow wrote: post #23

scott_s wrote: post #19

Earlier quoted context omitted.

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.

It's not, and it's not obvious.

https://tdotc.wordpress.com/2012/11/18/on-the-turing-complet...

Re: Brainfuck interpreter written in the C preprocessor

#36

Post by scott_s » Sun, Nov 18, 2012, 4:12 PM UTC

knz42 wrote: post #35

mistercow wrote: post #23

Earlier quoted context omitted.

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

It's not, and it's not obvious. https://tdotc.wordpress.com/2012/11/18/on-the-turing-complet...

I actually pondered on this for a long time, and I haven't come to a conclusion. I cannot, however, counter any of your arguments, as I thought some of the same things myself.

This is a surprising train of thought.