Operator paradoksalny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Operator paradoksalny (operator punktu stałego) - funkcja w rachunku lambda, która dla każdej funkcji tworzy jej punkt stały:

\mathbb{Y} (f) =_\beta f (\mathbb{Y} (f))

Nazwa bierze się stąd, że jeśli tą funkcją będzie na przykład negacja (niezależnie od przyjętej definicji) to:

\mathbb{Y} (\neg) =_\beta \neg  \mathbb{Y} (\neg)

Operatorów paradoksalnych jest nieskończenie wiele. Najczęściej używany jest zdefiniowany następująco:

\mathbb{Y} = \lambda f.\ (\lambda x.\ f\ (x\ x))(\lambda x.\ f\ (x\ x))

niemniej jeśli

  • ? = \lambda abcdefghijklmnopqstuvwxyzr.\ r\ (thisisafixedpointcombinator)

to funkcja

  • \$ =\ ??????????????????????????

też jest operatorem punktu stałego[1].

Przypisy

  1. H. P. Barendregt: The Lambda Calculus: Its Syntax and Semantics.. 1984. (ang.)