Chybějící krok v Turingově stroji
Chceme navrhnout Turingův stroj, který přičte 1 k binárnímu číslu. Stroj zpracovává číslo zprava doleva podle těchto pravidel:
- Začni na nejpravějším bitu.
- Pokud je aktuální bit 0: změň ho na 1 a zastav.
- Pokud je aktuální bit 1: změň ho na 0 (protože 1 + 1 způsobuje přenos) a posuň se doleva ke zpracování dalšího bitu.
- Pokud se stroj posune doleva za nejlevější číslici (tj. narazí na prázdnou buňku): zapiš 1, která reprezentuje přenesený bit, a zastav.
Níže uvedený stavový diagram se snaží zachytit tyto kroky, ale chybí v něm klíčový přechod. Urči, který krok chybí.

Toto cvičení je součástí kurzu
Koncepty v informatice
Interaktivní praktické cvičení
Proměňte teorii v praxi s jedním z našich interaktivních cvičení
Začít cvičení