ТЕМА 2. МАШИНА ТЬЮРИНГА I. Краткие теоретические сведения. Машина Тьюринга (кратко - МТ) математическое понятие, введенное англ. математиком А.Тьюрингом как формальное уточнение понятия алгоритма. В каж- дой МТ есть следующие 3 части: 1) неограниченная в обе стороны лента, разделенная на ячейки; 2) устройство управления (УУ); 3) головка (Г). С каждой МТ связан алфавит символов A и набор внутренних состояний Q (всего N cостояний, обозначаемых 1,2,...N). В каждой ячейке ленты записан один символ из A (считается, что A содержит "пустой" символ a0, т.е. отсутствие записи в ячейке интерпретируется как запись символа a0). УУ находится в од- ном из состояний 1 Ў N. Головка обозревает одну из ячеек ленты. Совокупность сведений о состоянии УУ и записи на ленте машины называ- ется конфигурацией МТ. УУ содержит команды, совокупность которых называет- ся программой МТ. Для каждого символа aлфавита А и каждого состояния 1 Ў N программа содержит в точности одну команду.Выполнение любой команды заклю- чается в следующем: а) заменяется записанный в обозреваемой ячейке символ на новый символ; б) Г сдвигается на 1 ячейку вправо или влево (может и не сдвигаться); в) происходит переход в новое состояние. Команда может быть 1)обычной; 2)заключительной. Каждую команду можно записать в виде триады , где a - записываемый на ленту символ, m - одна из букв L(вле- во),R (вправо) или S (не сдвигаться), i - состояние, в которое переходит МТ (отсутствует для заключительной команды). Работа МТ состоит из однотипных тактов. Каждый такт состоит в выпол- нении одной команды. Предполагается, что первоначально МТ находится в сос- тоянии 1. Таким образом, если задать информацию на ленте и положение голо- вки,работа МТ определяется однозначно. Работа МТ считается завершенной, если выполнилась заключительная команда. Полученное последнее cодержимое ленты является результатом работы МТ. II. Примеры на составление программ машины Тьюринга. Пример 1. К подряд записанным символам "X" на ленте добавить еще один символ "X". Алфавит символов для МТ, решающей эту задачу, состоит из одного симво- ла "X"; в качестве "пустого" символа можно использовать символ "пробел". Программа МТ содержит 2 состояния и может быть представлена в виде таб- лицы: j=1 j=2 ????????????????????????????? ? i ? ? X ? ????????????????????????????? ? 1 ? ? R ? 1 ? X ? R ? 2 ? ????????????????????????????? ? 2 ? X ? S ? ? X ? R ? 2 ? ????????????????????????????? В верхней строке этой таблицы перечислены символы алфавита, в левом столбце - номера состояний. На пересечении i-й строки и j-го столбца запи- сана команда, выполняемая, если МТ находится в состоянии i и головка обоз- ревает j-й символ алфавита. Например, если МТ находится в состоянии 1 и головка обозревает символ "X", то надо: 1)оставить в ячейке символ "X"; 2)cдвинуться вправо; 3)перейти в состояние 2. Данная программа МТ решает поставленную задачу,если в начальный момент головка либо указывает на один из символов "X", либо находится левее само- го левого символа "X". Применение программы, например, к ленте с исходным кодом "XX" в случае, если головка стоит на 1 символ левее левого символа "X", последовательно даст cостояния ленты: ХХ , (1) XX , (2) XX , (2) XX (2) XXX (в скобках указан текущий номер состояния МТ). Следующая программа решает эту же задачу для случая, когда в начальный момент головка находится правее всех символов "Х". ????????????????????????????? ? ? ? X ? ????????????????????????????? ? 1 ? ? L ? 1 ? X ? R ? 2 ? ????????????????????????????? ? 2 ? X ? S ? ? ? ? ? ????????????????????????????? Заметим, что при любом исходном коде на ленте машина Тьюринга никогда не попадет в состояние 2 с обозреваемым символом "Х". В качестве самостоятельного задания можно предложить составить прог- рамму МТ, которая решает данную задачу при любом начальном положении го- ловки. Пример 2. Прибавить к числу, записанному на ленте в двоичной системе счисления, единицу. Программа МТ имеет вид: ????????????????????????????????????????? ? ? ? 0 ? 1 ? ????????????????????????????????????????? ? 1 ? ? L ? 1 ? 1 ? S ? ? 0 ? L ? 2 ? ????????????????????????????????????????? ? 2 ? 1 ? S ? ? 1 ? S ? ? 0 ? L ? 2 ? ????????????????????????????????????????? Если в начальный момент головка либо указывает на правую цифру числа либо находится правее правой цифры, то данная программа решает поставлен- ную задачу. Применение программы, например,к ленте с исходным кодом '1011' в случае, если головка стоит на 1 символ правее правой единицы, последова- тельно даст конфигурации:1011 ,(1) 1011 ,(2) 1010 ,(2) 1001 ,(2) 1100. III. Описание системы - эмулятора машин Тьюринга. Предлагаемая система (автор Новиков М.Д.) позволяет моделировать любую машину Тьюринга, т.е. с ее помощью можно вводить конфигурацию МТ и выпол- нять преобразования над cодержимым ленты. Основные команды системы: F1 - помощь (выдается список команд и даются пояснения); F2 - запись конфигурации МТ на диск; F3 - считывание конфигурации МТ с диска; F4 - редактирование ленты; F5 - установка головки; F6 - редактирование алфавита символов; F7 - стирание конфигурации; F8 - выполнение программы МТ по шагам (после каждого такта происходит прерывание до нажатия любой клавиши); F9 - выполнение программы МТ. ALT+X - окончание работы с системой. Особенности системы: 1) Максимальное количество состояний - 100. 2) Максимальное количество символов алфавита - 13. 3) В качестве "пустого" символа используется символ "пробел". Литература. 1. Успенский В.А. Машина Поста. - М., Наука, 1988 г. 2. Энциклопедия кибернетики. - Киев, Полиграфкнига, 1975 г.