Lemma 3. ([1], 28) Olgu funktsioonid ja (*)-arvutatavad ning , siis on ka funktsioon (*)-arvutatav. Lemma 4. ([1], 29) Olgu funktsioon (*)-arvutatav ning , siis ka funktsioon (*)-arvutatav. Kõikide lemmade ja esitatud teoreemi tõestused on vormistatud viidatud materjalis. Nii palju võib öelda, et iga lemma tõestamiseks on vaja konstrueerida vastav Turingi masin, mis rahuldaks (*)-arvutatavuse kahte tingimust. Siinkohal esitame ainult meid huvitava tõestuse, milleks on Lemma 4 tõestus. Lemma 4 tõestus. ([1], 29-30). Kõigepealt konstrueerime masina, mis lisab lindile paremale vahetulemusi ja arvutab järjestikku kuni mingil väärtusel saadakse väärtuseks . Lindile kirjutatakse: , , kus Turingi masin, mis töötab seisust alustamise korral järgmiselt:
zzz.ee/epl Palm pilot: 1996 Google: 1997, Larry Page ja Sergei Brin Deep blue: 1997, AI, mis võitis males maailmameistrit Wikipedia: 2001, Jimmy Wales and Larry Sanger 6. Nädal Eksamiks: turingi masin, relee, mälutüübid, assembler, kompileerimine, interpreteerimine, jit. Lihtsad andmetüübid, stringid, massiivid, puud. Turingi masin; Alan Turingi 1937. aastal kirjeldatud lihtne abstraktne arvuti, mida kasutatakse arvutatavuse ja selle piiride uurimiseks Relee: mootoriga lüliti Mälutüübid: Assembler: kompilaator, mis tõlgib assemblerkeeles programmi masinkoodiks Kompileerimine: võtab sisendiks kõrgkeelse programmi ja tõlgib selle täitmisprogrammiks. Kompileeritud täitmisprogrammi saab edaspidi iseseisvalt käivitada, vajamata seal juures keelevahendeid Interpreteerimine: loeb programmi lähtekoodi rida haaval, tõlgib rea kohe masinkoodi
baasfunktsioonide (aritmeetika, loendid jms) mingeid lisavahendeid -- kõik kõrvalefektid on keelatud. Puhas funktsionaalne keel ei luba muutujatele väärtusi omistada. Ainus efekt, mis funktsiooni rakendamine argumentidele annab, on resultaadi leidmine. Kombineeritud funktsionaalsed keeled - ML, Lisp, Scheme - kombineerivad puhaste funktsionaalsete keelte mehhanisme imperatiivsete mehhanismidega. Lambda-arvutuse teooria tegeleb arvutatavuse ja arvutatavate funktsioonide uurimisega, kasutades selleks lambda-arvutuse keelt kui universaalset programmeerimiskeelt. Churchi tees väidab, et iga algoritmi saab lambda-arvutuse keeles kirja panna. On võimalik näidata, et lambda-arvutus, nagu ka Prolog, C ja Basic on üks paljudest universaalsetest programmeerimiskeeltest. Konkreetselt on lambda-arvutuse keel ja teooria funktsionaalsete programmeerimiskeelte aluseks. Loogika progra keel Prolog
Tuleb tõestada, et nimetatud aksiomaatika ei ole vastuoluline, st temast ei ole võimalik tuletada korraga mingit väidet A ja sellesama väite eitust -A KURT GÖDEL 1906-1978 1930: loogika baaskeel predikaatarvutus on täielik 1931: formaalne aritmeetika ei ole täielik, seda ei saagi lõpliku formaalse süsteemiga kirjeldada TURINGI MASIN 1935-1937: artikkel Turingi masinast: universaalsus, mittelahenduvus Lihtne abstraktne arvuti, mida kasutatakse arvutatavuse ja selle piiride uurimiseks. Kuna masina seisundite ja lindil olevate tähiste arv on lõplik, siis on ka tabel lõpliku suurusega ja seda saab hoida lindil. LAMBDA ARVUTUS 1936: Churchi tees universaalsus, mittelahenduvus Lambda-arvutus (-arvutus) on formaalne arvutuste esitusviis. Seda kasutatakse matemaatilises loogikas ja funktsionaalprogrammeerimises. CLAUDE SHANNON Oli ameerika matemaatik, elektroonik ja kodeerija, keda tuntakse kui informatsiooniteooria isa.
Iga sisuks on naturaalarv. Programm on operaatorite jada. Igal operaatoril Ni märgend. 7 liiki operaatoreid: INC DEC CLR JMP Rj = Ri JMP if NULL CONTINUE Iga Turingi masinal arvutatav f.-n on realiseeritav registermasinal. Tõestus kirjutame Turingi masina üleminekufunktsiooni registermasina mällu. Iga registermasina programm on realiseeritav Turingi masinal: Esitame registermasina kõigi nullist erinevate registrite sisu Turingi masina lindil Turingi masin ja registermasin on arvutatavuse mõttes ekvivalentsed. Church-Turingi tees: iga efektiivselt arvutatav funktsioon on realiseeritav Turingi masinal 24. Lihtrekursiivsed funktsioonid, nende arvutatavus Turingi mõttes. Arvtatavuseks piisab kolmest operaatorist: · superpositsioon (f.-nide järjest rakendamine) · rekursioon (f.-ni rakendamine iseenda sees omaenese eelmistele väärtustele) · minimeerimine arvutamine teatud tingimuse täitumiseni Superpositsioon: n-kohaline f
Ainus efekt, mis funktsiooni rakendamine argumentidele annab, on resultaadi leidmine. Kombineeritud funktsionaalsed keeled - ML, Lisp, Scheme - kombineerivad puhaste funktsionaalsete keelte mehhanisme imperatiivsete mehhanismidega. Alus: lambda-arvutus Lambda-arvutuse keel on Alonzo Churchi poolt 1930. aastatel leiutatud lihtne ja universaalne meetod funktsioonide kirjapanekuks. Lambda-arvutuse teooria tegeleb arvutatavuse ja arvutatavate funktsioonide uurimisega, kasutades selleks lambda-arvutuse keelt kui universaalset programmeerimiskeelt. Churchi tees väidab, et iga algoritmi saab lambda-arvutuse keeles kirja panna. On võimalik näidata, et lambda-arvutus, nagu ka Prolog, C ja Basic on üks paljudest universaalsetest programmeerimiskeeltest. Konkreetselt on lambda-arvutuse keel ja teooria funktsionaalsete programmeerimiskeelte aluseks.
annaabi.ee 
