Turingův stroj: Porovnání verzí
Smazaný obsah Přidaný obsah
m Bot: Odstranění 50 odkazů interwiki, které jsou nyní dostupné na Wikidatech (d:q163310) |
→Konfigurace: doplněn kompaktní zápis značka: editace z Vizuálního editoru |
||
Řádek 21:
'''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 jeko 1<math>q</math>234.
'''Počáteční konfigurace''' Turingova stroje pro vstup <math>w\in\Gamma^*</math> je konfigurace <math>(s,wb^\omega,0)</math>.▼
▲'''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>.
== Výpočet ==
| |||