# Relation between type-checking decidability, typability decidability and strong normalization

Yo! This is probably a stupid question, however I've never seen it written down explicitly if, for instance, decidability of type-checking is equivalent to the strong normalization property. Therefore I'm asking this question to clarify all possible relations between type-checking, typability and strong normalization.

Let me explain my motivation. For type theories (I'm being intentionally vague here, but I'm interested mainly in dependent type theories), strong normalization is used to prove the decidability of type-checking. On the other side, any typed systems that I know that have one of these properties also have the other one. However I've never seen explicitly stated that strong normalization is equivalent to decidability of type-checking.

Analogously, to prove typability, one usually (maybe always), reduces a term to a normal form. However it's know that typability is not true for dependent type theories, whereas strong normalization may hold.

By decidability of type-checking, I mean that for any given type $A$, context $\Gamma$ and untyped term $a$, it's possible to decide in a finite number of steps whether $\Gamma \vdash a: A$ is true or not.

By decidability of typability, I mean that for any given untyped term $a$, it's possible to decide in a finite number of steps whether there exist a context $\Gamma$ and a type $A$ such that $\Gamma \vdash a: A$ is true.

1)Is it true that decidability of type-checking is equivalent to every term being strongly normalizable?

2)More generally, what's the relation between decidability of type-checking, typability and strong normalization? Which one implies the other?

EDIT

Given the unsatisfaction regarding the level of generality of my question (which I was unaware of), I would like to delimit it only to Pure Type Systems. Of course, additional comments or counterexamples regarding other type theories will be of great utility.

• With no restrictions whatsoever? What if we take the trivial type system where every term has every type? That's trivially decidable but not normalizing. I fear that, in general, unless more constraints are put on the type system, there might be no relations among the notions you cite.
– chi
Apr 30 '17 at 23:19
• @chi I'm sorry. I wasn't aware of the level of generality of the definition of a typed system. What I had in mind was something like a fragment of Martin-Löf (extensional) type theory with universes. I believe, therefore, that Pure Typed Systems would be the correct bound in my question. May 2 '17 at 3:39
• What do you mean that Expansion Postponement has been settled? The link is not available anymore. My understanding so far is that it is known to be true for a subclass of PTS (semi-full I think) but it is still an open conjecture for the general case. Jul 26 '19 at 8:02

I'll give a more focused and technical answer to Martin's. If we're interested in dependent type theories, then neither direction is obvious, but both are generally assumed to hold. However the direction Decidable $\Rightarrow$ Normalizing is open, I believe, even for relatively well understood systems, though we do have partial results. This question explores some of the same issues.

More technically: a good technical framework for these questions is the setting of Pure Type Systems in which normalization does imply decidability of type checking. The result is folklore, but non-trivial, since a strategy for when to apply the conversion rule needs to be found. The obvious strategy is to normalize inferred types before all applications of the application rule. There are some subtleties even here, where the correctness of a natural (more efficient) strategy called expansion postponment was open for a while, but has been settled since.

There are type systems which are normalizing but undecidable, most notably the system with intersection types which types exactly the normalizing terms, and so must be undecidable (since otherwise it could be used to identify normalizing terms). It would be tempting to say here that the system is defective in the sense that it is not type directed, i.e. the terms do not contain enough information to figure out the type.

Now the converse, which would suggest non-normalizing systems are undecidable, is far from obvious: it was even open for a while for the famous $Type:Type$ system of Martin-Löf! This case was solved by giving an example of a looping combinator, which allows writing arbitrary computations.

However the general problem is still open for general pure type systems, though it is widely believed to be true, and some partial results have been shown in this direction, e.g. here.