Какое свойство системы типов Scala делает его полным по Тьюрингу?

Question

Scala использует систему типов, основанную на Системе F ω, которая обычно считается сильно нормализующей. Сильно нормализующая подразумевает нетюринговую полноту.

Тем не менее, система типов Скалы полна по Тьюрингу.

Какие изменения / дополнения / модификации делают систему типов Scala полной по Тьюрингу по сравнению с формальными алгоритмами и системами?

Answer 1

Это не исчерпывающий ответ, но причина в том, что вы можете определять рекурсивные типы.

Я задавал подобные вопросы раньше ( о том, как может выглядеть полный язык, не являющийся тьюринговым). Ответы были в форме: полный язык Тьюринга должен поддерживать произвольный цикл или рекурсию. Система типов Scala поддерживает последнее