1. Создать устройство Тьюринга, которое умеет увеличивать число n (восьмеричное) на 1. Рассмотреть действия машины

  • 24
1. Создать устройство Тьюринга, которое умеет увеличивать число n (восьмеричное) на 1. Рассмотреть действия машины в каждом из состояний, начиная с q1, где анализируется одна цифра входного числа. Помимо программы-таблицы, описать шаги, выполняемые машиной в каждом состоянии словесно.
Морозный_Воин
22
Задача:

Устройство Тьюринга для увеличения восьмеричного числа на 1:

Для решения данной задачи мы создадим устройство Тьюринга, которое будет увеличивать восьмеричное число на 1.

Исходные данные:
- n - восьмеричное число, которое необходимо увеличить на 1.

Программа-таблица:

\[сюда вставить таблицу программы-таблицы\]

Описание действий машины в каждом из состояний:

1. Состояние \(q1\):
- Машина начинает свою работу, анализируя крайнюю правую цифру входного числа.
- Если цифра равна 0, машина заменяет её на 1 и завершает работу.
- Если цифра равна 1, машина заменяет её на 2 и завершает работу.
- Если цифра равна 2, машина заменяет её на 3 и завершает работу.
- Если цифра равна 3, машина заменяет её на 4 и завершает работу.
- Если цифра равна 4, машина заменяет её на 5 и завершает работу.
- Если цифра равна 5, машина заменяет её на 6 и завершает работу.
- Если цифра равна 6, машина заменяет её на 7 и завершает работу.
- Если цифра равна 7, машина заменяет её на 0 и переходит в следующее состояние \(q2\).

2. Состояние \(q2\):
- Машина переходит на следующую цифру входного числа.
- Если цифра равна 7, машина заменяет её на 0 и продолжает работу, оставаясь в этом же состоянии.
- Если цифра не равна 7, машина останавливается.

Таким образом, устройство Тьюринга увеличит данное восьмеричное число \(n\) на 1, выполняя указанные действия в соответствии с программой-таблицей.