Editing Domain theory (section)

== Motivation and intuition ==
The primary motivation for the study of domains, which was initiated by [[Dana Scott]] in the late 1960s, was the search for a [[denotational semantics]] of the [[lambda calculus]]. In this formalism, one considers "functions" specified by certain terms in the language. In a purely [[syntax|syntactic]] way, one can go from simple functions to functions that take other functions as their input arguments. Using again just the syntactic transformations available in this formalism, one can obtain so-called [[fixed-point combinator]]s (the best-known of which is the [[Fixed-point combinator#Y combinator|Y combinator]]); these, by definition, have the property that ''f''('''Y'''(''f'')) = '''Y'''(''f'') for all functions ''f''.

To formulate such a denotational semantics, one might first try to construct a ''model'' for the lambda calculus, in which a genuine (total) function is associated with each lambda term. Such a model would formalize a link between the lambda calculus as a purely syntactic system and the lambda calculus as a notational system for manipulating concrete mathematical functions. The [[combinator calculus]] is such a model. However, the elements of the combinator calculus are functions from functions to functions; in order for the elements of a model of the lambda calculus to be of arbitrary domain and range, they could not be true functions, only [[partial functions]].

Scott got around this difficulty by formalizing a notion of "partial" or "incomplete" information to represent computations that have not yet returned a result. This was modeled by considering, for each domain of computation (e.g. the natural numbers), an additional element that represents an ''undefined'' output, i.e. the "result" of a computation that never ends. In addition, the domain of computation is equipped with an ''ordering relation'', in which the "undefined result" is the [[least element]].

The important step to finding a model for the lambda calculus is to consider only those functions (on such a partially ordered set) that are guaranteed to have [[least fixed point]]s. The set of these functions, together with an appropriate ordering, is again a "domain" in the sense of the theory. But the restriction to a subset of all available functions has another great benefit: it is possible to obtain domains that contain their own [[function space]]s, i.e. one gets functions that can be applied to themselves.

Beside these desirable properties, domain theory also allows for an appealing intuitive interpretation. As mentioned above, the domains of computation are always partially ordered. This ordering represents a hierarchy of information or knowledge. The higher an element is within the order, the more specific it is and the more information it contains. Lower elements represent incomplete knowledge or intermediate results.

Computation then is modeled by applying [[monotonic|monotone]] [[function (mathematics)|function]]s repeatedly on elements of the domain in order to refine a result. Reaching a [[fixed point (mathematics)|fixed point]] is equivalent to finishing a calculation. Domains provide a superior setting for these ideas since fixed points of monotone functions can be guaranteed to exist and, under additional restrictions, can be approximated from below.