Začněte nyníZačněte zdarma

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í.

Turing diagram with missing step

Toto cvičení je součástí kurzu

Koncepty v informatice

Zobrazit kurz

Interaktivní praktické cvičení

Proměňte teorii v praxi s jedním z našich interaktivních cvičení

Začít cvičení