타입 없는 λ-계산

타입 없는 λ-계산(untyped λ-calculus)는 가장 먼저 등장한 λ-계산이다. 타입이 없는 특성 덕에 매우 단순함에도 불구하고 튜링 완전하다.

\[ M, N ::= x \mid \lambda x. M \mid M \ N \]