25

Scala uses a type-system based on System F ω, which is normally said to be strongly normalizing. Strongly normalizing implies non-Turing completeness.

Nevertheless, Scala's type-system is Turing-complete.

Which changes/additions/modifications make Scala's type-system Turing-complete compared to the formal algorithms and systems?

5

1 Answer 1

4

It's not a comprehensive answer but the reason is that you can define recursive types.

I've asked similar questions before (about what a non-Turing complete language might look like). The answers were of the form: a Turing complete language must support either arbitrary looping or recursion. Scala's type system supports the latter

3
  • 3
    Recursive types exist in most languages, including Java and Pascal. Any type that refers to itself (like a linked list) is recursive. You need a way to perform computation at the type level, such as type application. In Scala, you have type members and partial type application in type aliases. Dec 14, 2011 at 13:41
  • 2
    I meant recursive types in the sense of the peano encoding: apocalisp.wordpress.com/2010/06/08/… using type, not class or trait. I thought that was reasonably obvious given the context. Like I said, I am echoing here, what I have been told about turing completeness. Dec 14, 2011 at 15:26
  • 1
    Recursive types can be used to encode numbers like you say, but they're not enough for Turing completeness. What you want is a way to compute, in this case using type application (which in turn uses substitution). Scala's type members make it somewhat easy, though Java performs similar substitutions for generics. Dec 15, 2011 at 12:26

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