Учебно-методический комплекс дисциплины для обучающегося «Языки программирования» для специальности 5В010900 Математика

Машины, введенные Постом и Тьюрингом, отличались не очень существенно и в дальнейшем стали называться машинами Тьюринга.

В общем случае такая машина состоит из следующих частей (рис.1.4):

Рис 1.4. Состав машины Тьюринга

2) «считывающей головки» - специального чувствительного элемента, способного обозревать содержимое ячеек. Вдоль голов­ки информационная лента перемещается в обе стороны так, чтобы в каждый рассматриваемый момент времени головка находилась в одной определенной ячейке ленты;

3) управляющего устройства, которое в каждый рассматрива­емый момент находится в некотором «состоянии». Предполагается, что устройство управления машины может находиться в некото­ром конечном числе состояний. Состояние устройства управления часто называют внутренним состоянием машины. Одно из этих со­стояний называется заключительным и управляет окончанием ра­боты машины.

Рассмотрим алгоритмическую систему, предложенную Постом. В алгоритмической системе Поста информация представляется в двоичном алфавите А = {1, 0}, т. е. в каждой ячейке информационной ленты можно поместить либо 0, либо 1. Алгоритм представляется в виде конечного упорядоченного набора правил, называемых прика­зами. Работа алгоритма начинается с некоторой начальной ячейки, соответствующей первому приказу алгоритма. Составляющие алгоритм приказы могут принадлежать к одному из шести приказов, выполняемых устройством управления машины Поста.

1. 
   Записать в рассматриваемую ячейку 1 и перейти к i-му приказу.
   
2. 
   Записать в рассматриваемую ячейку 0 и перейти к i-му приказу
   
3. 
   Сдвинуть ленту вправо на одну ячейку и приступить к выполнению i-го приказа.
   
4. 
   Сдвинуть ленту влево на одну ячейку и перейти к выполнению i-го приказа.
   
5. 
   Если в рассматриваемой ячейке записана 1, то перейти к выполнению j-го приказа, а если записан 0, то перейти к выполнению i-го приказа.
   
6. 
   Окончание работы алгоритма, остановка.
   

Алгоритмы Поста сводятся к алгоритмам, реализуемым с помощью частично рекурсивных функций, и наоборот — любая частично рекурсивная функция может быть представлена алгоритмом си­стемы Поста.

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

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

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

Конечную совокупность символов алфавита, с которой работает машина, называют внешним алфавитом, конечную совокупность состояний устройства управления — внутренним алфавитом.

Совокупность, образованную последовательностью состояний всех ячеек ленты и состоянием устройства управления, называют конфигурацией машины. Конфигурация задается в виде слова, описывающего конкретное состояние машины.

Пусть в некоторый момент времени машина Тьюринга находит­ся в состоянии, представленном на рис.1.5.

Рис 1.5. Состояние машины Тьюринга

где  - символ, обозначающий пустую ячейку;

 - состояние ячейки, просматриваемой в данный момент времени;

Каждая конфигурация содержит лишь одно вхождение символа  из внутреннего алфавита. Этот символ может быть в слове са­мым левым, но не может быть самым правым, так как справа от него должен помещаться символ состояния обозреваемой ячейки.

Если стандартная машина Тьюринга, находясь в состоянии  и воспринимая записанный на ленте символ  , переходит в новое состояние  осуществляя при этом замену символа в рассматрива­емой ячейке на символ  и сдвиг ленты влево на одну ячейку, то говорят, что машина выполняет команду  .

При манипуляциях с лентами используют следующие обозна­чения:

Л — движение ленты влево; П— движение ленты вправо; С — нет движения ленты.

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

Рассмотрим пример машины Тьюринга с алфавитами А={0, 1}, и командами. Л, С.

Пусть на ленте имеется слово 11100. Головка стоит над первой слева единицей (таблица 1.1).

В результате работы машины Тьюринга за четыре шага это слово превращается в 11110. По окончании ра­боты машины головка стоит над крайней правой единицей. Можно сказать, что данная машина выполнила сложение в двоичной сис­теме десятичных чисел 28 + 2.

Совокупность всех команд, которые может выполнять машина, называется ее программой.

Машина Тьюринга считается заданной, если заданы:

• 
  ее внешний и внутренний алфавиты;
  
• 
  программа;
  
• 
  начальная конфигурация;
  
• 
  символы, обозначающие пустую ячейку и заключительное состояние.
  

Пустую ячейку обозначает символ , а заключительное состоя­ние - .

В таблице 1.2 представлен процесс переработки машиной Тьюрин­га исходного слова bcadc в слово bcdcc. Начальная конфигурация имеет вид  bcadc.
Таблица 1.2. Алгоритм работы машины Тьюринга по переработке слова bcadc в слово bcdcc