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

13

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.XX:LLL

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.XLL

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?LLLf:LLX

Nataniel
źródło

Odpowiedzi:

6

λLL

δ:L2L

δ(M,N)={True if M=βηNFalse otherwise
λD
D M N=βηδ(M,N)
M,NL

FnNP1,,Pn

F x P1Pn=βηx Q1Qk

kQ1,,QkDδD

cody
źródło