Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов (1082244), страница 6
Текст из файла (страница 6)
Это позволяет получить на ленте сначала результат, а затем - исходныеданные или наоборот.Рассмотрим пример построения машины Тьюринга с правой полулентой, вычисляющейфункцию f(x) = 2x. Алгоритм вычисления данной функции состоит в приписывании нуля квходной цепочке справа.Таблица соответствия данной машины Тьюринга будет иметь следующий вид:<q00q0 0R1q0 1Rq1q2>q1 0Rεq2 >Lqz < Rq2 0Lq2 1LЗдесь символ “<“ обозначает левый маркер, а символ “>“ - правый маркер. МашинаТьюринга, начав работу из стандартной начальной конфигурации, после выполнениясовокупности команд переходит в стандартную заключительную конфигурацию.Полученный результат располагается между маркерами и сдвинут вплотную к левомумаркеру.3.9.
Универсальная машина ТьюрингаДо сих пор мы имели дело со специализированными машинами Тьюринга,предназначенными для решения конкретных задач и отличающимися набором команд,внутренним и внешним алфавитами. Однако можно построить универсальную машинуТьюринга, способную выполнять любой алгоритм, а значит работу любой машиныТьюринга. В ней входное слово должно включать изображение программы и входное словоинтерпретируемой машины.Чтобы получить изображение программы интерпретируемой машины, нужнопоследовательно, строка за строкой, закодировать эту программу в алфавите универсальноймашины.
Универсальная машина Тьюринга должна иметь фиксированный внешнийалфавит, используемый при записи программы, включая и алфавит интерпретируемоймашины.Она должна быть приспособлена к приему в качестве исходной информациивсевозможных состояний устройства управления и конфигураций, в которых могутвстречаться буквы из разнообразных алфавитов со сколь угодно большим числом различныхбукв.Это достигается путем кодирования конфигурации и программы любой заданноймашины Тьюринга в символах входного алфавита универсальной машины.Самокодирование должно выполняться следующим образом:1) различные буквы должны заменяться различными кодовыми группами, но одна и таже буква должна заменяться всюду, где бы она не встречалась, одной и той же кодовойгруппой;2) строки кодовых записей должны однозначным образом разбиваться на отдельныекодовые группы;3) должна существовать возможность распознать, какие кодовые группы соответствуютразличным сдвигам управляющей головки (R, L, E), и различать кодовые группы,соответствующие буквам внутреннего алфавита и буквам внешнего алфавита.Рассмотрим пример такого кодирования для машины Тьюринга Т, имеющей внешнийалфавит A = {a1, a2, ...
, ak} и внутренний алфавит Q = {q1, q2, ... , qz}. Если внешний алфавитсостоит из символов А = {0, 1}, то условия кодирования будут соблюдены при следующемспособе кодирования.1. В качестве кодовых групп возьмем 3+k+m различных слов вида 100...01, где междуединицами проставляются нули; k - число символов внешнего алфавита; m - числосостояний устройства управления.Тогда разбивка строк на кодовые группы производится путем выделенияпоследовательностей нулей, заключенных между двумя единицами.2.
Сопоставление кодовых групп исходным символам внешнего и внутреннегоалфавитов осуществляется согласно следующей таблице кодирования:БукваRELК о д о в а я гр у п п а101100110001100001a1a210000001.................................ak1 0 ...........0 1- 4 нуля- 6 н у л ейВ н у т р ен н и й q11000001а л фа в и тq2100000001(со ст о я н и я ).................................1 0 ................0 1qm- 5 н у л ей- 7 н у л ейВ н еш н и йа л фа в и т2 ( k + 1) н у л е йЧ ет н о еч и сл он у л ей ,б о л ь ш ееч ем 2Н еч ет н о еч и сл он у л ей ,б о л ь ш ее2 ( m + 1) + 1 н у л е й ч е м 3Например, для машины Тьюринга, которая перерабатывает слово bcad в слово bccd,входное слово в универсальной машине Тьюринга с данным кодом будет представленоследующей строкой:10000001 1000000001 100001 100000000001,где 100001 - a, 10000001 - b, 1000000001 - c, 100000000001 - d.Программа же будет представлена следующими строками:1) 1000001 10000001 1000001 10000001 101(q 0b → q 0 b R)2) 1000001 1000000001 1000001 1000000001 101(q 0c → q 0 c R)3) 1000001 100001 100000001 1000000001 101(q 0 a → q 1 c R)3) 100000001 100000000001 10000000001 100000000001 10001(q1d→q2dL).Рассмотрим еще один пример.
Пусть на ленту универсальной машины Тьюрингапоступает слово, составленное из букв английского алфавита. Задача машины Тьюринга переставлять местами буквы n и o таким образом, чтобы сочетание on преобразовывалось вno. Таким образом, после переработки входного слова в нем не должно остаться ни одногобуквосочетания on.Возьмем слово mnonnop, которое должно преобразоваться универсальной машинойТьюринга в новое слово mnnnoop.Пусть внешний алфавит универсальной машины Тьюринга состоит из символов A ={0,1}, а внутренний алфавит Q = {q0, q1, q2, q3, qz }, где qz - заключительноесостояние. Разбивка входных символов на кодовые группы и сопоставление кодовых групписходным символам внешнего и внутреннего алфавитов осуществляется согласноприведенной выше таблице кодирования.Тогда входное слово будет представлено следующим образом:100001 10000001 1000000001 10000001 10000001 1000000001 100000000001,где 100001 - m, 10000001 - n, 1000000001 - o, 100000000001 - p.Ниже представлены команды универсальной машины Тьюринга, которые будутвыполняться при обработке и преобразовании исходного слова.
Напротив каждой командыприводится входное слово таким, какое оно есть в момент начала выполнения даннойкоманды. Символ, на который указывает головка машины Тьюринга, показан как прописнаябуква.q 0m → q 0m Rq 0n → q 0n Rq 0o → q 1o Rq 1n → q 2o Lq 2o → q 0n Rq 0o → q 1o Rq 1n → q 2o Lq 2o → q 0n Rq 0o → q 1o Rq 1o → q 0o Rq 0p → q zp EMnonnopmNonnopmnOnnopmnoNnopmnOonopmnnOnopmnnoNopmnnOoopmnnnOopmnnnoOpm n n n o o P.Программа же будет выглядеть так:1000001 100001 1000001 100001 1011000001 10000001 1000001 10000001 1011000001 1000000001 100000001 1000000001 101100000001 10000001 10000000001 1000000001 1000110000000001 1000000001 1000001 10000001 1011000001 1000000001 100000001 1000000001 101100000001 10000001 10000000001 1000000001 1000110000000001 1000000001 1000001 10000001 1011000001 1000000001 100000001 1000000001 101100000001 1000000001 1000001 1000000001 1011000001 100000000001 1000000000001 1000000000011001.Таким образом, если какая-либо машина Тьюринга Т решает некоторую задачу, то иуниверсальная машина Тьюринга способна решить эту задачу при условии, что кроме кодовисходных данных этой задачи на ее ленту будет подан код программы машины Т.
Задаваяуниверсальной машине Тьюринга Тu изображение программы любой данной машиныТьюринга Тn и изображение любого ее входного слова xn, получим изображение выходногослова yn, в которое машина Тn переводит слово xn .Если же алгоритм, реализуемый машиной Тn, не применим к слову xn, то алгоритм,реализуемый универсальной машиной Тu, также не применим к слову, образованному изизображения xn и программы машины Тn.Таким образом, машина Тьюринга Тn может рассматриваться как одна из программ дляуниверсальной машины Тu .В связи с существованием универсальной машины Тьюринга таблицы соответствия,описывающие различные состояния устройства управления машины, имеют двоякоеназначение:1) для описания состояний устройства управления специальной машины Тьюринга,реализующей соответствующий алгоритм;2) для описания программы, подаваемой на ленту универсальной машины Тьюринга,при реализации соответствующего алгоритма.Современные ЭВМ строятся как универсальные; в запоминающее устройство наряду сисходными данными поставленной задачи вводится также и программа ее решения.Однако в отличие от машины Тьюринга, в которой внешняя память (лента) бесконечна, влюбой реальной вычислительной машине она конечна.3.10.
Алгоритмически неразрешимые проблемыСвойство массовости алгоритмов означает, что они предназначены для решениянекоторой массовой проблемы, формулируемой в виде отображения множества входныхслов в соответствующие им выходные слова. Поэтому всякий алгоритм можнорассматривать как универсальное средство для решения целого класса задач.В теории алгоритмов известны некоторые задачи, для решения которых не существуетединого универсального приема. Однако алгоритмическая неразрешимость проблемырешения задач того или иного класса не означает невозможность решения любой конкретнойзадачи из этого класса. В данном случае речь идет о невозможности решения всех задачодного класса одним и тем же приемом.Таким образом, задачи (проблемы) можно разделить на алгоритмически разрешимые иалгоритмически неразрешимые.Обычно алгоритмическая неразрешимость новых задач доказывается методомсведения к этим задачам известных алгоритмически неразрешимых задач.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
