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?
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With