*Találjunk olyan általános eljárást, amivel véges lépésben eldönthető, hogy egy tetszőleges diofantoszi egyenletnek van-e megoldása.* (Az 1900-ban David Hilbert által meghirdetett 23 legnagyobb megoldatlan matematikai probléma egyike.)
Átfogalmazás: ***Találjunk olyan általános eljárást, amivel véges lépésben eldönthető egy tetszőleges, tisztán logikai állítás igazságértéke.*** $\rightarrow$ ez a matematikai nyelven definiálható problémák általánosított megoldása lenne Mit jelent itt az *eljárás*? - Erre a kérdésre válaszolt Alan Turing...
 - **szalag**: tetszőleges hosszúságú, cellákra osztott, rajta jelekkel (cellánként egy jel)
- **gép:** - olvassa és írja a szalagot - beépített, egyértelmű instrukciók - meghatározott helyen kezd a szalagon - elolvas egy jelet és az instrukciók függvényében: - ír a helyére valamit, majd elmozdul jobbra/balra és beolvassa, ami ott van - leáll (HALT)
$ M = \langle Q, \Gamma, \delta, q_0, q_f \rangle $ - $Q$ - állások listája - ezen belül $q_0$ a kezdőállás, $q_f$ pedig a lehetséges végső ("halting") állások - $\Gamma$ - szalagon szerepelhető jelek ábécéje - $\delta$ az utasításkészlet egy függvényben: $(Q \setminus q_f) \times \Gamma \rightarrow Q \times \Gamma \times \[L,R\]$
Olyan Turing-gép, ami egy tiszán 0-kból álló szalagra a lehető legtöbb 1-est írja úgy, hogy végül eléri a halting állapotát. Egy ***n állású busy beaver*** legyőzi az összes olyan Turing-gépet ebben a feladatban, amelynek *n* lehetséges állása van.
$ \Gamma = \langle 1, 0 \rangle , Q=\langle A, B, HALT \rangle $, $ q_0 = A, q_f = HALT $, $\delta:$ | input | A | B | |---|---|---| | 1 | 1LB | 1RH | | 0 | 1RB | 1LA |
| input | A | B | C |-------|-------|-------|------------| | 0 | 1RB | 1LA | 1LB | 1 |1LC | 1RB | 1RH
<a href="https://turingmachine.io/" target="_blank">link</a>
| állások száma | maximálisan felrajzolható 1-esek | |---|---| | 2 | 6 | | 3 | 21 <!-- .element: class="fragment" --> | | 4 | 107 <!-- .element: class="fragment" --> | | 5 | 47176870 ? <!-- .element: class="fragment" --> | | 6 | $7.4 \times 10^{36534}$ ? <!-- .element: class="fragment" --> |
Egy függvény kiszámítható, ha létezik egy véges algoritmus, ami minden input függvényében megmondja az outputot. A busy beaver esetében **nincs olyan kiszámítható függvény, ami az állapotok számának függvényében megmondja a maximum felírható egyesek számát**.
Minden, a program által adott pontban elérhető és általa tárolt információ.
Meghatározza, hogy a gép a beolvasott jel alapján mit írjon, melyik legyen a következő jel, amit beolvas és milyen következő állásba menjen. - meghatározott számú állás van (köztük HALT)
- bármely tetszőleges Turing-gépet képes szimulálni tetszőleges inputtal - ez a számítógépek által elvégezhető algoritmusok absztrakt definíciója
Egy eszköz Turing-teljes, ha elméletben ekvivalens az univerzális Turing-géppel.
A mi paradigmánkban, egy programnyelv akkor Turing-teljes, ha van benne: - **értékadás** - **iteráció**
Probléma: honnan tudjuk, hogy egy Turing-gép valaha eléri a halting state-jét?
- $Q = \langle A, HALT \rangle$ - $\Gamma = \langle 0, 1 \rangle$ - $q_0 = A, q_f = HALT$ - $\delta$: | input | állás | |---|---| | 0 | 1RA | | 1 | 1RH |
Az, hogy adott program, adott inputtal eléri-e valaha a halting state-jét, **általánosan nem bizonyítható**. 
Videók: - [Halting problem - Computerphile](https://www.youtube.com/watch?v=macM_MtS_w4) - [Halting problem in Python](https://www.youtube.com/watch?v=r__GZ7ubU0M)
- ***imperatív***: utasításonként változtatom a program állapotát, amíg el nem érek a kívánt állapotba - ***procedurális***: meghívható utasítássorozatok, procedúrák (függvények) - ***struktúrált***: blokkok, elágazások, for/while struktúrák (iterációk) - ***objektumorientált***: függvényeket, adatot, speciális típusokat egységesen objektumként tároljuk az állapotban - ***generikus***: típusok tekintetében általánosítható függvények
- elágazás - if - else-if - switch/case - iteráció - while - for - do-while/until - blokk - függvény - procedúra
- elágazás - feltétel - ág - iteráció - feltétel - ciklusmag - blokk - utasítássorozat