Liczby naturalne Churcha

Ten artykuł od 2021-02 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Liczby naturalne Churcha – konstrukcja w rachunku lambda, umożliwiająca wykonywanie normalnej arytmetyki.

Rachunek lambda bez typów nie zawiera sam z siebie liczb, więc należy je skonstruować.

Liczba naturalna Churcha to funkcja wyższego rzędu pobierająca dwa argumenty – funkcję ${\displaystyle f}$ i argument ${\displaystyle x,}$ która ${\displaystyle n}$-krotnie aplikuje ${\displaystyle f}$ do ${\displaystyle x.}$

Tak więc w zapisie matematycznym:

• 0 to ${\displaystyle x,}$
• 1 to ${\displaystyle f(x),}$
• 2 to ${\displaystyle f(f(x)),}$
• 3 to ${\displaystyle f(f(f(x))),}$
• N+1 to ${\displaystyle f(N),}$

a w zapisie lambda: liczba naturalna ${\displaystyle n}$ to ${\displaystyle \lambda f\ .\lambda x\ .f^{n}x,}$

gdzie:

${\displaystyle f^{0}x}$ to ${\displaystyle x,}$

${\displaystyle f^{n+1}x}$ to ${\displaystyle f(f^{n}x).}$

Operacje na liczbach naturalnych Churcha są opisane w artykule arytmetyka w rachunku lambda.

Zobacz też

• Inne sposoby konstrukcji liczb