Teoreetilibe informaatika kordamisküsimused
seega ei saa kõik f.-nid olla lahenduvad.
· Turingi masina peatumine (kas A(x) = lõpmatus?)
· Hiberti kümnes probleem kas täisarvuliste kordajatega polünoomi
P(x1,..,xn) korral on võrrandil P(x1,..,xn) = 0 naturaalarvulisi lahendeid?
· Posti vastavuse probleem
Posti vastavuse probleem:
korteezhid tähestikus :
= (1,..,n)
= (1,..,n)
Kas leidub indeksite jada i1,..,ik nii, et
1i1i2..ik = 1i2..in
See ei ole lahenduv.
Kui see oleks lahenduv, leiduks predikaat
1, kui leidub
P(,) =
0, kui ei leidu
Teatud juhul on lahenduv. = {a,b}
= {aa,bb,abb}
= {aab,ba,b}
Ning indeksid <2;1;3> aabbabb = aabbab
Osade korral aga eksisteerib.
Koostame karakteristliku Turingi masina.
Näeme, et kuna seda genereeriva Turingi masina määramispiirkond pole
lahenduv hulk (mõnel korral jääb masin lõpmatusse tsüklisse).
annaabi.ee 
