Järelikult masina ka korral on tingimus 1) täidetud. Tingimuse 2*) kontrolliks vaatleme kahte võimalikku olukorda, kus pole määratud. Need olukorrad on järgmised: 1) on iga arvu korral määratud, kuid erineb nullist, 2) arvutusel jõutakse arvu sellise väärtuseni, kus pole määratud. Olukord 1 on see, mille tõttu mitte kõikjal defineeritud funktsioonid arvutustes tekivad: hakatakse otsima seda, mida tegelikult ei leidu. Olukord 2 on aga see, mille tõttu me ei saa algoritmiliselt leida seda, mida tegelikult tahaksime s.o. tingimust rahuldavat vähimat arvu. Tulla tagasi lemma juurde, kui erineb nullist iga arvu korral, siis jätkab masin lõpmatult lindile uute arvude kirjutamist ja arvutus ei lõpe. Kui aga masin jõuab sellise arvu väärtuseni, et pole määratud, siis ei lõpeta masin nendel argumentidel tööd, sest lemma eelduse põhjal rahuldab masin tingimust 2*). Näeme, et mõlemas olukorras töötab masin
järgi saame hiljem aru, kas on olek v täht). t+1 on L ja t+2 on R. Kirjutame TM üleminekufunktsioonid koodina tabelisse. Nüüd kirjutame tabeli registermällu (igale lahtrile 1 register) ja lisame 7 abiregistrit: hetkeolek, lugemispea asukoht, loetud täht, kirjutatud täht/L/R, vahetulemused, tähtede arv t. Registermasin lõpetab töö, kui TM jõuab lõppolekusse. Registrites Rx… on y=TM(x) kood. 17 Turingi masina kodeerimine. Algoritmiliselt mittelahenduvad ülesanded. Church-Turingi tees. Turingi masinat saab esitada ka programmina: kirjutada järjest hetkeolek, sisend ja jrg olek: q0aq1aR Olgu Turingi masina programm P = x1…xn ning Turingi masina lindi tähestik Σ={ a0,..,at }. Turingi masina kood tähestikus Σ={ 0,| } on sõne K = K(x1)K(x2)...K(xn), kus • K (ai)=0||···|0=i, kui ai∈Σ; (i = 0…t) • K (;) = 0||…|0 = t + 1; (tähestiku viimane on t) • K (L) = 0||…|0 = t + 2; • K (S) = 0||…|0 = t + 3;
Ometigi loetakse matemaatilise ja sümbolloogika rajajaks just Boole'i, mitte Leibnizit. Üksikud erandid välja arvatud, polnud Leibnizi loogikaalastel ideedel ning avastustel järgneva kahe sajandi jooksul praktiliselt mõju. Mõjutatuna nii Ramon Lulli ideedest kui matemaatika arengust püstitas Leibniz ülesande luua universaalne sümbolkeel (lingua characteristica universalis) ja seda keelt kasutav nn ``arutlemise aritmeetika'' (calculus rationator), mille abil saaks algoritmiliselt või mehaaniliselt tuletada uusi t~eseid väiteid ja kontrollida arutluste korrektsust. Leibniz oletas, et niisuguseid tuletusi ja kontrolle saaks teha spetsiaalse masina abil. 2.3.3 18. sajand ning 19. sajandi algus Leibniz ei olnud ainus, kes taolisi eesmärke püstitas. Jakob Bernoulli, hiljem ka Gottfried Ploucquet (1716-1790) ning matemaatikud Johann Heinrich Lambert (1728-1777) ja Leonhard Euler (1707-1783) pakkusid välja sama laadi ideid.
qf-s. Lahenduv hulk millele saab leida Turingi masina. Turingi masina määramispiirkond M(A = {x | A(x) < lõpmatusest}) Hulk, mis on Turingi masina määramispiirkonnaks, nimetatakse genereeritavaks hulgaks. Iga lahenduv hulk on genereeritav: Teeme sellise masina, milles qf ei ole lõppolek seega läheb ta lõpmatusse tsüklisse iga mitte hulka kuuluva elemendi korral. 23. Turingi masina kodeerimine. Algoritmiliselt mittelahenduvad ülesanded. Church-Turingi tees. Turingi masina käsk: qiajqkX jooksev olek, järgmine sümbol, uus olek, tegevus (süboli kirjutamine + nihe L/R). Üleminekufunktsioon on esitatav käskude jadana. Käsud on eraldatud mingi separatoriga (nt ";"). Programm on siis sümbolite jada P = x1x2...xn. Turingi masina kood on sõna K(P) tähestikus A = {_,|,0}, kus K(P) = K(x1)K(x2)..K(xn). K(ai) = 0|| ..i tk.. ||0 i kuulub At K(;) = 0|| .. t+1 tk.. ||0
Vahepealne 2 70 Valemina Teine levinud viis on funktsiooni esitamine valemina. Näiteks on seeläbi defineeri- tud enamik reaalarvulisi funktsioone. Lihtne näide on ruutfunktsioon: . Algoritmina funktsioon Funktsioone võib esitada ka algoritmiliselt ning eriti osutub see oluliseks just asja-ajamisel arvutitega. Järgmisel lehel näitame, kuidas algoritmina kirja panna faktoriaal ehk esimese arvu korrutis [lk 382]. Sõnaliselt Vahel on kõige lihtsam funktsioone esitada hoopis verbaalselt. Näiteks võiksime võtta funktsiooni, mis seab iga kolmnurgaga vastavusse tema pindala, või funkt- siooni, mis seab iga inimesega vastavusse tema pikkuse. Graafiliselt Tihti on kasulik funktsioone esitada graafiliselt
annaabi.ee 
