Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Шпоры - файл 15.htm


Шпоры
скачать (150.6 kb.)

Доступные файлы (6):

15.htm83kb.23.06.2011 02:11скачать
16.htm54kb.23.06.2011 02:08скачать
17.htm55kb.23.06.2011 02:08скачать
21.htm37kb.24.06.2011 19:29скачать
22.htm57kb.23.06.2011 02:10скачать
25.htm37kb.24.06.2011 19:31скачать

Загрузка...

15.htm

Реклама MarketGid:
Загрузка...

 

15.Конструирование МТ.  Операции над машинами Тьюринга.

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

Пример. Попытаемся построить такую машину Тьюринга, которая из п записанных подряд единиц оставляла бы на ленте n-2 единицы, также записанные подряд, если п > 2, и работала бы вечно, если п = 0 или п = 1.

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

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

q11® q20Л; q21® q30Л.

Машина находится в состоянии q3 обозревает третью справа ячейку из тех, в которых записано данное слово (п единиц). Не меняя содержимого обозреваемой ячейки, машина должна остановиться, т.е. перейти в заключительное состояние q0, независи­мо от содержимого ячейки. Вот эти команды:

q30® q00; q31® q01.

Теперь остается рассмотреть ситуации, когда на ленте записа­на всего одна единица или не записано ни одной. Если на ленте записана одна единица, то после первого шага (выполнив коман­ду q11® q2) машина будет находиться в состоянии q2 и будет обозревать вторую справа ячейку, в которой записан 0. По усло­вию, в таком случае машина должна работать вечно. Это можно обеспечить, например, такой командой:

q20® q20П,

выполняя которую шаг за шагом, машина будет двигаться по лен­те неограниченно вправо (или протягивать ленту через считываю­щую головку справа налево). Наконец, если на ленте не записано ни одной единицы, то машина, по условию, также должна рабо­тать вечно. В этом случае в начальном состоянии q1 обозревается ячейка с содержимым 0, и вечная работа машины обеспечивается следующей командой:

q10® q10П.

Запишем составленную программу (функциональную схему) построенной машины Тьюринга в виде таблицы:

A\Q

q1

q2

q3

0

1

q10П

q00Л

q20П

q20Л

q00

q01

В заключение отметим следующее. Созданная нами машина Тью­ринга может применяться не только к словам в алфавите А - {0, 1}, представляющим собой записанные подряд п единиц (п > 2). Она применима и ко многим другим словам в этом алфавите, напри­мер (проверьте самостоятельно) к словам: 1011, 10011, 111011, 11011, 1100111, 1001111, 10111, 10110111, 10010111 и т.д. (исходя из стандартного начального положения).

С другой стороны, пост­роенная машина не применима (т. е. при подаче этих слов на вход машины она работает вечно) не только к слову «1» или к слову, состоящему из одних нулей. Она не применима и к следующим словам (проверьте самостоятельно): 101, 1001, 11101, 101101, 1100101101 и т.д.

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

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

Во-первых, напомним, что речь идет о функциях (или возможно о частичных функциях, т. е. не всюду определенных), заданных на множестве натуральных чисел и принимающих также натуральные значения.

Во-вторых, нужно условиться, как записывать на ленте машины Тьюринга значения х1,, х2, ..., хп аргументов функции f(x1, x2, ..., хп), из какого положения начинать переработку исходного слова и, на­конец, в каком положении получать значение функции.

Это можно делать, например, следующим образом. Значения х1,, х2, ..., хп ар­гументов будем располагать на ленте в виде следующего слова:



Здесь полезно ввести следующие обозначения. Для натурально­го х обозначаем:

Iх = , 0х =.

Дополнительно полагаем 0° = 1° = Ù — пустое слово. Так что на слова 1° = Ù, I1 = 1, I2 = 11, I3 = 111, ... будем смотреть как на «изображения» натуральных чисел 0, 1, 2, 3, ... соответственно.

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

Если функция f(x1, x2, ..., хп) определена на данном наборе значений аргументов, то в резуль­тате на ленте должно быть записано подряд f(x1, x2, ..., хп) еди­ниц; в противном случае машина должна работать бесконечно. При выполнении всех перечисленных условий будем говорить, что машина Тьюринга вычисляет данную функцию. Таким образом, сфор­мулированное определение 1 становится абсолютно строгим.

Пример 1 Построим машину Тьюринга, вычисляющую фун­кцию f(x) = х/2. Эта функция не всюду определена: областью ее определения является лишь множество всех четных чисел. Поэтому, учитывая определение 1, нужно сконструировать такую машину Тьюринга, которая при подаче на ее вход четного числа давала бы на выходе половину этого числа, а при подаче нечетного — работала бы неограниченно долго.

 



Скачать файл (150.6 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru