4 ms·
It's Turing complete because it could simulate a Turing machine, not because of metaprogramming. The language brainfuck is Turing complete, for example.
by battery_cowboy 6y ago
It's Turing complete because it could simulate a Turing machine, not because of metaprogramming. The language brainfuck is Turing complete, for example.
- saagarjha 6y agoChecking 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.
- battery_cowboy 6y agoThe 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.
- tom_mellior 6y agoNo, the claim was that metaprogramming made the grammar of C++ Turing complete.
- deleted 6y ago[deleted]
- battery_cowboy 6y agoMetaprogramming in C++ is TC, but it's not what makes C++ TC by itself.
- MaxBarraclough 6y agoYou 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.
- battery_cowboy 6y agoThanks, i see what you were saying now, i misunderstood your original comment.
- tom_mellior 6y agoYes, 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.
- benibela 6y ago>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
- tom_mellior 6y agoNo. You would need the ability to write unbounded loops or unbounded recursion. You don't have that with the C preprocessor. Yes, you can do a lot with the C preprocessor. You can also do a lot in languages that only have bounded loops and are therefore not Turing complete. You can either express nonterminating computations (Turing completeness), or you can't (still powerful, but dramatically less poweful). This question is binary. There is no fuzziness, there is no approximation, there is no "quite close".
- battery_cowboy 6y agoYes i now realize that, thanks for explaining further. The original comment was worded in a way that i misunderstood the claim.
- wtetzner 6y agoThe 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.
- battery_cowboy 6y agoIt was a weird phrasing to me, but i get what you were all saying now.