Zacznij terazZacznij za darmo

Brakujący krok w maszynie Turinga

Chcemy zaprojektować maszynę Turinga, która dodaje 1 do liczby binarnej. Maszyna przetwarza liczbę od prawej do lewej strony, zgodnie z następującymi regułami:

  • Zacznij od skrajnego prawego bitu.
  • Jeśli bieżący bit to 0: zmień go na 1 i zatrzymaj maszynę.
  • Jeśli bieżący bit to 1: zmień go na 0 (ponieważ 1 + 1 generuje przeniesienie) i przesuń się w lewo, aby przetworzyć następny bit.
  • Jeśli maszyna przesunie się w lewo poza najbardziej lewy bit (czyli trafi na puste pole): wpisz 1, aby zapisać przeniesienie, i zatrzymaj maszynę.

Poniższy diagram stanów próbuje odwzorować te kroki, ale brakuje w nim jednego kluczowego przejścia. Wskaż brakujący krok.

Turing diagram with missing step

To ćwiczenie jest częścią kursu

Pojęcia informatyki

Zobacz kurs

Interaktywne ćwiczenie praktyczne

Przekształć teorię w praktykę dzięki jednemu z naszych interaktywnych ćwiczeń

Rozpocznij ćwiczenie