Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

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?

like image 451
soc Avatar asked Dec 13 '11 23:12

soc


1 Answers

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

like image 146
oxbow_lakes Avatar answered Nov 17 '22 00:11

oxbow_lakes