Последовательность неотрицательных целых чисел задается на ленте машины Тьюринга как слово , где обозначает слово 11…1, состоящее из x единиц (остальные клетки ленты заполнены «мусором»

25 июля 2024
Высшая математика

Условие:

Последовательность неотрицательных целых чисел задается на ленте машины Тьюринга как слово , где обозначает слово 11…1, состоящее из x единиц (остальные клетки ленты заполнены «мусором», то есть заранее неизвестными символами алфавита).

Требуется построить машину Тьюринга, осуществляющую заданные ниже преобразования.

Предполагается, что в начале работы машина, находится в стандартном состоянии, то есть, головка показывает на 0 перед крайней левой единицей исходных данных и машина находится в состоянии q₁.

По окончании работы алгоритма также предусмотреть стандартное состояние машины, то есть, головка показывает на 0 перед крайней левой единицей результата и машина находится в состоянии q₀

Решение:

а)

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

Опишем кратко алгоритм: ставим перед начальным положением головки 0, тем самым обозначая начало массивов двумя 0, затем находим окончание второго массива 0, заменяем 0 на 1, следующий символ приравниваем 0, и начинаем переносить последовательно символы ...