9

There is a well-known fact that C++ templates are turing-complete, CSS is turing-complete (!) and that the C# overload resolution is NP-hard (even without generics).

But is C# 4.0 (with co/contravariance, generics etc) compile-time turing complete?

Community
  • 1
  • 1
wizzard0
  • 1,883
  • 1
  • 15
  • 38

1 Answers1

2

Unlike templates in C++, generics in C# (and other .net lang) are a runtime generated feature. The compiler does do some checking as to verify the types use but, actual substitution happens at runtime. Same goes for Co and contravariance if I'm not mistaken as well as even the preprocessor directives. Lots of CLR magic.

(At the implementation level, the primary difference is that C# generic type substitutions are performed at runtime and generic type information is thereby preserved for instantiated objects)

See MSDN

http://msdn.microsoft.com/en-us/library/c6cyy67b(v=vs.110).aspx

Update: The CLR does preform type checking via information stored in the metadata associated with the compiled assemblies(Vis-à-vis Jit Compliation), It does this as one of its many services,(ShuggyCoUk answer on this question explains it in detail) (others include memory management and exception handling). So with that I would infer that the compiler has a understanding of state as progression and state as in machine internal state (TC,in part, mean being able to review data (symbols) with so reference to previous data(symbols) , conditionally and evaluate) (I hesitated to state the exact def of TC as I, myself am not sure I have it fully grasped, so feel free to fill in the blanks and correct me when applicable ) So with that I would say with a bit of trepidation, yes, yes it can be.

Community
  • 1
  • 1
Terrance
  • 11,764
  • 4
  • 54
  • 80
  • Generics are instantiated at run-time, you are right. But "some checking" can very well be turing-complete as well. You never know :) Also, preprocessor directives are compile-time. – wizzard0 Sep 23 '12 at 07:31
  • Preprocessor Directives are compile-time, you are correct there sir. My mistake, let me fix. – Terrance Sep 23 '12 at 18:36
  • But you said C# doesn't have a preprocessor. I mention that compiler does and I make a correction about it. What is it that I am repeating? Also the OP asked specifically about the compiler being TC specifically after additional features the .NET runtime were added. While I do agree it is not a complete answer, I do think it addresses,at least in part, what the OP was wondering about in regards to the compiler. – Terrance Sep 24 '12 at 13:14
  • Hmm, after an update to an answer, if we count JIT as being part of the C# compiler, then it definitely IS turing complete. Though it isnt :) But you made me thinking about the TypeRef resolution step of compilation and I think I can encode a turing machine in this.. so, I think I'll accept this answer now and try :) – wizzard0 Sep 25 '12 at 16:05
  • Well, thanks for the interesting question. Post a comment when you have something. I'm definitely curious to see how you go about it. – Terrance Sep 25 '12 at 17:55
  • Is there any update on this? The topic came up in a chat forked off the comments discussion for [this question](http://stackoverflow.com/questions/15148425/class-specialization-a-valid-transformation-for-a-conforming-compiler) so now I'm curious. (Obviously, generics instantiate at runtime, but can you encode an arbitrary TM as runtime generic instantiation?) – Stephen Lin Mar 01 '13 at 03:20
  • Well, the C# compiler has some [interesting properties](https://codegolf.stackexchange.com/a/24419/14742). – IS4 Nov 02 '17 at 21:55