1. Создать устройство Тьюринга, которое умеет увеличивать число n (восьмеричное) на 1. Рассмотреть действия машины
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, выполняя указанные действия в соответствии с программой-таблицей.