Teoreetilibe informaatika kordamisküsimused
kas f.-nid a ja b ühtivad või mitte
Järeldus:
Pole olemas algoritmi, mis suvalise arvutatava f.-ni f korral teeks kindlaks, kas
võrrand f(x) = 0 on arvutatav või mitte.
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,.
annaabi.ee 
