Programming Language Theory: Difference between revisions

@@ Line 17: / Line 17: @@
 C-app ::= C-term C-term</pre>
 ====Fixed-Point Combinators====
-For a function F, its set of ''fixed points'' are those inputs which map to themselves. Provided algebraic functions, for instance, fixed points of a function F(x) would be found by setting <i>F(x) = x</i> and solving for the roots. The ''fixed-point combinators'' compute the fixed points of their functional inputs. Curry's ''Y-combinator'' was the first:
+For a function F, its set of ''fixed points'' are those inputs which map to themselves. Provided algebraic functions, for instance, fixed points of a function F(x) would be found by setting <i>F(x) = x</i> and solving for the roots. Provided an ordered, finite domain, looping through the domain will find all solutions. For an infinite ordered domain, looping is a semi-decision: if there is a least fixed point, it will be found, but the loop never terminates otherwise. The ''fixed-point combinators'' compute the fixed points of their functional inputs. Curry's ''Y-combinator'' was the first:
 * <tt>Y ≡ λf. (λx. f (x x)) (λx. f (x x))</tt> (untyped λ-calculus)
 * <tt>Y ≡ S (K (S I I)) (S (S (K S) K) (K (S I I)))</tt> (SKI calculus)