тюмгу / Тишин В.В. Дискретная математика в примерах

Глава 3. Теория алгоритмов

Командой машины Тьюринга называется запись вида a^Sj ~ ^a pD s j,

где a D, s - - значения на наборе (a/;.v() функций S. а и г соответ­

ственно.

Программой машины Тьюринга называется набор всех её команд.

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

Работа машины Тьюринга над словом а, записанным на ленте, проходит

следующим образом:

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

считав символ в ячейке, обозреваемой считывающим устройством ма­ шины Тьюринга, она печатает в эту ячейку символ, найденный с помо­ щью функции выхода к двигается вдоль ленты вправо, влево или оста­ ётся на месте, в случае, если функция ц принимает значения П, JI, или Н соответственно и переходит в состояние, определяемое с помощью функции перехода S;

при переходе машины Тьюринга в состояние л0 считают, что она за­

кончила работу над словом а и говорят, что машина Тьюринга приме­ нима к слову а.

Если машина Тьюринга при работе над словом а не переходит в со­ стояние S q , то говорят, что она не применима к слову а.

Конфигурацией машины Тьюринга называется запись щ h а 2 . где b - sk

символ ячейки, обозреваемой считывающим устройством машины Тью­

ринга, находящейся в состоянии sk , а а ; и а 2 - слова, записанные на ленте соответственно левее и правее символа Ь.

Кодом машины Тьюринга называется запись набора её команд в алфа­

вите {*,1}, позволяющая однозначно восстанавливать каждую команду.

Машина Тьюринга называется самоприменимой (несамоприменимой), в

случае, ели она применима (не применима) к своему коду.

гу, если существует машина Тьюринга, применимая к любому слову

вида (*), переводящая его в слово 1 У+1, где у = / (х] ,х 2 хк ).

Задание 3.1.1

1.Построить машину Тьюринга, применимую ко всем словам х1х2...хи

валфавите {а, Ь} и переводящую их в слово а

2.Проверить работу машины Тьюринга над некоторыми словами.

Таблица 3.1.1

28хйхй_i„.Xi

29ХхХ2 ...Хп- 2 ^ п - \ Хп

30ab, если слово начинается на Ьа. х1...хи_1 в других случаях

Пример решения задания 3.1.1

Решить задание 3.1.1 для

а = {хп, если хп_х =а, Ьп~ххп, если хп_х = b, (п> 1).

1. Опишем работу алгоритма, решающего эту задачу.

Будем обозначать состояния машины Тьюринга числами 0,1,2..., при­ чём 1 - начальное, а 0 - заключительное состояния.

Вначале с помощью команд (а,1)—>аП1; (ЙД)—>ЙП1 проходим до конца слова, не изменяя его символов.

Признаком окончания слова будет считывание X в первом состоянии.

С помощью команд (X,1)—»Ш2; (а.2) —» а ЛЗ; (Ъ,2) —> b ЛЗ движемся

влево, не изменяя последнего символа слова.

Если в состоянии 3 считываем символ а, значит, хп_\ = а, нужно сти­

рать все символы слова а , кроме последнего. Эго можно сделать с по­ мощью команд (а,3)-> лЛ4: (а,4)-> /Л 4: (Ь,4)-> /Л4. Если в со­

стоянии 4 считывается X, значит, вся работа проделана, и пора останав­

ливаться с помощью команды (^,4)—»ХН0.

Если в состоянии 3 считываем символ Ь, значит, хп_\ = Ь. нужно все символы, кроме хп, заменять буквами Ь. Эго делаем с помощью ко­ манд (Z>,3) — Л5; (а,5) —>ЙЛ5; (Ь,5)—>Ы15. Если в состоянии 5 считывается X, значит, всё символы исходного слова пройдены, можно

переходить в состояние 0 с помощью команды (Л,5)—»Ш0. Запишем программу найденной машины Тьюринга в виде таблицы:

2. Проверим работу построенной машины Тьюринга над словом abba :

abba, abba, abba, abba, abbaX, abbaX, abba, abba, abba,

Xbbba, Xbbba.

5 0

Итак, в слове abba предпоследний символ - b, и все буквы исходного слова, кроме последней, заменены буквой b.

Проверим работу построенной машины Тьюринга над словом bbaaa :

bba a a , b baaa, b b aaa, bbaaa, b baaa, b baaaX, bbaaa,

1 1 1 1 1 1 2

bbaaa, bbaXa, bbXXa, bXXXa, XXXXXa, XXXXXa.

3 4 4 4 4 0

В слове bbaaa предпоследний символ - а, и все буквы исходного сло­

ва, кроме последней, заменены пустыми символами X.

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

Задание 3.1.2

1. Построить машину Тьюринга, вычисляющую числовую функцию

/ ( * ! ,*2,

2. Проверить работу построенной машины над некоторыми наборами значений переменных.

Таблица 3.1.2

1f ( x , y , z ) = x + y

2f ( x , y , z ) = y + 3

Таблица 3.1.2 (продолжение)

Пример решения задания 3.1.2

Решить задание 3.1.2 для f ( x , y ) = x + 2у.

1. Внутренние состояния машины Тьюринга, которую мы требуется построить, будем обозначать числами 0,1,2..., причём 1 - начальное, а 0 - заключительные состояния.

Набор значений аргументов (х,у) изображается словом 1Х+1 /Л' -1.

Аргумент х должен остаться без изменения, этого можно добиться с помощью команды (1,1)—»1П1. Когда в первом состоянии встретится символ X, значит, мы попали на символ, разделяющий изображения ар­ гументов, переходим в состояние 2, а сам символ X пока оставляем без изменений с помощью команды (?ц1)—>1X12.

Далее, набор единиц, изображающий аргумент у , проходим до конца.

Для этого добавим команды (1,2)—>1П2; (/^.2)—»/Л.З.

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

Расширим алфавит, введя метку #. Считая, что к единиц блока продуб­

жающего вторую переменную, меткой # и будем двигаться вправо ((1,3)—>#П4; (1,4)—»1П4 ) пока не встретим пустую ячейку, заполним её единицей, и пойдём влево ( (?ц4)—>1J15; (1,5)—»1Л5 ), пока не встре­ тим метку, заменим её единицей, перейдём к следующему символу сле­ ва, вернувшись в состояние 3 ((#,5)—>1ЛЗ).

Когда в третьем состоянии считается X, значит, блок, изображающий

вторую переменную, продублирован. Заменим разделяющий символ

единицей ( (Х,3)—»1J15 ) и пойдём на начало полученного блока из х +1 +14- 2(у +1) = х + 2у + 4 единиц. Когда в состоянии 5 встретится

X, значит, пора идти вправо, стирать три лишние единицы, ведь для изо­

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

В клетках таблицы, помеченных неопределённым символом - можно вписать любые команды, т.к. до их исполнения дело всё равно не дой­ дёт.

2. Проверим работу алгоритма над изображением набора переменных

(0,1), т.е. над словом 1Л.11:

Итак, в результате осталось три единицы, которые являются изображе­ нием числа 2.

Заметим, что УХОД) = 0 + 2 • 1 = 2, так что на ленте получено то, что и нужно было получить.