Відсутній крок у машині Тюрінга
Ми хочемо спроєктувати машину Тюрінга, яка додає 1 до двійкового числа. Машина обробляє число справа наліво за такими правилами:
- Почніть з крайнього правого біта.
- Якщо поточний біт — 0: змініть його на 1 і зупиніться.
- Якщо поточний біт — 1: змініть його на 0 (адже 1 + 1 спричиняє перенесення) і рухайтеся ліворуч, щоб обробити наступний біт.
- Якщо машина рухається ліворуч за межі крайньої лівої цифри (тобто натрапляє на порожню комірку): запишіть 1, щоб позначити перенесений біт, і зупиніться.
Наведена нижче діаграма станів намагається відобразити ці кроки, але в ній бракує критичного переходу. Визначте відсутній крок.

Ця вправа є частиною курсу
Концепції комп'ютерних наук
Практична інтерактивна вправа
Перетворіть теорію на практику за допомогою однієї з наших інтерактивних вправ
Почати вправу