Утицај математике на настанак и темеље рачунарства (2. део)
Аутор: Недељко Стефановић
Геделови и Тјурингови резултати
Још је Еуклид схватио да се не могу сви ставови доказати, већ да се мора поћи од неких почетних ставова из којих се изводе остали. Од њега потиче аксиоматски метод. Касније је уочено да исто важи и за појмове. Не могу се сви дефинисати, већ се од неких мора поћи (осим ако прихватимо индуктивно увођење појмова преко примера и контрапримера, што има предности и мане, а које у заснивању математике није прихваћено). Аксиоматски метод се развијао, а немачки логичар Готлоб Фреге (1848-1925) уочио је да и саму логику на коју се ослањају аксиоматске теорије треба некако описати.
Формална теорија се састоји најпре од неког изабраног скупа симбола, затим од скупа формула, које су ништа друго до неки изабрани коначни низови симбола, затим од аксиома, које су, такође, неке од изабраних формула и од неких изабраних правила извођења, по којима се од неких формула добија нека друга формула. Теореме су онда формуле које се могу добити полазећи од аксиома коначном применом правила извођења.
Овакав приступ, који не захтева удубљивање у значење аксиома, формула и правила, омогућава да рачунари, који не могу да се удубе у садржај, већ само раде по строго дефинисаном скупу механичких правила, могу да се примењују на сложене математичке теорије.
Међутим, треба нагласити да тиме математика није шаблонизована. Такви системи се могу упоредити са шаховском игром. Она је дефинисана једноставним правилима игре, чије познавање омогућава проверу да ли је ток партије исправан и који је коначан исход игре, али не обезбеђују успех у игрању шаха, већ је за то потребна и вештина вођења шаховских фигура. Тако је за формалне теорије могуће написати програм који проверава исправност доказа теорема у тој теорији, али је проблем проналажења доказа теорема далеко сложенији.
Осим тога, намеће се питање моћи тог приступа. Са једне стране, свака теорија има свој језик, а сваки језик има ограничену изражајну моћ, тј. на њему није могуће изразити било шта. Самим тим, од теорије се не може очекивати да одговори на било каква питања, већ само на она која се могу поставити на њеном језику. Онда се намеће питање да ли теорија може да одговори на сва таква питања. За такве теорије се каже да су потпуне.
Геделови резултати
Аустријско-амерички математичар (логичар) Курт Гедел (1906-1978) бавио се управо овим питањима. Доказао је да се математика не може формализовати на непротивречан начин тако да тај формализам може да да одговор на свако питање које се у оквиру њега може поставити. Међутим, овај исказ у наведеној формулацији заправо није тачан. Елементарно је логичко тврђење да се сваки непротивречан формалан систем може допунити до непротивречног и потпуног формалног система.
Стога је Гедел увео још један услов – да су аксиоме и правила алгоритамски описиви. То заправо значи да имамо потпуно дефинисан поступак на основу кога знамо да ли је нека формула аксиома и да ли је нека формула непосредно изводива из неких других формула по неком од правила извођења. Тај услов је природан, јер у супротном нема превише смисла систем сматрати формалним. То је уједно данашњи степен развоја у заснивању математике и мада немамо потпуне формализације математике, постоји формализација која представља основне математичке принципе прихваћене од стране највећег броја математичара.
Но, пошто је то саставни део формулације и доказа, било је неопходно да се сам појам алгоритма опише математички, тј. формално, а Геделов тзв. систем рекурзивних функција јесте прво свођење појма алгоритма на коначан број једноставних правила.
Тјурингови резултати
Тај систем, међутим, није био подесан за реализацију у виду машине. Мада би начелно то било могуће, таква би машина била много сложенија, него што је неопходно, јер Гедел то није имао у виду будући да је тај систем осмислио за сасвим другу сврху. Након објаве Геделовог рада „О формално неодлучивим исказима принципа математике и сродних система” (1931), Гедел је (1934) држао предавања на семинару на Универзитету у Принстону. Предавања су кулминирала објављивањем научних радова других истраживача, од којих је за настанак рачунара најзначајнији рад британског математичара Алана Тјуринга „О израчунљивим бројевима са применом на проблем одлучивости” (1936), у коме је Тјуринг дао потпуно другачије заснован, еквивалентан опис алгоритма, који је садржао и опис једноставне машине која по том опису алгоритма може да ради. Штавише, алгоритам је описан управо описом такве машине.
Нажалост, убрзо је избио Други светски рат, а ова открића су примењена на разбијање немачке војне шифре „енигма”. Машинско шифровање је иначе постојало и у Првом светском рату, али није било могућности да се таква машина направи, јер су недостајала ова открића. Но, да до Другог светског рата није дошло, рачунари би се свакако користили у неке хуманије сврхе јер се до потребних открића већ дошло, тако да том рату немамо на чему да се захвалимо (прим.аут.).
Ту се одмах намеће питање како знамо да су тиме обухваћени сви алгоритми. Такозвана Черч-Тјурингова теза тврди да се овако уведен појам алгоритма поклапа са интуитивним схватањем алгоритма, али пошто учествује један нематематички појам, она није математичко тврђење, па се не може доказати математичким средствима.
Но, то не значи да не можемо рећи ништа о том питању. Прво, сматра се да пошто постоје суштински различити приступи опису појма алгоритма, сви они доводе до истог скупа алгоритама (еквивалентност познатих система израчунљивости је математичка теорема), што представља једну емпиријску потврду Черч-Тјурингове тезе. Наравно, такав аргумент није математички, иначе би Черч-Тјурингова теза била теорема.
Такође, ти системи израчунљивости покривају све нумеричке алгоритме потребне за решавање једначина постојећих физичких теорија. Стога, да бисмо направили поуздану машину, која решава неки детерминистички задатак са једнозначним резултатом (чему служе алгоритми у својој основној формулацији), било би неопходно открити неке до сада непознате природне појаве које се не могу описати законима, а који се могу нумерички решавати алгоритмима обухваћеним постојећим описима појма алгоритма.
Постојање вероватносних физичких теорија не мења ништа, јер се за поуздане машине може на основу почетног стања нумерички одредити највероватније завршно стање. Ипак, ова аргументација се може применити само на вештачке машине, које су направљене свесно на основу тренутног знања коначне сложености, а не и на људски мозак, који је настао спонтано еволуцијом, на основу природних закона који нису у потпуности проучени и за које се не зна какав им је стваран облик и колика им је стварна сложеност (прим.аут.). Научне теорије су само тренутно људско разумевање природе, која се њима описује само приближно и делимично, а напредак науке се састоји у томе што оне временом постају све тачније и све потпуније.