Wyrażenie kombinatora (powiedzmy na podstawie SK) można traktować jako funkcję, która odwzorowuje wyrażenia rachunku kombinatora na wyrażenia rachunku kombinatora. To znaczy, można myśleć o wyrażeniu jako funkcji X : L → L , gdzie L jest zbiorem wszystkich poprawnych pod względem składniowym wyrażeń kombinatorycznych w podstawie SK. To mapowanie jest wykonywane przez zastosowanie danych wejściowych do wyrażenia, a następnie zredukowanie do normalnej postaci w celu uzyskania danych wyjściowych.
Ponieważ podstawą SK Turinga kompletne, można naiwnie myśleć, że istnieje SK wyrażenie , który implementuje każdy obliczalna funkcja od L do L . Jednak wyraźnie tak nie jest, ponieważ wynik redukcji zawsze będzie miał normalną formę. Oznacza to, że wyrażenie nie może mieć wyjścia, które nie jest w normalnej formie.
Zamiast tego mogłem myśleć o wyrażeniach rachunku SK jako odwzorowaniu na L ′ , gdzie L ′ jest zbiorem wyrażeń SK w normalnej formie. Czy to przypadek, że na każdej mapie obliczeniowego f : L ' → L ' , istnieje SK wyrażenie X , który implementuje tę mapę? Czy też istnieją dalsze ograniczenia dotyczące zestawu funkcji, które mogą być obliczane przez wyrażenia rachunku kombinatorycznego w ten sposób?
źródło