Vyčíslitelnost

Note	Turingův stroj. Problém zastavení. Rozhodnutelnost a částečná rozhodnutelnost, nerozhodnutelnost. Metoda redukce, diagonalizace. IB102/IB005+IB107

Vyčíslitelnost se zabývá funkcemi, které je možné vyčíslit — nějakým způsobem naprogramovat.

Turingův stroj

Turingův stroj (TM) je 9-ice $M = (Q, Σ, Γ, ⊳, ⊔, δ, q_{0}, q_{accept}, q_{reject})$ , kde:

$Q$ je konečná množina stavů,
$Σ$ je konečná množina vstupních symbolů,
$Γ$ je konečná množina páskových symbolů taková, že $Σ \subseteq Γ$ ,
$⊳ \in Γ ∖ Σ$ je levá konzová značka,
$⊔ \in Γ ∖ Σ$ je symbol označující prázdné políčko,
$δ : (Q ∖ {q_{accept, q_{reject}}}) \times Γ \to Q \times Γ \times {L, R}$ je totální přechodová funkce,
$q_{0}$ je počáteční stav,
$q_{accept}$ je akceptující stav,
$q_{reject}$ je zamítající stav.

Navíc platí $(\forall q \in Q) (\exists p \in Q) (δ (q, ⊳) = (p, ⊳, R))$ . Jinými slovy, TM nesmí přepsat $⊳$ .

Konfigurace

Konfigurace $(q, z, n)$ obsahuje stav, obsah pásky a index políčka, nad kterým je hlava:

(q, z, n) \in Q \times {y ⊔^{ω} ∣ y \in Γ^{*}} \times N_{0}

Počáteční konfigurace je $(q_{0}, ⊳ w ⊔^{ω}, 0)$ .

Akceptující konfigurace má tvar $(q_{accept}, z, n)$ , kde $z \in Γ^{*}, n \in N_{0}$ . Podobně, zamítající konfigurace má tvar $(q_{reject}, z, n)$ .

Krok výpočtu

Krok výpočtu je relace $M ⊢$ na konfiguracích TM $M$ :

Note	$s_{b}^{n} (z)$ značí upravený $z$ , kde n-tý symbol je $b$ .

(p, z, n) M ⊢ {(q, s_{b}^{n} (z), n + 1) (q, s_{b}^{n} (z), n - 1) pro δ (p, z_{n}) = (q, b, R) pro δ (p, z_{n}) = (q, b, L) .

Výpočet TM $M$ na vstupu $w$ je posloupnost konfigurací $K_{0}, K_{1}, K_{2}, ...$ taková, že $K_{0}$ je počáteční konfigurace pro $w$ a pro všechna $i \geq 0$ platí $K_{i} M ⊢ K_{i + 1}$ .

Stroj $M$ akceptuje slovo $w$ , právě když výpočet $M$ na $w$ je konečný a poslední konfigurace je akceptující.

Stroj $M$ zamítá slovo $w$ , právě když výpočet $M$ na $w$ je konečný a poslední konfigurace je zamítající.

Stroj $M$ cyklí slovo $w$ , právě když výpočet $M$ na $w$ je nekonečný.

Jazyk akceptovaný $M$ je $L (M) = {w \in Σ^{*} ∣ M akceptuje w}$ .

Rozhodnutelnost

Jazyk $L \subseteq Σ^{*}$ je:

rekurzivně spočetný: právě když $L \in L (M)$ pro nějaký $M$ . Tedy pokud $w \in L$ , pak ho $M$ akceptuje, jinak zastaví nebo cyklí.
rekurzivní: právě když $L \in L (M)$ pro nějaký úplný $M$ . Tedy pokud $w \in L$ , pak ho $M$ , jinak zamítá. Nikdy necyklí.

Problém určit, zda řetěz $w$ má vlastnost $P$ , je

rozhodnutelný: právě když jazyk všech řetězů s vlastností $P$ je rekurzivní.
nerozhodnutelný: právě když není rozhodnutelný. Nerozhodnutelný problém může být částečně rozhodnutelný.
částečně rozhodnutelný (semirozhodnutelný): právě když jazyk všech řetězů s vlastností $P$ je rekurzivně spočetný.

Problém zastavení

Je výpočet $M$ na $w$ konečný?

HALT = {⟨ M, w ⟩ ∣ M je TM a v \overset{y}{ˊ} po \overset{c}{ˇ} et na w je kone \overset{c}{ˇ} n \overset{y}{ˊ}}

Je částečné rozhodnutelný, neboť, pokud $M$ na $w$ zastaví, pak lze $⟨ M, w ⟩$ akceptovat.

Je však nerozhodnutelný. Důkaz se vede sporem: Kdyby HALT rozhodnutelný byl, pak existuje TM $M$ , který jej rozhoduje. Ale! Představme si TM $T$ , který interně používá $M$ a cyklí, právě když TM na vstupu zastaví, pokud dostane svůj vlastní kód jako vstup:

T (⟨ F ⟩) = {⊥ 1 pokud M (⟨ F, ⟨ F ⟩⟩) = 1 jinak

Když $M$ předhodíme vstup $⟨ T, ⟨ T ⟩⟩$ , nastane problém, protože $M$ spustí $T$ se vstupem $⟨ T ⟩$ a $T$ má proto zastavit, právě když $T$ nezastaví, takže HALT musí být nerozhodnutelný.

Metoda redukce

Nechť $A \subseteq Σ^{*}$ a $B \subseteq Φ^{*}$ jsou jazyky. Redukce jazyka $A$ na jazyk $B$ je rekurzivní (totálně vyčíslitelná) funkce $f : Σ^{*} \to Φ^{*}$ taková, že $w \in A ⟺ f (w) \in B$ .

Pokud existuje redukce z $A$ do $B$ , jazyk $A$ se redukuje na jazyk $b$ . Píšeme $A \leq_{M} B$ .

Pokud je $B$ rekurzivní (resp. rekurzivně spočetný), pak i $A$ je rekurzivní (resp. rekurzivně spočetný).

Note

Představ si, že

B

je rozhodnutelný problém toho, jestli má dané restaurační zařízení v danou hodinu otevřeno či zavřeno, a

A

je problém, zda zrovna U Valáška mají otevřeno. Jelikož

A

je jen speciální případ

B

, redukce jen dosadí konstantu "U Valáška" za parametr "restaurační zařízení" a tedy je rekurzivní. Tedy lze rozhodnout, zda U Valáška mají otevřeno.

Tuto implikaci lze obměnit: Pokud $A$ rekurzivní (resp. rekurzivně spočetný) není, pak ani $B$ rekurzivní (resp. rekurzivně spočetný) není. A tohoto se využívá k důkazu toho, že nějaký problém $P$ je nerozhodnutelný. Stačí najít redukci $HALT \leq_{M} P$ .

Note	Intuitivně se na to dá dívat i tak, že $P$ je alespoň tak "těžký" jako HALT.

Diagonalizace

Původně použita v Cantorově důkazu toho, že reálných čísel je víc než přirozených:

Note	Řádky jsou indexy reálných čísel. Sloupce jsou desetinná místa ve dvojkové soustavě.

$r_{0}$	0	0	0	0	0	…
$r_{1}$	1	1	1	1	1	…
$r_{2}$	0	1	0	1	0	…
$r_{3}$	1	1	0	0	1	…
$r_{4}$	0	0	0	1	1	…
…

Existuje však reálné číslo $z = 0.10110...$ , které se liší od každého čísla v tabulce, jelikož je to invertovaná diagonála.

V důkazu nerozhodnosti HALTu výše je taky diagonalizace. Jen tam sloupce jsou vstupy, řádky Turingovy stroje a buňky "zastaví/nezastaví".