Operator paradoksalny

Operator paradoksalny

Operator paradoksalny, znany również jako operator punktu stałego, to funkcja w rachunku lambda, która generuje punkt stały dla każdej danej funkcji. Można to zapisać jako:

$\backslash mathbb\{Y\}\; (f)\; =\_\backslash beta\; f\; (\backslash mathbb\{Y\}\; (f)).$

Nazwa operatora pochodzi od jego właściwości. Na przykład, dla funkcji negacji (niezależnie od definicji) otrzymujemy:

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

Istnieje nieskończona liczba operatorów paradoksalnych, jednak najczęściej używany jest zdefiniowany w następujący sposób:

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

Innym przykładem operatora punktu stałego może być:

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

co prowadzi do powstania funkcji:

$\backslash \$\; \backslash equiv\; ??????????????????????????$

Przypisy

Kategoria: Rachunek lambda