Untyped higher-order languages [dt-004M]

If we take PCF, discard the type system, \textbf {fix}, natural number primitives and any other superfluous features, and just boil our language down to a minimal, Turing-complete subset, we end up with the untyped \lambda -calculus — a language consisting only of untyped functions.

Trying to give a semantics to the untyped \lambda calculus poses an issue: we can no longer rely on the type of an expression to select an appropriate semantic domain. Instead, we we must pick a single domain D which, since functions can be applied to themselves, must apparently include the set of functions D \twoheadrightarrow D: D \simeq D\twoheadrightarrow D

Context

Why we need recursively defined domains [dt-004J]

Related

PCF [dt-003T]

Definition. The \textbf {fix} operator [dt-001Q]

Definition. Untyped \lambda -calculus [dt-004K]