Which property of Scala's type-system make it Turing-complete? [closed]
-
15-03-2021 - |
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?
La solution
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
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow