Operator paradoksalny

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

${\displaystyle \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:

${\displaystyle \mathbb {Y} (\neg )=_{\beta }\neg \mathbb {Y} (\neg ).}$

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

${\displaystyle \mathbb {Y} \equiv \lambda f.\ (\lambda x.\ f\ (x\ x))(\lambda x.\ f\ (x\ x)).}$

Niemniej jeśli

${\displaystyle$ ?\equiv \lambda abcdefghijklmnopqstuvwxyzr.\ r\ (thisisafixedpointcombinator),}

to funkcja

${\displaystyle \$\equiv \$ ??????????????????????????}

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

Przypisy

1. H.P. Barendregt: The Lambda Calculus: Its Syntax and Semantics. 1984. (ang.). Brak numerów stron w książce