[mehrdadn]

There's something that's unsatisfying about most of these examples which is that a sane person wouldn't write code that multiplies two objects and throws away the result, so people might think that if you added extra constraints to prevent depending on silly side effects, the issue would go away. This is definitely false, but it's not exactly obvious if you don't think about it too hard... I wish people actually paid attention to it when constructing counterexamples.

So, for anyone else feeling similarly unsatisfied, here's another example that might be more satisfying in that respect:

  y = f(g<T, U>(x));

In conjunction with the fact that templates are already Turing-complete, we can see that detecting whether this is a call to a templated g or two comparisons is a Turing-complete question.

Also notice a similar parsing issue arises in C# as well, but I don't think generics there can be used to perform Turing-complete computation... though not sure.

[ygra]

You can use generics and overload resolution to solve satisfiability problems in C# and Java. But not in the way like templates in C++ allow for compile-time computation.

[mehrdadn]

Yup I've seen that aspect haha.