Òåîðåòè÷åñêèå ñâåäåíèÿ. Êàê èçâåñòíî, îäíèì èç îñíîâíûõ ïåðâè÷íûõ ìà-
òåìàòè÷åñêèõ ïîíÿòèé ÿâëÿåòñÿ ïîíÿòèå ÷èñëà. Ïîëüçóÿñü ÷èñëàìè, ñòðî-
ÿò äðóãèå îáúåêòû, áîëåå áëèçêî ïðåäñòàâëÿþùèå ñîäåðæàòåëüíûå ïîíÿ-
òèÿ ïðåäìåòíîé îáëàñòè.  òåîðåòè÷åñêèõ èññëåäîâàíèÿõ “õîðîøèì òî-
íîì” ñ÷èòàåòñÿ ñâåñòè ïîñòðîåííóþ òåîðèþ ê êàêîé-ëèáî çàðàíåå çàäàí-
íîé àðèôìåòè÷åñêîé ñèñòåìå.
Âîçíèêàåò âîïðîñ, òàê ëè óæ íåèçáåæíî èñïîëüçîâàòü â êà÷åñòâå ïåð-
âè÷íîãî îáúåêòà ïîíÿòèå ÷èñëà. Ýòî îäèí èç ñàìûõ ñëîæíûõ âîïðîñîâ
ñîâðåìåííîé ìàòåìàòèêè, ïîïûòêè ïîëó÷åíèÿ îòâåòà íà êîòîðûé ïðèâî-
äÿò ê äàëåêî èäóùèì ïîñëåäñòâèÿì.
Òåì íå ìåíåå ïðè ïîñòðîåíèè êîìáèíàòîðíîé ëîãèêè èëèλ- èñ÷èñëåíèÿ
ñðåäè èñõîäíûõ îáúåêòîâ íåò ÷èñåë. Íåò ëè â ýòèõ ñèñòåìàõ íåäîñòàòêà
â âûðàçèòåëüíûõ âîçìîæíîñòÿõ ? Îêàçûâàåòñÿ, ÷òî â ðàìêàõ êîìáèíà-
òîðíîé ëîãèêè èëè λ-èñ÷èñëåíèÿ ìîæíî óñòàíîâèòü òàêèå êîìáèíàòîðû
èëè, ñîîòâåòñòâåííî, òåðìû, êîòîðûå âåäóò ñåáÿ êàê ÷èñëà. Ýòè ïðåä-
ñòàâëåíèÿ ÷èñåë ïîëó÷èëè íàçâàíèå íóìåðàëîâ. Íóìåðàëû êàê êîìáèíàòî-
ðû óäîâëåòâîðÿþò âñåì çàêîíàì êîìáèíàòîðíîé ëîãèêè. Áîëåå òîãî, ìîæ-
íî óêàçàòü êîìáèíàòîðû, ïðåäñòàâëÿþùèå àðèôìåòè÷åñêèå îïåðàöèè, íà-
ïðèìåð, ñëîæåíèå ÷èñåë. Èññëåäîâàíèÿ â ýòîé îáëàñòè ïîêà âñå åùå äàëåêè
îò çàâåðøåíèÿ.
Çàäà÷à 5.1 Îïðåäåëèòü îáúåêòû, îáëàäàþùèå ñâîéñòâàìè íàòóðàëü-
íûõ ÷èñåë (íóìåðàëîâ) è èññëåäîâàòü èõ ñâîéñòâà.
Ôîðìóëèðîâêà çàäà÷è. Íóìåðàëû - ýòî ñëåäóþùèå îáúåêòû: n¯ =
λxy.(xn)y , ãäå n - íàòóðàëüíîå ÷èñëî èç ìíîæåñòâà {1,2,3, . . . }.
Ïîêàçàòü, ÷òî íóìåðàëû ýòî îáúåêòû ñ õàðàêòåðèñòèêîé:
Ðåøåíèå.
n¯--1. Ôîðìà çàïèñè xny îïðåäåëÿåòñÿ ïî èíäóêöèè:
Òàêèì îáðàçîì, x4y = x(x(x(xy))).
n¯--2. Ïðîâåðèì ïîâåäåíèå îáúåêòîâ n¯ = (SB)n(KI) äëÿ n = 0,1.
¯0 = (SB)0(KI) = KI, ¯0ab = KIab = Ib = b = (λxy.y)ab, ¯1 = SB(KI), ¯1ab = SB(KI)ab = Ba(KIa)b = BaIb
= a(Ib) = ab = (λxy.xy)ab.
n¯--3. Ïðîâåðèì ïîâåäåíèå n¯ = (SB)n(KI) â îáùåì ñëó÷àå.
nab ¯ = (SB)n(KI)ab = SB((SB)n−1(KI))ab ( ïî îïðåäåëåíèþ)
= Ba((SB)n−1(KI)a)b ( ïî ñõåìå (S))
= a((SB)n−1(KI)ab) ( ïî ñõåìå (B))
= a(n−1ab) ( ïî îïðåäåëåíèþ)
= a(an−1b) ( ïî îïðåäåëåíèþ)
= anb = (λxy.xny)ab. ( ïî îïðåäåëåíèþ)
Îòâåò. Íóìåðàëû (λxy.xny) èìåþò âèä (SB)n(KI).
Çàäà÷à 5.2 Îïðåäåëèòü îáúåêò, ïðåäñòàâëÿþùèé îïåðàöèþ “+1”
íà ìíîæåñòâå íóìåðàëîâ è èññëåäîâàòü åãî ñâîéñòâà.
Ôîðìóëèðîâêà çàäà÷è. Ïîêàçàòü, ÷òîσ = λxyz.xy(yz)çàäàåò íà ìíî-
æåñòâå íóìåðàëîâ ôóíêöèþ “ñëåäîâàíèÿ çà” (“ïðèáàâëåíèå åäèíè-
öû”):
Ðåøåíèå.
σ--1. Êîìáèíàòîðíàÿ õàðàêòåðèñòèêà íóìåðàëîâ: nab ¯ = anb.
σ--2. Ïðèìåíèì ôóíêöèþ σ ê íóìåðàëó n¯ â îáùåì âèäå:
Èòàê, σnab ¯ = n+ 1ab, òî åñòü σn¯ = n+ 1.
Îòâåò. Ôóíêöèÿ σ = λxyz.xy(yz) åñòü ôóíêöèÿ ñëåäîâàíèÿ äëÿ íóìåðàëîâ n¯ = λxy.xny.
Çàäà÷à 5.3 Îïðåäåëèòü îáúåêò, âû÷èñëÿþùèé äëèíó êîíå÷íîé ïîñëåäîâàòåëüíîñòè (ñïèñêà)
Ôîðìóëèðîâêà çàäà÷è. Ïîêàçàòü, ÷òî ôóíêöèÿ
Length = λxy.Null x ¯0(σ(Length(Cdr x))y).
åñòü ôóíêöèÿ îïðåäåëåíèÿ äëèíû ñïèñêà x :
Ðåøåíèå.
Length--1. Ââåäåì âñïîìîãàòåëüíûå ôóíêöèè Null è Cdr :
Length--2. ÏðèëîæèìLength ê ïóñòîìó ñïèñêó N il:
Òàêèì îáðàçîì, ôóíêöèÿ Length êîððåêòíà ïî îòíîøåíèþ ê
ïðèìåíåíèþ ê ïóñòîìó ñïèñêó, òî åñòü Length N il = ¯0.
Length--3. Ïðèëîæèì ôóíêöèþ Lengthê ñïèñêó x, ñîñòîÿùåìó èç
îäíîãî ýëåìåíòà: x =< a >:
Ôóíêöèÿ Length êîððåêòíà ïî îòíîøåíèþ ê ïðèìåíåíèþ ê
ñïèñêó, ñîñòîÿùåìó èç îäíîãî ýëåìåíòà, òî åñòü ðàâíà ¯1.
Length--4. Òåïåðü ïðîâåðèìLength â îáùåì ñëó÷àå  , ãäå
çíàê  îçíà÷àåò “íå êîíâåðòèðóåòñÿ ê”:
Îòâåò. ÔóíêöèÿLength äåéñòâèòåëüíî âû÷èñëÿåò äëèíó ñïèñêà. |
Ãëàâíàÿ
Êàòàëîã ôàéëîâ
