Which property of Scala's type-system make it Turing-complete? [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 9 years ago.

Improve this question

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?

Answer 1

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