Turingův stroj: Porovnání verzí
Smazaný obsah Přidaný obsah
→Definice: oprava formální definice Turingova stroje + seřazení prvků sedmice dle en wiki |
m →Konfigurace: překlep |
||
Řádek 22:
'''Konfigurace''' Turingova stroje je prvek <math>\left \langle q, s, n \right \rangle</math> množiny <math>Q\times\{yb^\omega \mid y \in \Gamma^*\}\times \mathbb{N}_0</math>, kde ''q'' je aktuální stav, ''s'' je nejmenší souvislá část pásky obsahující všechny neprázdné symboly a ''n'' je pozice čtecí hlavy (číslo buňky).
Vzhledem k tomu, že množiny <math>Q</math> a <math>\Gamma</math> jsou obvykle disjunktní (resp. lze vhodnou volbou prvků množiny <math>Q</math> dosáhnout toho, aby byly), používá se též kompaktní tvar, ve kterém se konfigurace Turingova stroje zapisuje jako řetězec symbolů odpovídající stavu pásky a aktuální stav se do něj vloží před symbol, na kterém se nachází čtecí hlavy. Pokud například páska obsahuje 1234, stroj je ve stavu <math>q</math> a čtecí hlava stojí na symbolu 2, zapíše se tato konfigurace
'''Počáteční konfigurace''' Turingova stroje pro vstup <math>w\in\Gamma^*</math> je konfigurace <math>(s,wb^\omega,0)</math>, resp. v kompaktním zápisu <math>sw</math>.
| |||