Teoreetilibe informaatika kordamisküsimused
32. Posti vastavuse probleemi mittelahenduvus. Mittelahenduvate
ülesannete näited.
A = {x1,..,xn} f: A A on ühskohaline kõikjal määrat' naturaalarvuline f.-n.
f on Nn tükki.
Kõigi ühekohaliste naturaalarvuliste f.-nide arv aga on |N| |N| - kontiinumi võimsus.
Kõigil arvutatavatel f.-nidel on Gödeli numbrid need aga on naturaalarvud
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
annaabi.ee 
