1
Tvrzení i. Jazyk A není rekurzivní.
{(•A4) | výpočet TS Ai nad slovem e je konečný}
Myšlenka důkazu. Budeme chtít ukázat, že nějaký jazyk, o kterém víme, že není rekurzivní, se redukuje na jazyk A. Pak jazyk A jistě nemůže být rekurzivní.
Přirozenou volbou takového známého nerekurzivního jazyka je HALT, protože stejně jako v jazyce A rozhoduje o příslušnosti slova do jazyka HALT konečnost nějakého výpočtu Turingova stroje. Chceme tedy najít redukci HALT <m A.
Chceme tedy vymyslet, jak z kódu dvojice (Ai, w), kde Ai je Turin-gův stroj a w je slovo nad jeho abecedou, algoritmicky zkonstruovat kód takového TM Ai', že výpočet TM Ai nad slovem w je konečný právě tehdy, když výpočet TM Ai' nad slovem £ je konečný.
Chtěli bychom tedy zkonstruovat takový Turingův stroj, který se nad vstupem £ chová stejně jako TM Ai nad vstupem w. Můžeme si konstrukci trochu ulehčit a zkonstruovat TM, který se dokonce nad každým vstupem chová jako TM Ai nad vstupem w. Takový stroj získáme ze stroje Ai tak, že do stroje Ai natvrdo zakódujeme vstupní slovo w. Tedy stroj Ai' pro libovolný vstup smaže vstupní pásku, zapíše na ni slovo w a dál se bude chovat úplně stejně jako stroj Ai. Tím docílíme toho, že se stroj Ai' chová na každém vstupu stejně, jako TM Ai na vstupu w.
Důkaz. Ukážeme, že platí vztah HALT <m A, pak jazyk A nemůže být rekurzivní. Označme Z abecedu jazyka HALT a <E> abecedu jazyka A.
Pro libovolný Turingův stroj Ai a slovo w označme jako T~m,w Turingův stroj, který se pro libovolný vstup chová následujícím způsobem:
1. Smaž vstupní pásku.
2. Zapiš na vstupní pásku slovo w a posuň hlavu zpět na začátek pásky.
3. Spusť výpočet stroje Ai (tedy přepni se do počátečního stavu stroje Ai).
Dále označme jako %o stroj, který pro libovolný vstup cyklí. Definujeme funkci /: Z* —> <E>* pro každé slovo x G Z* následujícím předpisem:
I (Tm w)>  jestliže x = (Ai, w) pro nějaký TM Ai a slovo w, j\x) = \
I (7^o), jinak.
Ukážeme, že funkce / je redukce HALT na A.
Protože víme, že pokud L <m R a L není rekurzivní, pak ani R není rekurzivní.
Pro připomenutí: HALT = {(M,w) výpočet TM M nad slovem w je konečný}
Jinými slovy (M, w) G HALT právě tehdy, když (M') G A.
Když se TM M' bude nad každým vstupem chovat jako stroj M nad vstupem w, bude se tak jistě chovat i nad vstupem e.
O jaké abecedy se konkrétně jedná, pro nás není podstatné. Ale ve skutečnosti Z = {0,1,#} a <J> = {0,1}.
Stroj Tm,w je přesně stroj M' z myšlenky důkazu, jen je parametrizovaný libovolným strojem M a slovem w.
Druhý případ v definici je nutný, aby funkce / byla totální. Ne každé slovo nad abecedou Z je totiž kódem dvojice TM a slova.
Tedy, že / je totální, vyčíslitelná a pro každé x G Z* platí x G HALT
/(x) G A.
2
Funkce / je jistě totální. Také je vyčíslitelná, protože pomocí TM je možné zkontrolovat, jestli je slovo x kódem dvojice TM a slova, a také je možné zkonstruovat kód příslušného Turingova stroje T~m,w nebo Tco ■ Obě tyto úlohy je totiž možné vyřešit algoritmicky.
Zbývá dokázat, že pro každé slovo x G Z* platí x E HALT právě tehdy, když f(x) E A. Dokážeme obě tyto implikace:
• „=>": Předpokládejme, že x G HALT. Tedy z definice jazyka HALT platí x = (Ai,w), kde Ai je Turingův stroj, jehož výpočet nad slovem w je konečný. Z definice funkce / dostáváme, že f(x) = f((M,w)) = (TM,w)-
Výpočet TM Tm,w na<A každým vstupním slovem je také konečný, protože tento TM v prvním kroku smaže vstupní pásku, ve druhém na ni zapíše slovo w a pak spustí výpočet stroje Ai, a ten je z předpokladu na slově w konečný. Tím spíše je tedy konečný výpočet TM Tm,w na<A slovem e, a tedy f(x) = (Tm,w) £ A, což jsme chtěli dokázat.
• „<=": Tento směr implikace ukážeme obměnou. Předpokládejme tedy, že x £ HALT. Rozlišíme dva případy, proč slovo x může nebýt v jazyce HALT:
- Slovo x není kódem dvojce TM a slova: Pak z definice funkce / dostáváme f(x) = (Tco)- Turingův stroj To cyklí nad každým vstupem, tím spíše tedy cyklí nad vstupem e, a tedy f(x) = (To)    A, což jsme chtěli dokázat.
- Platí x = (Ai, iv), kde Ai je Turingův stroj, jehož výpočet nad slovem w je nekonečný: Z definice funkce / dostáváme, že f(x) = f((Ai,w)) = (TM,w)-
Výpočet TM Tm,w nad každým vstupním slovem je také nekonečný, protože tento TM v prvním kroku smaže vstupní pásku, ve druhém na ni zapíše slovo w a pak spustí výpočet stroje Ai, a ten je z předpokladu na slově w nekonečný. Tím spíše je tedy nekonečný výpočet TM Tm,w nad slovem e, a tedy f(x) = (Tm,w) č A, což jsme chtěli dokázat.
Ukázali jsme tedy, že platí HALT <m A, a protože jazyk HALT není rekurzivní, nemůže být rekurzivní ani jazyk A. □
Vzpomeňte si, že obměna tvrzení
x e HALT <= f(x) e A je x £ HALT =>•
/(x) 0 A