# 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$