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?

1 Answer 1

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.

7
  • 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
    Commented Sep 23, 2012 at 7:31
  • Preprocessor Directives are compile-time, you are correct there sir. My mistake, let me fix.
    – Terrance
    Commented Sep 23, 2012 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
    Commented Sep 24, 2012 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
    Commented Sep 25, 2012 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
    Commented Sep 25, 2012 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.