Přednáška

• kontrola programů je těžká
  • pojďme napsat program, který to udělá za nás
  • nerozhodnutelnost problému Helloworld (důkaz sporem)
  • převod problému Volání funkce na Helloworld
• Churchova-Turingova teze: lambda-kalkulus, částečně rekurzivní funkce a Turingovy stroje jsou navzájem ekvivalentní co do výpočetní síly
• jednopáskový deterministický Turingův stroj
  • $M=(Q,\Sigma,\delta,q_0,F)$
  • $Q$ … stavy
  • $\Sigma$ … abeceda (písmena na pásce), včetně prázdného znaku $\lambda$
    • budeme uvažovat situaci, kdy součástí uživatelského vstupu nejsou prázdné znaky
  • $\delta$ … přechodová funkce
    • může mít nějaké nedefinované přechody – pak výpočet končí
  • $q_0$ … výchozí stav
  • $F$ … přijímající stavy
• jazyk palindromů
  • načtu první znak, uložím do stavu, dojdu na konec vstupu, smažu znak shodný se stavem, vrátím se, smažu první znak
  • pokud narazím na různý koncový znak, tak to není palindrom
  • jinak skončím s prázdnou páskou → je to palindrom
  • poznámka k implementaci: pro každý znak $x$ se nám hodí mít stavy MEM_$x$ a CHECK_$x$, přičemž při prvním se posouváme po pásce doprava (hledáme konec vstupu) a druhý použijeme k jednomu kroku doleva (z prázdné buňky k poslednímu znaku vstupu, který pak porovnáme s $x$)
• částečně rozhodnutelné (rekurzivně spočetné) jazyky
  • přijímané nějakým TS
• rozhodnutelné (rekurzivní) jazyky
  • TS se s každým vstupem zastaví
• turingovsky vyčíslitelné funkce
• $k$-páskový TS
• Random Access Machine
  • program je uložen odděleně od registrů (paměti)
  • umí opravdu náhodný přístup do paměti
  • instrukce jsou vykonávány jedna po druhé – je to imperativní program
  • instrukce: load, add, sub, copy (dvě verze), jnz, read, print
  • příkaz copy umožňuje použití nepřímé adresace – bez toho bychom nemohli využít neomezenou paměť (nebylo by to ekvivalentní TS)
  • program pro součin čísel
  • můžeme mít neomezeně dlouhá pole
  • RASP
    • random access stored program
    • odpovídá von Neumannově architektuře (program je také uložen v registrech)
    • není potřeba nepřímá adresace
  • PRAM = paralelní RAM
  • ke každému TS $M$ existuje ekvivalentní RAM $R$
    • BÚNO uvažujeme pásku $M$ omezenou zleva
    • $R$ musí ve své paměti reprezentovat konfiguraci $M$, tj. stav řídicí jednotky, slovo na pásce, polohu hlavy
  • ke každému RAMu existuje ekvivalentní TS
• číslování Turingových strojů
  • shortlex uspořádání – řetězce primárně řazeny podle léky, pak lexikograficky
  • jazyk $L\subseteq\Sigma^*$ odpovídá množině přirozených čísel (každé slovo můžeme očíslovat pomocí shortlex uspořádání)
  • jazyků nad konečnou abecedou $\Sigma$ není spočetně mnoho
    • množina jazyků odpovídá potenční množině přirozených čísel
    • podle Cantorovy věty platí, že kardinalita $\mathcal P(A)$ je ostře větší než kardinalita $A$
  • každému Turingovu stroji přiřadíme přirozené číslo (tzv. Gödelovo číslo)
    • pomocí binárního kódování a shortlex uspořádání
  • pokud číslo neodpovídá syntakticky správnému zápisu TS, budeme uvažovat TS, který nic nepřjímá
  • jednomu TS odpovídá nekonečně mnoho Gödelových čísel, protože ho lze zakódovat nekonečně mnoho různými binárními kódy
  • ale jazyků je nespočetně mnoho, takže je jich víc, než kolik je TS – ne každý jazyk je částečně rozhodnutelný
• univerzální Turingův stroj
  • na vstupu bere $\braket{M,x}$ (tzn. binární kód kódující TS $M$ a vstup $x$)
  • univerzální Turingův stroj simuluje práci stroje $M$ nad vstupem $x$