  ̌      ̌   
P 46 (2018/2019) 4 25
Računalnik iz domin
N S H, P̌ Š, M Š̌
M: V K
Moderni računalniški centri porabijo enormne
količine električne energije, zato je v času global-
nega segrevanja pomembno, da razmislimo o al-
ternativnih načinih računanja, ki niso električno
potratni. V tem članku nas bo zanimalo, ali lahko
poljuben problem, ki ga lahko izračunamo s stan-
dardnim računalnikom, izračunamo s podiranjem
domin.
Z dominami bomo poskusili simulirati logične iz-
raze in iz teh sestaviti teoretični model računalnika,
imenovan Turingov stroj. Spoznali bomo idejo Chur-
ch-Turingove hipoteze, ki pravi, da naj bi za vsak iz-
računljiv problem obstajal Turingov stroj, ki ga reši.
Torej, če najdemo postopek za sestavo poljubnega
Turingovega stroja iz domin, pokažemo, da lahko
poljuben izračunljiv problem rešimo zgolj s podira-
njem domin. Najprej bomo spoznali, kaj so logični
izrazi in kaj je Turingov stroj. Iz domin bomo zgra-
dili logične izraze, z logičnimi izrazi pa bomo Turin-
gov stroj simulirali. Če se računalnik da simulirati
z dominami, potem se ga da simulirati tudi z vsem,
kar se obnaša podobno kot domine, npr. škatle za
kosmiče, knjige, omare, ali pa kar nebotičniki (vsaj
če si velikan v nizkokvalitetnem ameriškem filmu).
Logični izrazi
Neformalno povedano so logični izrazi funkcije lo-
gičnih spremenljivk, ki so povezane z logičnimi ope-
racijami. Logična spremenljivka lahko zavzame le
resnično vrednost »1« ali neresnično vrednost »0«.
Logične izraze predstavimo s tako imenovano resnič-
nostno tabelo. Vsak izraz lahko zapišemo v obliki
resničnostne tabele, ki nam za vsako možno kombi-
nacijo vrednosti vhodnih spremenljivk poda pripa-
dajočo izhodno vrednost. Operacije, ki so nam rele-
vantne, so:
Negacija:
1 0
0 1
x ¬x
Konjunkcija:
1 1 1
1 0 0
0 1 0
0 0 0
x y x ∧y
Disjunkcija:
1 1 1
1 0 1
0 1 1
0 0 0
x y x ∨y
Strogi ali:
1 1 0
1 0 1
0 1 1
0 0 0
x y x ⊕y
Disjunktivna normalna oblika
Pokazali bomo, da lahko za vsako resničnostno ta-
belo sestavimo logični izraz, ki se obnaša natanko
tako, kot to velí resničnostna tabela.
  ̌      ̌   
P 46 (2018/2019) 426
Primer: Recimo, da želimo dobiti logični izraz, ki
bo pri vseh kombinacijah vrednosti dveh spremen-
ljivk pravilen. Za vsako možno kombinacijo vredno-
sti vhodnih spremenljivk najdemo konjunkcijo, ki je
resnična natanko pri teh vhodih. Za vhod x = 0 in
y = 1 je pripadajoča konjunkcija ¬x ∧ y , saj, če
preberemo izraz, ta pravi, da je resničen natanko te-
daj, ko x ni resničen, y pa je. Na levi strani spodnje
sheme se nahaja resničnostna tabela, ki je vhod na-
šemu postopku. Za vsako vrstico je na desni strani
podan logični izraz, ki je resničen natanko pri kom-
binaciji vhodnih vrednosti podanih v isti vrstici.
1 1 1
1 0 1
0 1 1
0 0 1
x y
rezultat
logičnega
izraza
(¬x ∧¬y)
(¬x ∧y)
(x ∧¬y)
(x ∧y)
→
Nato izraze na desni povežemo z disjunkcijami,
da dobimo izraz, ki je vedno pravilen:
(¬x ∧¬y)∨ (¬x ∧y)∨ (x ∧¬y)∨ (x ∧y)
Primer 2: Recimo, da želimo skonstruirati logični
izraz, ki se obnaša kot naslednja logična tabela:
1 1 0
1 0 0
0 1 1
0 0 1
x y
rezultat
logičnega
izraza
V tem primeru potrebujemo logična izraza, ki bo-
sta pravilna zgolj za vhode v prvih dveh vrsticah ta-
bele. Oba logična izraza povežemo z disjunkcijo, da
dobimo nov logični izraz, ki je pravilen pri natanko
zgornjih dveh vhodih.
www.dmfa-zaloznistvo.si
1 1 0
1 0 0
0 1 1
0 0 1
x y
rezultat
logičnega
izraza
(¬x ∧¬y)
(¬x ∧y)
→
ց
(¬x ∧¬y)∨ (¬x ∧y)
Vidimo, da bodo izrazi, zgrajeni na tak način, ve-
dno podobne oblike, to je, več konjunkcij, povezanih
z disjunkcijami. Pravimo, da so ti izrazi v disjunk-
tivni normalni obliki. Iz primerov zgoraj je razvi-
dno, da lahko logični izraz v disjunktivni normalni
obliki zgradimo za poljubno resničnostno tabelo. To
pomeni, da lahko iz negacije, disjunkcije in konjunk-
cije zgradimo poljuben logični izraz. Če je vhodnih
spremenljivk več, bo dolžina tega izraza naraščala
eksponentno. To v praksi sicer ni optimalno, ven-
dar, ker nas zanima zgolj »Ali se da?« in ne »Ali se da
učinkovito?« se zadovoljimo tudi z zelo ogromnimi
formulami, če le opravijo delo.
Poln nabor operatorjev
Če lahko iz nabora operatorjev sestavimo poljuben
logični izraz, pravimo, da je tak nabor operatorjev
poln. Dokažimo, da lahko sestavimo poln nabor tudi
z manj operatorji. Najlažji način je, da z novim na-
borom izrazimo nabor, za katerega že vemo, da je
poln, torej {¬,∧,∨}. Negacija (¬) in disjunkcija (∨)
sta poln nabor, saj lahko konjunkcijo x ∧ y po De
Morganovem zakonu izrazimo z ¬(¬x ∨¬y)
Logične operacije iz domin
Z dominami lahko modeliramo logične operacije. Lo-
gični izraz bomo zapisali kot zaporedje domin, tako
da bo podiranje domin služilo kot proces računanja.
Podrte domine predstavljajo logično vrednost 1, sto-
ječe pa logično vrednost 0. Vrednost vhodnih spre-
menljivk vnesemo tako, da podremo pripadajoče vr-
ste domin, nato pa počakamo, dokler se proces po-
diranja domin ne zaključi. Na drugi strani zaporedja
podrte oziroma stoječe vrste predstavljajo izhodno
vrednost spremenljivk.
Računanje v notranjosti zaporedja poteka preko
logičnih operacij, ki jih sestavimo iz domin. Upora-
  ̌      ̌   
P 46 (2018/2019) 4 27
bljene logične operacije so predstavljene na slikah
1, 2 in 3. Na skicah se domine podirajo od spodaj
navzgor.
Dokažimo, da je nabor {∨,⊕,1}, ki smo ga sesta-
vili iz domin, poln. Konstanto 1 predstavimo kot vr-
sto domin, ki jo na vhodu zagotovo podremo, preo-
stali dve operaciji pa sta bili predstavljeni na slikah
1, 2 in 3.
1 1 0
1 0 1
1 y x ⊕ 1 = ¬x
Iz tega lahko zaključimo, da iz domin lahko sesta-
vimo tudi nabor {¬, ∨}, za katerega smo že dokazali,
da je poln. Torej lahko iz domin sestavimo poljuben
logični izraz.
Turingov stroj
V tem razdelku vpeljemo skico definicij in nekate-
rih dokazov v zvezi s Turingovim strojem. Ker gre
za matematično precej kompleksen model, se bomo
natančnim definicijam ognili. Bralec, ki ga zanima
točna izpeljava, lahko to najde v knjigi [1]. Turingov
stroj je abstrakten model računanja, ki sledi strogim
navodilom. Deli takšnega stroja so:
Neskončen trak – To je spomin, na katerem so na-
pisane 0, 1 (vhodni podatki) in prazna polja. Spo-
min je neomejen.
Glava – Glava po traku bere in zapisuje podatke.
V vsakem koraku se nahaja nekje na traku, kjer
vsebino polja lahko prebere in prepiše, nato pa se
premakne za največ eno polje levo ali desno.
Stanja in prehodi med njimi – So stroga, natančna
navodila za delovanje stroja. V vsakem koraku je
stroj v enem izmed sranj. Glede na trenutno sta-
nje stroja in znak pod glavo, prehodi natančno do-
ločajo, kaj glava zapiše na trenutno mesto, kam se
premakne in v katerem stanju bo Turingov stroj v
naslednjem koraku.
Alan Turing si je Turingov stroj zamislil leta 1936
in z njim matematično opredelil pojem računalnika
in izračunljivosti. Turingovi stroji so po zmožnosti
tega, kaj je z njimi mogoče izračunati, ekvivalentni
računalniškim programom.
SLIKA 1.
Kopiranje: Iz enega vhoda dobimo dva izhoda (kopiranje vre-
dnosti vhodne spremenljivke). Ta vrata uporabimo, če se neka
spremenljivka v izrazu pojavi več kot enkrat.
SLIKA 2.
Disjunkcija dveh vhodnih spremenljivk
SLIKA 3.
Strogi ali dveh vhodnih spremenljivk
  ̌      ̌   
P 46 (2018/2019) 428
Turingov stroj ima končno število stanj in je v vsa-
kem trenutku v enem izmed teh stanj, zato ga lahko
predstavimo z nizom ničel in enic. Za fiksne vho-
dne podatke so izhodni podatki vedno enaki in po-
novljivi, saj rezultat ni odvisen od zunanjih dejavni-
kov ali naključja.
Church-Turingova hipoteza
Church-Turingova hipoteza pravi, da za vsak izra-
čunljiv problem obstaja Turingov stroj, ki ga reši.
Torej, če Turingov stroj, ki reši problem, ne obstaja,
je problem neizračunljiv tudi z najmočnejšim raču-
nalnikom. To je le hipoteza in je ne moremo do-
kazati, a vseeno služi kot definicija izračunljivosti.
Resnična je za vse do sedaj znane praktične modele
računanja.
Simulacija Turingovega stroja z logičnimi izrazi
Ker bi bil temeljit dokaz obsežen in zahteven, bomo
skicirali zgolj glavne točke. Nadobudnega bralca pa
vzpodbujamo, naj si več prebere v literaturi [1]. Glav-
ne točke dokaza:
Turingovega stroja ni mogoče predstaviti le z
enim končnim logičnim izrazom. Vsak logični iz-
raz ima fiksno velikost, vhod Turingovemu stroju
pa je lahko poljubno velik. Zato popravimo naš cilj
in Turingov stroj predstavimo z družino izrazov:
Za vsako dolžino niza vhodnih podatkov drugačen
logični izraz.
Z logično funkcijo predstavimo i-ti korak Turingo-
vega stroja. Vemo, da je stanj Turingovega stroja
končno mnogo. Vhodnih podatkov Turingovemu
stroju je bilo prav tako končno mnogo in zaradi
popravljenega cilja vnaprej znano (recimo, da je
bilo popisanih d elementov traku), torej je po i ko-
rakih zagotovo popisanih največ d+i polj traku. Iz
tega zaključimo, da je vhodnih (in izhodnih) spre-
menljivk naši logični funkciji končno mnogo in jo
lahko sestavimo iz domin.
Iz zgornjih dveh alinej zaključimo, da lahko rezul-
tat enega koraka Turingovega stroja izračunamo z
dominami.
Če poznamo zgornjo mejo števila korakov Turin-
govega stroja, ga torej lahko predstavimo kot
kompozicijo funkcij, ki izračunajo posamezne ko-
rake. Žal pa se nekateri Turingovi stroji nikoli ne
ustavijo, zato bi za simulacijo takih strojev potre-
bovali neskončno mnogo domin.
Praktična izvedba
Nekateri Turingovi stroji se na nekaterih vhodih ne
ustavijo, ampak računajo v nedogled. Da bi tak ra-
čun simulirali, bi torej potrebovali neskončno mnogo
domin, ali pa tekoči trak in robota, ki bi domine po-
stavljal hitreje, kot se podirajo. Posledično je sestava
Turingovega stroja zelo težka. Vzrok za to izhaja iz
narave domin, saj se vsaka domina podre samo en-
krat – realizacija povratnih zank ni mogoča. Kljub
temu so preproste programe, kot je seštevanje dveh
števil, že sestavili iz domin, posnetki teh eksperi-
mentov pa so dostopni na spletnemu portalu You-
tube.
Vabilo na MaRS 2019
Zgornji članek je nastal kot povzetek projekta, izde-
lanega na matematičnem taboru MaRS 2018. Bralce
vabimo, da se nam pridružijo prihodnje leto, več na
http://mars.dmfa.si/.
Literatura
[1] M. Sipser, Introduction to the Theory of Computa-
tion, Course Technology, second edition, 2006.
×××