Uma prova simples de que a decidibilidade da tipabilidade no Sistema F (

Suponha que não conheçamos o resultado de Joe B. Wells, de 1994, de que tanto a tipabilidade quanto a verificação de tipos são indecidíveis no Sistema F (AKA ). No cálculo lambda de Barendregt com tipos (1992), encontrei uma prova, devido a Malecki 1989, de que a verificação de tipo implica tipicidade. Isto é porque$\lambda 2$

existe tal que M : $\sigma$$M:\sigma$

é equivalente a

$(\lambda xy.y)M : (\alpha\rightarrow\alpha)$

(Isso ocorre porque se um termo é tipável no Sistema F, todos os seus subtermos são.)

Existe uma prova simples ao contrário? Ou seja, uma prova de que tipibilidade implica verificação de tipo no Sistema F?

Tanto quanto eu sei, mostrando que essa direção é a parte mais difícil da prova de Wells! Pelo menos é o que Pawel (Urzyczyn) me explicou alguns anos atrás.

Aparentemente, não é muito difícil mostrar que a verificação de tipo é indecidível; a parte difícil é mostrar que isso implica indecidibilidade na reconstrução de tipos! De fato, existem alguns casos em que o primeiro é indecidível e o segundo decidível: ver, por exemplo, Dowek 1993.