Postov korespondenčni problem

Postov korespondenčni problem je primer neodljočljivega problema.

Opis PKP

Imamo dva seznama:

X = <x₁, x₂, ... x_n>

Y = <y₁, y₂, ... y_n>

Zanima nas, ali obstaja algoritem, ki bi ugotovil: ali obstaja nek k in zanj zaporedje indeksov i₁, i₂, ... i_k, da velja:

x_i1 x_i2 ... x_ik = y_i1 y_i2 ... y_ik

Algoritem lahko predstavimo tudi kot Turingov stroj in Turingov generator, zato lahko pri dokazovanju neodljočljivosti postopamo na enak način.

Omejeni Postov korespondenčni problem (OPKP)

OPKP je definiran kot PKP z omejitvijo: velja i₁ = 1. To pomeni, da morata biti na prvem mestu v primerjavi na obeh straneh prva elementa seznamov X in Y. Pogoj je pri OPKP torej definiran tako:

x₁ x_i2 ... x_ik = y₁ y_i2 ... y_ik

OPKP = PKP

Velja: OPKP lahko prevedemo na PKP (Če obstaja algoritem za OPKP, obstaja tudi za PKP).

Dokaz:

Poiskati moramo totalno rekurzivno funkcijo f, ki preslika opis konkretnega OPKP (recimo konkretnemu problemu w) v opis konkretnega PKP (f(w)), da velja:

w ima rešitev ⇔ f(w) ima rešitev

OPKP ⇒ PKP: ta smer ni problematična, saj je rešitev OPKP obenem že rešitev PKP

OPKP ⇐ PKP:

Neodločljivost PKP