8299308023

W pkt. 3 zademonstrowany został operator rekursji Fix, o którym jeszcze będzie mowa w rozdziale 1.7.

1.2.3.2 A-rachunek jako model obliczeń

Dla przeprowadzanych obliczeń nie ma znaczenia, na jakim „materiale” je wykonujemy — czy na palcach, czy na ciągach bitów, czy na funkcjach. Ważne jest tylko, żeby podstawy spełniały te same aksjomaty początkowe. Otóż funkcje, wyrażane przez A-rachunek, są materiałem na tyle bogatym, że można przy ich pomocy zdefiniować liczby naturalne i podstawowe działania na nich¹³.

Okazuje się, że możliwe jest symulowanie w ten sposób obliczenia dowolnej maszyny Tu-ringa:

Twierdzenie 1.21

\-rachunek jest zupełny w sensie Turinga.

Wszystko, co daje się efektywnie obliczyć dowolnymi sposobami, daje się policzyć przy pomocy pewnych ^-konwersji (por. Teza 1.15). Jak widać z przykładu 1.20 pkt. 3, przy pomocy ^-konwersji możliwe jest uzyskanie nieskończonego obliczenia.

/^-konwersja jest bardzo prostym mechanizmem obliczania, sprowadza się do samego zastępowania zmiennych wyrażeniami, z ewentualnym przenazwowaniem zmiennych. Nie zawiera wielu elementów, do których programiści są przyzwyczajeni — np. pętli. A jednak okazuje się, że nadaje się do obliczeń równie dobrze jak kroki maszyny Turinga. W szczególności wszystkie rodzaje pętli można zastąpić rekursją, a rekursję wyrazić przy pomocy operatora Fix zademonstrowanego w przykładzie 1.20 pkt. 3.

Z tego powodu na modelu A-rachunku zbudowano całą klasę języków programowania, t.zw. języków funkcyjnych. Najstarszym przykładem takiego języka jest LISP; do nowszych należą Standard ML i Haskell. A-wyrażenia występują też w wielu zwykłych imperatywnych językach programowania, takich jak Ruby czy C#.

W niektórych językach funkcyjnych (np. w Standard ML) stosuje się bardziej skomplikowany t.zw. typowany \-rachunek. Bez wchodzenia w szczegóły należy zauważyć, że przy klasycznym rozumieniu pojęcia typu wyrażenia, taki rachunek nie jest już zupełny w sensie Turinga. Wynika to z tego, że operator rekursji Fix z przykładu 1.20 pkt. 3 zawiera samoza-stosowania funkcji do siebie samej. Takiej funkcji nie da się przypisać typu. Albo więc należy bardzo zmienić pojęcie typu, albo wykluczyć samozastosowania. Standard ML i inne typowane języki programowania poszły tą drugą drogą, a żeby nie utracić zupełności w sensie Turinga, wprowadziły jawną rekursję jako dodatkowy mechanizm językowy, niezwiązany bezpośrednio z /^-konwersją.

1.3 O językach i gramatykach

Jak już było wspomniane, każdy problem decyzyjny jest równoważny problemowi należenia słowa do pewnego języka. Trudność takiego problemu można więc mierzyć stopniem komplikacji algorytmu akceptacji słów, związanego z językiem. Z kolei akceptacja słów ma związek¹⁴ z ich generowaniem. Klasycznymi generatorami słów są gramatyki, a klasyfikację

¹³Tak więc użyte wyżej mnożenie • nie musi być funkcją predefiniowaną. Odpowiada mu pewne A-wyrażenie, a wykonuje się je przez zastosowanie /3-konwersji do tego A-wyrażenia.

¹⁴ Niezbyt prosty związek.

16