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)?

  • $\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$ Sep 24 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$ Sep 24 at 11:58
  • $\begingroup$ In fact, Java is listed as an example. $\endgroup$ Sep 24 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.