Operator paradoksalny

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))$$\mathbb {Y} (f)=_{\beta }f(\mathbb {Y} (f))$.

Nazwa bierze się stąd, iż 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 )$$\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} \equiv \lambda f.\ (\lambda x.\ f\ (x\ x))(\lambda x.\ f\ (x\ x))$$\mathbb {Y} \equiv \lambda f.\ (\lambda x.\ f\ (x\ x))(\lambda x.\ f\ (x\ x))$.

Niemniej jeśli

• $?\equiv \lambda abcdefghijklmnopqstuvwxyzr.\ r\ (thisisafixedpointcombinator)$$?\equiv \lambda abcdefghijklmnopqstuvwxyzr.\ r\ (thisisafixedpointcombinator)$,

to funkcja

• $\$\equiv \ ??????????????????????????$$\$\equiv \ ??????????????????????????$

też jest operatorem punktu stałego.