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)).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32b1f7f5687c6883a974ccf1ef2b3598d05bf858)
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 ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33c70d2fe84f7387defa9ffe00437e25a586e28e)
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)).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ba022507162049235c6262ac931f6f337fcd638)
Niemniej jeśli
![{\displaystyle ?\equiv \lambda abcdefghijklmnopqstuvwxyzr.\ r\ (thisisafixedpointcombinator),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/080db78a6e67df61354f419c9446050fa33b47a7)
to funkcja
![{\displaystyle \$\equiv \ ??????????????????????????}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6729c410290acb56c352277b4b5a6010fcdb8b99)
też jest operatorem punktu stałego[1].
Przypisy
- ↑ H.P. Barendregt: The Lambda Calculus: Its Syntax and Semantics. 1984. (ang.). Brak numerów stron w książce