e-gradiva				Sistemi	Motorola	Omrežja
						SERŠ Maribor

Računanje in izračunljivost

Pojem "računanje", kot ga uporabljamo v vsakdanjem življenju in kot smo ga uporabljali do sedaj, je intuitiven in zato neuporaben za matematično dokazovanje. če želimo odgovoriti na vprašanja o tem, kaj bi lahko kakršenkoli računalnik izračunal, moramo najprej strogo definirati tako računanje, kot tudi izračunljivost.

Za naše namene je y skladu z navadami v matematiki primerno definirati računanje kot določanje vrednosti neki funkciji f(x), kjer je x vhodni podatek, z = f(x) pa iskani rezultat. Pri tem imajo f, x in z zelo široko interpretacijo. Funkcija f je lahko numerični izračun, dokaz nekega izreka, pisanje na datoteko, itd. Podobno sta x in z lahko števiii, z besedami izražen stavek, program za vzdrževanje datotek, itd.

V skladu s to definicijo je potem smiselno reči, da je neka funkcija f(x) izračunljiva, če obstaja postopek za njeno računanje za vse vrednosti x, za katere je definirana. Pri tem privzemimo, daje moč množice x kvečjemu števno neskončna. Z drugimi besedami, obstajati mora navodilo, s katerim lahko izračunamo f(x) v končnem številu korakov. Navodilu, ki v končnem številu korakov pripelje do želenega rezultata, pravimo algoritem. Formalno lahko defmiramo, da je neka funkcija izračunljiva natanko takrat, kadar obstoja algoritem za njeno računanje.

Taki definiciji računanja in izračunljivosti se zanesljivo dobro ujemata z intuitivnim razumevanjem teh dveh pojmov in tudi z izkušnjami iz vsakodnevnega življenja. Za matematika pa to ne zadošča. Osnovni problem je v tem, da je pojem algoritem komaj kaj manj intuitiven kot pojem izračunljivost. če naj bo uporaben za strogo dokazovanje, nujno potrebujemo njegovo strogo defmicijo. Strogo definiranje kompleksnega intuitivnega pojma, kot je algoritem, pa nikakor ni preprosta zadeva.

če želimo razumeti kako je prišlo do danes veljavne definicije, se moramo vrniti v zgodovino. Leta 1900 je sloviti nemški matematik David Hilbert na mednarodnem kongresu matematikov v Parizu izzval matematični svet s seznamom pomembnih še nereš enih problemov. Triindvajseti problem na seznamu se je nanašal na odkritje postopka za ugotavljanje resničnosti ali neresničnosti poljubne trditve v jeziku matematične logike, ki se imenuje predikatni račun. Namesto izrazov resničnost ali neresničnost trditve se pogosto uporabljata izraza dokazljivost ali nedokazljivost formule.

Hilbert je implicitno predpostavljal, da so vse formule v predikatnem računu ali dokazljive (resnične) ali nedokazljive (neresnične); problem je samo, kako najti postopek za ugotavljanje v katero skupino spada katera. Leta 1931 pa je avstrijski matematik Kurt Gödel, ki je delal v ZDA na Institute for Advanced Study v Princetonu, dokazal, daje ta predpostavka napačna. Gödel je dokazal, da v vsakem aksiomatskem sistemu, ki je dovolj močan, da se z njim lahko izrazi običajna aritmetika, obstajajo tudi formule, ki niso niti dokazijive (resnične) niti nedokazljive (neresnične). O teh formulah ne moremo reči ničesar, zato jih običajno imenujemo neodločljive (undecidable).

Na sliki je problem za lažje razumevanje prikazan grafično. Tu povejmo, da Gödelov rezultat ne velja samo za predikatni račun, temveč za vse aksiomatske sisteme, ki so dovolj močni, da lahko izrazijo aritmetiko.

Hilbertov 23-ti problem je torej nerešljiv. Pojavil pa se je soroden problem: ali je mogoče razlikovati dokazijive formule od nedokazljivih in neodločljivih? Bolj natančno, ali obstaja postopek, ki glede na podan sistem aksiomov, vedno prepozna dokazijive formule. Oziroma z drugimi besedami, ali obstaja postopek, ki bo pri vsaki dokazljivi formuli, ki mu jo damo v obdelavo, zapisal "da", pri nedokazljivih in neodločljivih pa "ne"?

Najvidnejši raziskovalec s področja matematične logike v letih takoj po Goedelovem dokazu je bil Alonzo Church s Princetonske univerze. Church je skupaj z dvema od svojih študentov razvil formalni jezik, imenovan lambda račun. V tem jeziku je mogoče izraziti velike razrede matematičnih funkcij vključno z vsemi, ki jih je uporabil Gödel. Church je trdil, da je vsako izračunljivo matematično funkcijo mogoče definirati v lambda računu. Potem je dokazal, da bi obstoj neke v lambda računu definirane neizračunljive matematične funkcije pomenil, da ne more obstajati splošen postopek za ugotavljanje, ali je neka formula dokazijiva. Aprila 1936 je Church objavil v lambda računu definirano logično funkcijo, ki ni izračunljiva in s tem dokončno ovrgel Hilbertovo tezo..

Nekoliko poenostavljeno povedano lahko povzamemo, daje bilo leta 1936 v matematiki sprejeto spoznanje, da v splošnem znotraj vsakega (dovolj kompleksnega) aksiomatskega sistema obstajajo tudi formule, ki jih ne moremo niti dokazati niti ovreči. Poleg tega ne obstaja postopek s katerim bi lahko te formule razlikovali od dokazljivih. Takoj omenimo, da to seveda ne pomeni, da sploh ne moremo ugotavljati resničnosti formul ali trditev. Nasprotno, zelo veliko formul lahko dokažemo za resnične ali neresnične - ne moremo pa vseh.

Pomembna ugotovitev, ki sledi iz vsega povedanega je, da obstajajo problemi, ki so v principu nerešljivi in to tako za računanje na ročni kot na strojni način. Ali drugače povedano, nekateri problemi so neizračunljivi ne glede na to kako se jih lotimo. Ta ugotovitev je prav gotovo pomembna za razvoj računalnikov, saj opozarja na nesmiselno st poskusov zgraditi stroj, ki zna izračunati vse. Še bolj koristna pa postane, če si jo ogledamo v obliki, ki jo je našel angleški matematik Alan M. Turing.

Neodvisno od Churcha in v približno istem času je tudi Turing dojel povezanost ideje izračunljive funkcije s Hilbertovim problemom. Njegova pot do rešitve pa je bistveno bolj neposredna in za večino tudi razumljivejša od Churchove. Zanjo je izumil preprost, vendar matematično strog model računanja. Ta matematični model, ki ga danes poznamo pod imenom Turingovi stroji, je Turing objavil leta 1936.

Ne da bi se spuščali v podrobnosti dokazovanja, lahko rečemo, da je sestavljena iz naslednjih dveh delov:

1. Prvi del je formalna defincija izračunljivosti. Turing je postavil naslednjo definicijo: neka matematična funkcija je izračunljiva, če jo je mogoče v končnem številu korakov izračunati na enem od Turingovih strojev. Ta definicija je ekvivalentna Churchovi - da je funkcija izračunljiva, če jo je mogoče definirati v lambda računu.
2. Drugi del predstavlja uporaba Cantorjevega dokaza o eksistenci neštevnih kardinalnih števil, ki ga je Turing uporabil za dokaz, da obstaja več funkcij kot Turingovih strojev. To z drugimi besedami povedano pomeni, da obstajajo neizračunljive matematične funkcije.

Gor     Sistemi     Motorola 68XX      Računanje     Turingov stroj 

SERŠ Maribor, Strokovna gimnazija, leto: 2003/04, avtor: Gregor Bohak