In die jaar 1900 het David Hilbert ʼn konferensie toegespreek waarin hy voorspel het watter wiskundige probleme die belangrikste vir die volgende eeu sou wees. Hilbert was in die kol met die 23 areas in wiskunde wat hy geïdentifiseer het as die hoofkoers van wiskunde in die twintigste eeu. Ten spyte daarvan dat die rekenaar opsigself nie een van Hilbert se voorspellings was nie, het twee areas wat deur Hilbert geïdentifiseer is gemanifesteer as uiters belangrik vir rekenaarwetenskap.

Hilbert wou eerstens hê die verwarring in versamelingsteorie moet opgelos word, en tweedens was hy nie tevrede daarmee dat alle wiskundig bewysbare resultate as waar aanvaar is nie. Hy het in gedagte gehad om ʼn omvattende rekenkunde te ontwikkel wat analises kon doen en terselfdertyd teenstrydighede of paradokse sou vermy. Die idee was om met die aksiomatisering van klassieke rekenkunde (arithmetic) te begin en dit dan te formaliseer. Tydens die formaliseringsproses word die tradisionele wiskundige inhoud verwyder; die oorblywende kenmerke is suiwer formeel. Die taak van die formalis was om aan te toon dat die resulterende formalisme ʼn konsekwente asook volledige, formele bewys van klassieke rekenkunde voorsien.

Een van die sentrale probleme waarmee die sogenaamde formalis gekonfronteer is, was om ʼn definitiewe eindige prosedure (algoritme) te vind wat gebruik kon word om ondubbelsinning te besluit oor die bewysbaarheid van enige bewering in geformaliseerde wiskunde. Sodanige algoritme moet dus ʼn ja- of nee–antwoord voorsien wat aandui of ʼn stelling voldoen aan al die voorwaardes van die formalisme (versameling van aksiomas) en of die stelling universeel waar is of nie. Die probleem, soos hierbo beskryf, staan bekend as Hilbert se Entscheidungsproblem (of dan besluitnemingsprobleem in Afrikaans).

Die hieropvolgende paragrawe sluit ʼn kort beskrywing van die status quo van wiskundige bewysbaarheid met die draai van die 19de eeu in. Daar word gewys op die bydrae van versamelingsteorie wat een van die mees filosofiese belangrike stellings in teoretiese rekenaarwetenskap bewys. Daarna word kortliks ʼn bespreking gegee van hoe die ontwikkeling van berekenbaarheid en rekenaars kousaal gedeeltelik verband hou met ontwikkelings in die voorgenoemde twee wiskundige navorsingsvelde.

Wiskundig bewysbare resultate: Watter stellings het bewyse en hoe kan ons die bewyse genereer?

Wiskundiges soos Church, Kleene, Post, Markov, Von Neuman, Gödel en Turing het almal, meestal onafhanklik van mekaar, aan hierdie probleme gewerk. Hierdie wiskundiges het almal baie eenvoudige versamelings van boublokke voorsien wat gelyk het na die “atome” waarvan wiskundige algoritmes gebou kan word. Gödel en Turing het albei afsonderlik geantwoord op Hilbert se Entscheidungsproblem van 1928.

In 1931 het Kurt Gödel sy welbekende “incompleteness”-stelling bewys, waarin hy aantoon dat enige wiskundige stelsel noodwendig stellings het wat nie as waar of onwaar bewys kan word nie. Hierdie stelling het geïllustreer dat daar geen oplossing vir Hilbert se besluitnemingsprobleem is nie. Turing se ontwikkeling van sy universele berekeningsmasjien, waarna daar oor die algemeen verwys word as ʼn Turing Masjien (TM), was ook ʼn antwoord op die uitdaging van die besluitnemingsprobleem. Turing het naamlik die haltprobleem gebruik om aan te dui waarom Hilbert se besluitnemingsprobleem nie ʼn oplossing het nie.

Versamelingsteorie

Vanuit ʼn filosofiese perspektief is die haltprobleem een van die mees belangrike probleme in teoretiese rekenaarswetenskap, aangesien dit demonstreer dat nie alle probleme met algoritmes opgelos kan word nie. Die onbeslisbaarheid van die haltprobleem is destyds bewys deur van ʼn tegniek genaamd diagonalisering gebruik te maak. Diagonalisering is in 1873 deur die wiskundige Georg Cantor ontdek.

Cantor het homself met die meting van twee oneindige versamelings bemoei. Hy het gevra: “Indien ons twee oneindige versamelings het, hoe kan ons bepaal of die een versameling groter as die ander is en of hul dalk dieselfde grootte is?” Ten einde hierdie vraag te beantwoord het hy die diagonaliseringstegniek ontwikkel en gebruik.

Hierdie bevindinge het alle hoop op Hilbert se meganisering van wiskunde vernietig. Selfs die hoop om te kan bepaal of ʼn arbitrêre gekose probleem meganies opgelos kan word, is daarmee heen. Met ander woorde, die hoop om meganies te kan bepaal watter probleme is berekenbaar is laat vaar. Turing se model het egter van so ʼn eenvoudige stel wiskundige instruksies gebruik gemaak dat die moontlikheid bestaan het om in der waarheid ʼn fisiese model van Turing se idee te konstrueer.

Alhoewel daar dikwels gesê word dat die 1936-publikasie van Turing nie werklikwaar die praktiese ontwikkeling van rekenaars beïnvloed het nie, hou Minsky (medestigter van MIT, oftewel die Massachusetts Instituut van Tegnologie) voet by stuk dat Turing se publikasie teen die intellektuele agtergrond van ʼn verskeidenheid van idees gesien moet word wat handel oor beskrywings en prosesse. Turing se antwoord op die vraag “Watter prosesse kan beskryf word?” is verwant aan algoritmes, berekenbaarheid en rekenaars. Die woord “beskrywing” behels taal. Kan ʼn vasgestelde taal beskrywings van alle wenslike prosesse toelaat? Is dit moontlik dat daar prosesse bestaan wat goed gedefinieerd is maar hoegenaamd nie beskryf kan word nie? Hierdie vrae word geassosieer met die idee van ʼn algoritme, ʼn effektiewe prosedure om die waarde van ʼn kwantiteit te bereken of ʼn oplossing vir ʼn wiskundige probleem te bepaal.

Indien ons die wiskundige akademiese landskap aan die begin van die 19de eeu in oënskou neem, is dit klinkklaar dat dit baie van ons huidige akademiese landskap verskil. Die meeste van die wiskundiges wat groot bydraes tot die ontwikkeling van rekenaarwetenskap gelewer het, het dikwels saam om ʼn tafel gesit en idees uitgeruil.