Lemma 2. ([1], 26) Olgu funktsioonid ja (*)-arvutatavad ning , siis on ka funktsioon (*)-arvutatav. 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:
moodusega lemmadeks. Lemmasid, mis põhinevad modus tollens’i tüüpi arutlusel, nimetatakse destruktiivseteks lemmadeks või eitava moodusega lemmadeks. Ülalpool fikseeritud kokkuleppe kohaselt vaatleme kõiki tingimuslikke väiteid materiaalsete implikatsioonidena. Juhul kui tegemist oli tingivate väidetega, siis seda saab arvesse võtta lausete tõlgendamise käigus. Selguse mõttes kehtestatakse käesoleva õpiku raames lemmade kohta täiendav kokkulepe. Kui järgnevalt ... … kasutatakse termineid konstruktiivne lemma ja destruktiivne lemma, siis on tegemist ainult selliste lemmadega, mille puhul esineb mittevälistav disjunktsioon, selle rõhutamiseks võib öelda mittevälistav konstruktiivne lemma ja mittevälistav destruktiivne lemma; … kasutatakse termineid välistav konstruktiivne lemma ja välistav destruktiivne lemma
moodusega lemmadeks. Lemmasid, mis põhinevad modus tollens'i tüüpi arutlusel, nimetatakse destruktiivseteks lemmadeks või eitava moodusega lemmadeks. Ülalpool fikseeritud kokkuleppe kohaselt vaatleme kõiki tingimuslikke väiteid materiaalsete implikatsioonidena. Juhul kui tegemist oli tingivate väidetega, siis seda saab arvesse võtta lausete tõlgendamise käigus. Selguse mõttes kehtestatakse käesoleva õpiku raames lemmade kohta täiendav kokkulepe. Kui järgnevalt ... ... kasutatakse termineid konstruktiivne lemma ja destruktiivne lemma, siis on tegemist ainult selliste lemmadega, mille puhul esineb mittevälistav disjunktsioon, selle rõhutamiseks võib öelda mittevälistav konstruktiivne lemma ja mittevälistav destruktiivne lemma; ... kasutatakse termineid välistav konstruktiivne lemma ja välistav destruktiivne lemma
annaabi.ee 
