Hacker News new | ask | show | jobs
by battery_cowboy 2241 days ago
It's Turing complete because it could simulate a Turing machine, not because of metaprogramming. The language brainfuck is Turing complete, for example.
1 comments

Checking if a Brainfuck program is well formed (i.e. can be run) is a linear time operation. In C++ this can take forever. They have different complexities.
The original comment was about Turing completeness, and it was defined incorrectly. I was giving an example of a dead-simple language that was Turing complete, because the claim was that metaprogramming made C++ Turing complete.
The claim wasn’t that C++ is Turing complete, that’s trivially true. The claim was that C++’s grammar is Turing complete. I don’t know if that’s exactly the right way to phrase it, but C++’s template expansion stuff is Turing complete.
It was a weird phrasing to me, but i get what you were all saying now.
No, the claim was that metaprogramming made the grammar of C++ Turing complete.
Metaprogramming in C++ is TC, but it's not what makes C++ TC by itself.
Yes, but it is the difference to other programming languages.

In C you cannot encode a Turing machine that is executed by the compiler at compile time. In Brainfuck you cannot encode a Turing machine that is executed by the compiler at compile time. In C++ you can encode a Turing machine that is executed by the compiler at compile time.

That is the difference we are discussing here.

Yes i now realize that, thanks for explaining further. The original comment was worded in a way that i misunderstood the claim.
>In C you cannot encode a Turing machine that is executed by the compiler at compile time.

But you can get quite close with macros

You misunderstand. C++ is Turing-complete at compile time, due to template metaprogramming. This demonstrates that it isn't a context-free grammar.

This isn't true of all programming languages.

Thanks, i see what you were saying now, i misunderstood your original comment.