This feels like a restatement of the trivially obvious observation that, if your type system is Turing complete, you're going to run into the halting problem.
I don't think that's quite it. In many statically-typed languages that we would typically refer to as having "Turing-complete type systems", types cannot be manipulated at runtime, and thus Type is not really a type in the same way that e.g. int or float are types.
It's sort of like having two languages in one. There is a first, interpreted language which manipulates Types and code and produces a program, and then a second language which is the program itself that ultimately gets typechecked and compiled. Typechecking in this case is not (necessarily) undecidable.
This paper is moreso about dependently-typed languages, where the type of one term can depend on the runtime value of another term.
I'm not sure it is exactly the same. But even if so, someone needed to do the work to prove it. It's also worth noting that proving the undecidability of the halting problem is one of the reasons Turing is so celebrated in the first place.
wavemode|3 months ago
It's sort of like having two languages in one. There is a first, interpreted language which manipulates Types and code and produces a program, and then a second language which is the program itself that ultimately gets typechecked and compiled. Typechecking in this case is not (necessarily) undecidable.
This paper is moreso about dependently-typed languages, where the type of one term can depend on the runtime value of another term.
acjohnson55|3 months ago