Přednáška: kartičky | zaklady-slozitosti-vycislitelnosti

kontrola programů je těžká

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í

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$ $M$ existuje ekvivalentní RAM $R$ $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