ПочатиПочніть безкоштовно

Відсутній крок у машині Тюрінга

Ми хочемо спроєктувати машину Тюрінга, яка додає 1 до двійкового числа. Машина обробляє число справа наліво за такими правилами:

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

Наведена нижче діаграма станів намагається відобразити ці кроки, але в ній бракує критичного переходу. Визначте відсутній крок.

Turing diagram with missing step

Ця вправа є частиною курсу

Концепції комп'ютерних наук

Переглянути курс

Практична інтерактивна вправа

Перетворіть теорію на практику за допомогою однієї з наших інтерактивних вправ

Почати вправу