Jakie funkcje mogą obliczać wyrażenia rachunku kombinatorycznego?

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.$X$$X:L \to L$$L$

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.$X$$L$$L$

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?$L'$$L'$$L'$$f:L'\to L'$$X$

$\lambda$$L'\to L'$

$\delta:L'^2\to L'$

$$\delta(M, N) = \cases{\mathrm{True}\mbox{ if }M=_{\beta\eta}N\\ \mathrm{False}\mbox{ otherwise}}$$ $\lambda$$D$ $$D\ M\ N =_{\beta\eta} \delta(M,N)$$ $M,N\in L'$

$F$$n\in\mathbb{N}$$P_1,\ldots,P_n$

$$F\ x\ P_1\ldots P_n =_{\beta\eta} x\ Q_1\ldots Q_k$$

$k$$Q_1,\ldots,Q_k$$D$$\delta$$D$