Студопедия Главная Случайная страница Задать вопрос

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Вычислимые функции. 1 страница




Пусть — произвольный набор целых неотрицательных чисел. Слово называется основным машинным кодом (или просто кодом) набора (в алфавите ) и обозначается . В частности, слово является основным машинным кодом числа .

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

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

а) если определено, то

б) если не определено, то либо не является кодом никакого числа из N. либо машина не применима к слову .

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

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

Говорят, что машина Тьюринга Т правильно вычисляет функ­цию , если:

а) в случае, когда определено, машина Т, начав работу с левой единицы кода , останавливается, и головка машины в заключительной конфигурации обозревает левую единицу кода k(f(an));

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

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

Расстояние между двумя ячейками С и С' ленты равно уве­личенному на единицу числу ячеек, расположенных между С и С'. В частности, соседние ячейки ленты находятся друг от друга на расстоянии 1. Пусть l — целое положительное число. Подмножество всех таких ячеек ленты, каждые две из которых расположены друг от друга на расстоянии, кратном l, называется решеткой с шагом l. Ленту можно рассматривать как объединение l решеток с шагом l. Пусть — решетка с шагом l. Две ячейки этой решетки назы­ваются соседними, если расстояние между ними, рассматриваемое относительно всей ленты, равно l.

Говорят, что слово записано на решетке , если:

символ записан в некоторой ячейке этой решетки;

символ записан в ячейке , которая является соседней к на решетке и расположена справа от нее и т.д.;

символ записан в ячейке , отстоящей от ячейки на расстояние и расположенной справа от .

Будем говорить, что машина Тьюринга моделирует машину Тьюринга Т на решетке (с шагом l), если, каково бы ни было слово Р (в алфавите А), выполняется следующее условие: пусть на решетке записано слово Р и в начальный момент головка маши­ны обозревает самую левую букву слова Р;машина останав­ливается тогда и только тогда, когда машина Т применима к сло­ву Р; при этом, если Т(Р) определено, то после окончания работы машины на решетке будет записано слово Т(Р).

Справедливо следующее утверждение: для каждой машины Тью­ринга Т и каждой решетки с шагом l можно построить машину Тьюринга , моделирующую машину Тьюринга Т на региетпке

Пусть — произвольный набор це­лых неотрицательных чисел; l-кратным кодом этого набора назы­вается слово в алфавите {0, 1}, имеющее вид .

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

Решетчатым кодом набора назы­вается слово в алфавите {0, 1}, записанное на п решетках с шагом п, причем так, что на первой решетке записано слово , на второй — слово и т.д., на n-й — слово ; начала слов на решетках должны быть согласованы, т. е. самая левая единица на первой решет­ке непосредственно предшествует (на всей ленте) самой левой единице на второй решетке, а эта единица непосредственно предшествует самой левой единице на третьей решетке и т. д.

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

Пример 4. Для функции построить машину Тью­ринга, вычисляющую ее, а также машину Тьюринга, правильно вы­числяющую эту функцию.

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

Решение примера 4. Имеем

Нужно построить такую машину Тьюринга Т, которая «перера­батывает» любое слово в слово и удовлетворяет условию: либо Т(1) не определено, либо Т(1) не является основным машинным кодом никакого числа из N.

Попытаемся реализовать следующую идею: стирая самую левую единицу в слове и проходя оставшееся подслово слева направо, головка пропускает еще одну (пустую) ячейку («раз­делительный нуль») и печатает две единицы подряд; получается слово ; затем головка возвращается к левой единице подслова (если такая единица есть), вычеркивает ее, проходит новое подсло­во слева направо, потом проходит «разделительный нуль» и две ранее напечатанные единицы (справа от него), печатает еще две еди­ницы и опять возвращается к началу «остатка» исходного слова и т.д.; когда в исходном слове все единицы будут вычеркнуты, а во «вновь формируемом» массиве все единицы будут напечатаны, то на ленте «останется» массив из единиц; вычеркнем в нем две первые единицы и «процесс вычисления» закончим.

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

Имеем и (пустое слово). Значит, машина Т действительно вычисляет заданную функцию , но не является машиной Тьюринга, правильно вычисляющей эту функцию (так как она применима к слову 1, соответствующему значению х = 0, а на этом значении аргумента функция не определена). Что­бы из машины Т построить машину Т', правильно вычисляющую функцию достаточно удалить из программы машины Т коман­ду q7~lqoOR и добавить команды и .

 

Варианты заданий

 

Вариант 1

1. Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то выписать результат применения машины Т к слову Р. Предполагается, что — началь­ное состояние, — заключительное состояние и в начальный момент головка машины обозревает самую левую единицу на ленте:

a) б) в)

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

3. Найти результат применения итерации машины Т по паре состояний ( , ) к слову Р (заключительными состояниями являют­ся и ):

 

 

i=3, T:

 

4. Построить машину Тьюринга, вычисляющую функцию :

5. На решетке с шагом l смоделировать работу машины Т, вычисляющей функцию

Вариант 2

1. Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то выписать результат применения машины Т к слову Р. Предполагается, что — началь­ное состояние, — заключительное состояние и в начальный момент головка машины обозревает самую левую единицу на ленте:

a) б) в)

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

3. Найти результат применения машины к слову Р ( — заключительное состояние маши­ны , а — заключительное состояние машины ):

 

 

 

.

4. Построить машину Тьюринга, вычисляющую функцию :

5. На решетке с шагом l смоделировать работу машины Т, вычисляющей функцию

 

Вариант 3

1. Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то выписать результат применения машины Т к слову Р. Предполагается, что — началь­ное состояние, — заключительное состояние и в начальный момент головка машины обозревает самую левую единицу на ленте:

a) б) в)

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

3. Найти результат применения машины к слову Р ( — заключительное состояние маши­ны , а — заключительное состояние машины ):

 

 

 

4. Построить машину Тьюринга, правильно вычисляющую функцию :

5. На решетке с шагом l смоделировать работу машины Т, вычисляющей функцию

 

Вариант 4

1. Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то выписать результат применения машины Т к слову Р. Предполагается, что — началь­ное состояние, — заключительное состояние и в начальный момент головка машины обозревает самую левую единицу на ленте:

a) б) в)

2. Сколько существует неэквивалентных машин Тьюринга в алфавите программы которых содержат только по одной ко­манде?

3. Найти результат применения машины к слову Р ( — заключительное состояние маши­ны , а — заключительное состояние машины ):

 

 







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

Studopedia.info - Студопедия - 2014-2017 год . (0.01 сек.) русская версия | украинская версия