i
i
“Hafner-Stroji” — 2010/5/28 — 10:41 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 14 (1986/1987)
Številka 4
Strani 212–215
Izidor Hafner:
McCULLOCHOVI STROJI
Ključne besede: matematika, razvedrilo.
Elektronska verzija: http://www.presek.si/14/849-Hafner.pdf
c© 1987 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
1" '-'Tl~l"I-'-Il~1-''" ICI" I n
MCCULLOCHOVI STROJI
V knjigi The lady or the tiger je Raymond Smullyan uvedel novo vrsto logičnih
nalog. V teh je treba najti kombinacijo znakov, ki mora izpolnjevati določene
pogoje.
Recimo, da imamo na razpolago le nize črtic . Niz n črtic, to je 11 1...1, naj
pomeni naravno število n. Potem lahko definiramo pojem "Iiho število" takole :
1. I je liho število.
2. Če je X liho število, potem je tudi X II liho število.
Kako bi preverili, da je IIIII liho število? PO drugem pogoju bo 1111Iliho ,
če je III liho. Po istem pogoju bo III liho, če je I liho . Toda lje liho po pravilu
1, to rej je liho tudi III oziroma 11111.
Takšne naloge imajo še drug pomen. V programskem jeziku prolog je pro-
gram množica takšnih pogojev. Prologov interpreter pa rešuje nalogo na podo-
ben način, kot smo jo mi.
Vrnimo se k Smullyanovi knjigi.
Inšpektor Craig je obiskal prijatelja McCullocha, ki se je ukvarjal z izdelavo
čudnih strojev, prednikov današnjih računalnikov. Seveda se je vse to dogajalo
precej pred izumom prvih elektronskih računalnikov. Ko sta se že nekaj časa
pogovarjala, katera števila stroj sprejme in katerih ne, se je njun pogovor nada-
ljeval takole:
"Dovoli, da ti pojasnim pravila ," je nadaljeval McCulloch. "Število zame
pomeni naravno število; moj stroj za zdaj ne računa z negativnimi števili in
ulomki. Število N zapišemo na običajen način kot zaporedje znakov O, 1,2,3,
4,5,6,7,8,9. Toda stroj lahko sprejme le števila, v katerih O ne nastopa, na
primer, 23 in 5492, ne pa 502 ali 3250607 . Vzemimo dve števili : N, M . Potem
NM ne pomeni N krat M, pač pa je NM število, ki ga dobimo tako , da na]-
prej zapišemo N, nato pa pripišemo M. Recimo, da je N števi lo 53, M pa 728,
potem je NM število 53728."
"Kakšna čudna operacija s števili," se je začudil Craig.
"Vem," je odvrnil McCulloch , "toda to operacijo stroj razume najbolje.
Kakorkoli že, naj ti razložim pravila te operacije. Pravim, da število X produci-
ra število Y, če stroj sprejme število X in če potem, ko ga damo v stroj, iz
stroja pride kot rezultat število Y. Prvo pravilo je tole:
Pravilo 1: Za poljubno število X je število 2X (to je 2, ki mu sledi X, ne
212
pa 2 krat X) sprejemljivo in 2X produci ra x."
" Recimo, 253 producira 53; 27482 producira 7482. D rugače povedano, če
vstavimo 2X v stroj, nam le-ta zbriše 2 na začetku in to, kar ostane, X, stroj
vrne. "
"To je precej enostavno ," je odgovoril Cra ig. " Katera so ostala pravila?"
"Samo še eno prav ilo je," je odgovoril McCulloch, "toda prej moram
op redeliti še tole: številu X2X pravim pridruženo štev ilo k številu X. Torej je
727 pridruženo k št evilu 7. Drugo pravilo je takole:
. Pravilo 2: Če X producira Y , potem 3X producira število, ki je pridruženo
k Y (to pa je Y2 Y) .
" Na pr ime r: 27 producira 7 po prvem pravilu . Zato 327 producira 727 , ki
je prid ruženo k 7."
Zdaj pa zastav imo nekaj nalog z našim strojem .
1. Poišči število N , ki producira samo sebe.
2 . Poišč i število N , ki p roducira N2N.
3. Po išči število N, ki producira 7N.
4. Poišč i takšno štev ilo N, da štev ilo 3N producira N2N.
Reš itve
Najprej zapiš imo pravili simbolično. Izjava
X producira Y
seveda pomeni, da X producira Y. Uporabimo še implikacijo in pravili se
glasita :
Prav ilo 1: 2X producira X.
Prav ilo 2 : X produci ra Y =>3X producira Y2 Y.
V nadaljevanju bomo zA, B, .., zaznamovali nize iz znakov 1 - 9 vključno
s praznim nizom . X, Y, N pa pomenijo neprazne nize.
1. Iščemo takšno šte vilo, da bo veljalo
N producira N
Prvo prav ilo ne pride v poštev . Če hočemo uporabiti drugo, mora veljati
3X = N in Y2 Y = N ter X producira Y
Ker mora biti 3X = Y2 Y, se mora Y začeti s 3: Y = 3A . Torej
3X = 3A 23A, X =A 23A
A 23A producira 3A
213
Če je A prazen niz, je to že rešitev, saj
23 producira 3
po pravilu 1.
N= 3X= 323
2. Iščemo število N, da velja
N producira N2N
Po drugem pravilu mora biti
N = 3X, N2N = Y2 Y, X producira Y
Prvi dve enačbi zahtevata
3X23X = Y2Y
to je Y = 3X, in veljati mora še X producira 3X.
Po drugem pravilu mora biti
X = 3X', 3X = Y'2 y', X' producira Y'
Prvi dve enačb i dasta
33X' = Y'2Y'
Zato Y' = 33A, 33X' =33A 233A, X ' =A 233A. Seveda mora biti še
A 233A producira 33A
Če vzamemo za A prazen niz, po pravilu 1 velja: 233 producira 33. Torej
N = 3X = 33X' = 33233
3. Kdaj velja: N producira 7N? Veljat i mora
N=3X, 7N=Y2Y, X producira Y
Od tod 73X = Y2 Y, Y = 73A, 73X = 73A 273A, X =A 273A. Veljati mora
še A 273A producira 73A. Za A vzamemo prazen niz, saj 273 producira 73 .
N = 3X = 3273.
4. 3N producira N 2N?
3N = 3X: N2N = Y2 Y, X producira Y
N =X = Y, X producira X
PO nalogi 1 je N = 323 .
214