2

I often hear that C++ templates are Turing complete. What does it mean?

My previous search lead me to links [1] and [2] which are good but they do not answer what I am asking.

it's capable of expressing general recursion by simply using templates that refer to themselves and using template specialization for making decisions.

Is recursion and and making decision equivalent to Turing completeness?

Could someone please break down the requirements of Turing completeness in the programming aspect (not from the computer science aspect)?

yumbi
  • 45
  • 2
  • 1
    I'm voting to close this question as off-topic because this theory-based question belongs on Quora or the [CS Site](http://cs.stackexchange.com). – tadman Mar 02 '18 at 01:09
  • 3
    @tadman, I am exactly opposite as I escape computer science. I need to understand it in from the programming aspect, otherwise the definition of Turing completeness on wikipedia would be enough for me. – yumbi Mar 02 '18 at 01:12
  • 1
    A lot of things are Turing complete, including CSS. What does it mean in practice? Not much. Just because you *can* write complicated code in things like CSS and C++ templates doesn't mean you should. Just as the [Game of Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life) is Turing complete since you can build a Turing machine in it, that definition is almost meaningless since the utility of such a thing is nearly zero. – tadman Mar 02 '18 at 01:13
  • 2
    @tadman. Then what is Turing completeness? Your commend does not convince me. – yumbi Mar 02 '18 at 01:16
  • 2
    In programming "Turing complete" usually means "a language which can *theoretically* perform any function" even if implementing that function may be extremely difficult. – tadman Mar 02 '18 at 01:16
  • 1
    @tadman, Then, how do you know C++ templates perform any function? – yumbi Mar 02 '18 at 01:17
  • 2
    This is back to theory on how to prove Turing completeness. In the simplest form: If you can make a Turing machine with the language, it's Turing complete by definition. See also [this answer](https://stackoverflow.com/questions/189172/c-templates-turing-complete) from 2008. – tadman Mar 02 '18 at 01:17
  • 1
    @tadman, This is something like asking about `void*` or `try catch` to me. As I mentioned I am not interested in its theories. – yumbi Mar 02 '18 at 01:19
  • 2
    You can emulate Turing machine with C++ templates => C++ templates are Turing-complete. You don't have to prove every function. – Ivan Aksamentov - Drop Mar 02 '18 at 01:19
  • 2
    @yumbi Turing completeness is a theoretical construct. You can't escape that. When talking about Turing complete languages you're talking about *theory*. `void*` isn't a theory, it's an application of various theories. – tadman Mar 02 '18 at 01:19
  • 2
    @Drop, I do not know what Turing machine means. Beside that, I do not understand `every function`. How about a CPU that eats human? Can it do that function? – yumbi Mar 02 '18 at 01:20
  • 2
    If you don't understand what Turing machine is you're never going to understand Turing completeness, so you need to fill in that gap in your knowledge first. The concept is pretty simple, but there's explanations out there far better than can fit in a little comment. – tadman Mar 02 '18 at 01:21
  • 2
    @tadman, It is theoritical, but it can be translated into C++ like many other things. – yumbi Mar 02 '18 at 01:21
  • 1
    I just linked to it: [Theory as applied to C++ templates](https://stackoverflow.com/questions/189172/c-templates-turing-complete/275295#275295). Theories aren't translated, they're applied. – tadman Mar 02 '18 at 01:22
  • 2
    @tadman, It did not answer my question as I had already linked it in my question. – yumbi Mar 02 '18 at 01:23
  • 4
    **Read up on what a Turing machine is**. – tadman Mar 02 '18 at 01:23
  • 1
    @tadman, I am an engineer. Not a computer scientist. I just understand C++. Just want to know what C++ requirements make templates Turing complete. – yumbi Mar 02 '18 at 01:25
  • 4
    Try [engineering version](https://simple.wikipedia.org/wiki/Turing_machine) then. It has pictures! – Ivan Aksamentov - Drop Mar 02 '18 at 01:25
  • 5
    If you're not willing to take the time to read up on the theoretical concept nobody can help you here. This isn't a C++ thing, this is a **computer science theory** you're refusing to take the time to learn about. As an engineer I spent a lot of time learning about theories, and then how to apply them. – tadman Mar 02 '18 at 01:26
  • 2
    @tadman, It is not about reading. The sentences are so ambiguous to me. What is machine? What is function? .... all are unclear in that context and not related to C++. – yumbi Mar 02 '18 at 01:29
  • 4
    Please, before testing everyone's patience with this ridiculousness, **do your homework**. This is veering wildly off-topic. An engineer not willing to take the time to understand the fundamentals of what they're working with, of absorbing and comprehending the theories, is not an engineer at all. – tadman Mar 02 '18 at 01:30
  • 1
    @tadman You are being heroic here – Amadeus Mar 02 '18 at 01:30
  • @yumbi You would not make a good engineer if you don't know about state machines (which Turing machine is a particular case of). Basically, you just admitted that you either unable to develop a large stateful application (like most of GUI apps), or it is every time a mess of conditional statements and jumps. Go do your homework and stop complaining. – Ivan Aksamentov - Drop Mar 02 '18 at 01:30
  • @Amadeus I'm willing to go to great lengths to help anyone willing to learn. – tadman Mar 02 '18 at 01:30
  • @tadman yeah but after all the links. you deserve congratulations – Amadeus Mar 02 '18 at 01:31
  • @tadman You are my hero! – Ivan Aksamentov - Drop Mar 02 '18 at 01:31
  • 2
    @tadman, I am graduated. Just a C++ enthusiast. It is not a homework. If you do not like the question, at least you can respect ethics. – yumbi Mar 02 '18 at 01:31
  • 3
    Just because you graduated doesn't mean you get a free pass and don't have to learn any more theory. As a programmer you're going to need to learn through your *whole career*. – tadman Mar 02 '18 at 01:32
  • 2
    @yumbi (s)he is being very polite. The time you spent discussing here, if you use it to read the links almost all doubts could be gone – Amadeus Mar 02 '18 at 01:33
  • 1
    @Amadeus, it is wrong to assume I didn't read the theory. I just did not understand it. I am not interested in reading so many books to understand a question which has a simple answer. – yumbi Mar 02 '18 at 01:36
  • 3
    We can't help you understand theory, that's for another site or another platform. We can only help you with code you've written that doesn't work. – tadman Mar 02 '18 at 01:37
  • @tadman, being graduated referred to you accusation about doing a homework. – yumbi Mar 02 '18 at 01:37
  • 2
    @tadman, other SE branches will pass me back to SO. – yumbi Mar 02 '18 at 01:37
  • 2
    Just because you've graduated doesn't mean you're immune from having to do homework. I have to do it all the time and I haven't been in school for decades. If this has you really stumped, hire a tutor or find a mentor. – tadman Mar 02 '18 at 01:37
  • @tadman, I do not ask anybody helping me to understand the theory. You didnt get the point of the question. I just asked what C++ requirements will lead to turing completeness. – yumbi Mar 02 '18 at 01:39
  • @tadman, being good in Ruby does not qualify understanding C++ template meta-programming. – yumbi Mar 02 '18 at 01:43
  • 2
    If you want to attack the people attempting to help you that's one way to do it. – tadman Mar 02 '18 at 01:45
  • 1
    @tadman, not attacking anyone. I just asked a question, and someone smeared me with accusation of doing homework and being lazy to read the theories. And insisting on that in an area out of the scope. Downvoting and attempting to close my question does not seem attempting to help to me but I tolerated it. – yumbi Mar 02 '18 at 01:51
  • 2
    My advice: Put down the shovel, stop digging a deeper hole for yourself, and dust off your textbooks. You've got some learning to do. We can only advance our knowledge by admitting what we don't know and working to fill the gaps by studying. – tadman Mar 02 '18 at 01:52
  • 2
    @tadman, having even 100K does not qualify bullying or even giving advice as a teacher to the new users. The question is correct no matter if you like it or not. No matter if you spend time to revenge or not. I do not even care about that. If your aim was making me angry, you failed. – yumbi Mar 02 '18 at 02:02
  • 1
    Sure, or you can do that instead. – tadman Mar 02 '18 at 02:03

0 Answers0