"peatumisprobleemile" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

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). Taandasime Posti vastavuse probleemi Turingi masina peatumisprobleemile. Kontekstivabade keelte ühesuse mittelahenduvus: Mitmete formaalsete keelte ühesuse mittelahenduvus tugineb posti vastavuse mittelahenduvusele. KV keel L. Olgu antud sõnade paarid: C = {(x1,y1),..,(xn,yn)} (vähemalt ühetähelised keele sõnad) Ning naturaalarvud: I = {1,2,..,n} (numbrid ei kuulu keelse sõnade hulka) Defineerime hulgad: Lc = {xi1 .. xim, im .. i1 | ik kuulub I, m>=1} Mc = {ui1...yim im... i1 | ik kuulub I, m>=1}