1
$\begingroup$

Java's type system is Turing complete. For whatever reason, I was under the impression that Kotlin's type system (for concreteness, let's say the latest version of the language -- 1.5.30) was not Turing complete.

I'm not sure exactly where I got this impression, but this leads to the question: Is Kotlin's type system Turing complete? Specifically, is it Turing complete by the same mechanism used in the paper linked above?

Towards the end of this paper, the author says:

Does the reduction from Section 5 apply to other languages like C] and Scala? No. Both of them adopted the recursive–expansive restriction of (Viroli 2000), as recommended by (Kennedy and Pierce 2007). Roughly, this restriction is a syntactic check that succeeds if and only if our Turing tapes are bounded.

I could not find the referenced paper outside of a pay-wall, so I cannot say exactly what this restriction is, but it leads to the question: Does Kotlin have this restriction, thus not making Kotlin's type system Turing complete (by the same mechanism as Java)?

Improve this question
$\endgroup$
3
  • $\begingroup$ No, it's not like java: the specifications of the language (kotlinlang.org/spec/introduction.html) say that the parametric polymorphism is bounded. $\endgroup$
    – Marzio De Biasi
    Commented Sep 24, 2021 at 7:14
  • $\begingroup$ @Marzio De Biasi Does that not just mean that generic parameters can be bound by subtype constraints? That's the impression I get here -- and Java has that as well. en.m.wikipedia.org/wiki/…. $\endgroup$
    – Nathan BeDell
    Commented Sep 24, 2021 at 11:58
  • $\begingroup$ In fact, Java is listed as an example. $\endgroup$
    – Nathan BeDell
    Commented Sep 24, 2021 at 11:59

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.