Turing-teljesség

Egy eszköz Turing-teljes, ha elméletben ekvivalens az univerzális Turing-géppel.

---

In Lectures:

---

Turing-gép formálisan

$ 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\]$

---

In Lectures:

---

Turing-gép informálisan

 - **szalag**: tetszőleges hosszúságú, cellákra osztott, rajta jelekkel (cellánként egy jel)

---

In Lectures:

---

Turing-gép állás (kártya)

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)

---

In Lectures:

---

Busy beaver automata

<a href="https://turingmachine.io/" target="_blank">link</a>

---

In Lectures:

---

Két állású busy beaver

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

---

In Lectures:

---

Busy Beaver

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.

---

In Lectures:

---

Mi kell Turing teljességhez?

A mi paradigmánkban, egy programnyelv akkor Turing-teljes, ha van benne: - **értékadás** - **iteráció**

---

In Lectures:

---

Turing kihívások

- Ember létre tudjon hozni ilyet - Készíteni olyan univerzális gépet, ami megért egy ilyen leírást, és onnantól így működik (UTM) - Egyre komplexebb, érdekesebb dolgokat, egyre érthetőbben leírni - Megtalálni a korlátokat

---

In Lectures:

---