Тема 7. Универсальная машина Тьюринга

План лекции

1. Универсальная машина Тьюринга

2. Алгоритмически неразрешимые проблемы

1. Универсальная машина Тьюринга

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

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

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

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

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

1) различные буквы должны заменяться различными кодовыми группами, но одна и та же буква должна заменяться всюду, где бы она не встречалась, одной и той же кодовой группой;

2) строки кодовых записей должны однозначным образом разбиваться на отдельные кодовые группы;

3) должна существовать возможность распознать, какие кодовые группы соответствуют различным сдвигам управляющей головки (R, L, E), и различать кодовые группы, соответствующие буквам внутреннего алфавита и буквам внешнего алфавита.

Рассмотрим пример такого кодирования для машины Тьюринга Т, имеющей внешний алфавит A = {a₁, a₂, ... , a_k} и внутренний алфавит Q = {q₁, q₂, ... , q_z}. Если внешний алфавит состоит из символов А = {0, 1}, то условия кодирования будут соблюдены при следующем способе кодирования.

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

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

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

Например, для машины Тьюринга, которая перерабатывает слово bcad в слово bccd, входное слово в универсальной машине Тьюринга с данным кодом будет представлено следующей строкой:

10000001 1000000001 100001 100000000001,

где 100001 - a, 10000001 - b, 1000000001 - c, 100000000001 - d.

Программа же будет представлена следующими строками:

1) 1000001 10000001 1000001 10000001 101

(q ₀b → q ₀ b R)

2) 1000001 1000000001 1000001 1000000001 101

(q ₀c → q ₀ c R)

3) 1000001 100001 100000001 1000000001 101

(q ₀ a → q ₁ c R)

3) 100000001 100000000001 10000000001 100000000001 10001

(q₁d→q₂dL).

Рассмотрим еще один пример. Пусть на ленту универсальной машины Тьюринга поступает слово, составленное из букв английского алфавита. Задача машины Тьюринга - переставлять местами буквы nи oтаким образом, чтобы сочетание onпреобразовывалось в no. Таким образом, после переработки входного слова в нем не должно остаться ни одного буквосочетания on.

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

Пусть внешний алфавит универсальной машины Тьюринга состоит из символов A ={0,1}, а внутренний алфавит Q = {q₀, q₁, q₂, q₃, q_z }, где q_z – заключительное состояние. Разбивка входных символов на кодовые группы и сопоставление кодовых групп исходным символам внешнего и внутреннего алфавитов осуществляется согласно приведенной выше таблице кодирования.

Тогда входное слово будет представлено следующим образом:

100001 10000001 1000000001 10000001 10000001 1000000001 100000000001,

где 100001 - m, 10000001 - n, 1000000001 - o, 100000000001 - p.

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

q ₀ m → q ₀ m R M n o n n o p

q ₀ n → q ₀ n R m N o n n o p

q ₀ o → q ₁ o R m n O n n o p

q ₁ n → q ₂ o L m n o N n o p

q ₂ o → q ₀ n R m n O o n o p

q ₀ o → q ₁ o R m n n O n o p

q ₁ n → q ₂ o L m n n o N o p

q ₂ o → q ₀ n R m n n O o o p

q ₀ o → q ₁ o R m n n n O o p

q ₁ o → q ₀ o R m n n n o O p

q ₀ p → q _z p E m n n n o o P.

Программа же будет выглядеть так:

1000001 100001 1000001 100001 101

1000001 10000001 1000001 10000001 101

1000001 1000000001 100000001 1000000001 101

100000001 10000001 10000000001 1000000001 10001

10000000001 1000000001 1000001 10000001 101

1000001 1000000001 100000001 1000000001 101

100000001 10000001 10000000001 1000000001 10001

10000000001 1000000001 1000001 10000001 101

1000001 1000000001 100000001 1000000001 101

100000001 1000000001 1000001 1000000001 101

1000001 100000000001 1000000000001 100000000001 1001.

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

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

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

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

1) для описания состояний устройства управления специальной машины Тьюринга, реализующей соответствующий алгоритм;

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

Современные ЭВМ строятся как универсальные; в запоминающее устройство наряду с исходными данными поставленной задачи вводится также и программа ее решения.

Однако в отличие от машины Тьюринга, в которой внешняя память (лента) бесконечна, в любой реальной вычислительной машине она конечна.

Дата добавления: 2015-07-26; просмотров: 311; Нарушение авторских прав

Мы поможем в написании ваших работ!