Scott's graph model (commonly referred to as **) is a model of the untyped -calculus.
It is historically the second model of the untyped -calculus, with being the first. It belongs to the class of graph models.
The model is closely related to notions from higher-order computability, in particular enumeration and continuous functionals.
The domain underlying Scott's graph model is the powerset of natural numbers
(The ordinal notation , which is synonymous to , is used here.)
Please expand: description of the model.
Because every -term is interpreted as a set of numbers, is naturally able to support nondeterminism.
This is known to be an algebraic lattice. This means that it has joins and unions of arbitrary subsets (and hence top and bottom elements); and that every one of its elements can be written as a directed family of compact elements.
In this particular case, algebraicity amounts to the observation that any set of natural numbers is the union of its finite subsets, which are the compact elements:
Scott, Dana S. 1976. ‘Data Types as Lattices’. SIAM Journal on Computing 5 (3): 522–87. https://doi.org/10.1137/0205037.
@article{scott_1976,
title = {Data {Types} as {Lattices}},
volume = {5},
doi = {10.1137/0205037},
number = {3},
journal = {SIAM Journal on Computing},
author = {Scott, Dana S.},
year = {1976},
pages = {522--587},
Previous versions had been published under alternative titles at conference proceedings, as technical reports, etc.