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

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

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

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

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

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

Это достигается путем кодирования конфигурации и програм­мы любой данной машины Тьюринга в символах входного (внеш­него) алфавита универсальной машины. Само кодирование долж­но выполняться следующим образом:

1. 
   различные символы должны заменяться различными кодовыми группами, но один и тот же символ должен заменяться всю­ду, где бы он ни встречался, одной и той же кодовой группой;
   
2. 
   строки кодовых записей должны однозначным образом раз­биваться на отдельные кодовые группы;
   
3. 
   должна иметь место возможность распознать, какие кодовые группы соответствуют различным сдвигам, т. е. каждой из букв Л, П, С в отдельности, и различать кодовые группы, соответствующие сим­волам внутреннего алфавита и символам внешнего алфавита.
   

Если внешний алфавит универсальной машины Тьюринга со­стоит из символов А={0, 1}, то эти условия будут выполнены при следующем способе кодирования.

1. В качестве кодовых групп используются 3 + k + m различных слов вида 100 ... 01 (между единицами — нули), где k — число сим­волов внешнего алфавита; m — число состояний устройства управ­ления.

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

2. Сопоставление кодовых групп с исходными символами внеш­него и внутреннего алфавитов осуществляется согласно следующей таблице кодирования:


Так, для машины Тьюринга, перерабатывающей слово bcadc в сло­во bcdcc (см. табл.1.2), входное слово в универсальной машине Тью­ринга с данным кодом будет представлено следующей строкой:

1000000110000000011000011000000000011000000001, где 100001 - а, 10000001 - b, 1000000001 - с, 100000000001 - d.

Вся программа будет иметь вид:

Таблица 1.4

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

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

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

При изучении моделей вычислений обычно проводят различие между детерминированными и недетерминированными машинами Тьюринга. В детерминированной машине Тьюринга общий ход вы­числений полностью определяется машиной Тьюринга (програм­мой), начальным символом и начальными вводами с ленты. В неде­терминированной машине Тьюринга на каждой стадии вычислений существуют альтернативы, т.е. она может работать в одном из не­скольких основных режимов. При этом класс задач, решаемых на де­терминированных машинах Тьюринга за полиномиальное время, на­зывают классом Р, а класс задач, решаемых на недертеминированных машинах Тьюринга за полиномиальное время, — классом NP.

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

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