M. H. Newman's Typability Algorithm for Lambda-calculus

摘要

This article is essentially an extended review with historical comments. It looks at an algorithm published in 1943 by M. H. A. Newman, which decides whether a lambda-calculus term is typable without actually computing its principal type. Newman's algorithm seems to have been completely neglected by the type-theorists who invented their own rather different typability algorithms over 15 years later.