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

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

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

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

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

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

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

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

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

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

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

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

Расстояние между двумя ячейками С и С' ленты равно уве­личенному на единицу числу ячеек, расположенных между С и С'. В частности, соседние ячейки ленты находятся друг от друга на расстоянии 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. Найти результат применения машины к слову Р ( — заключительное состояние маши­ны , а — заключительное состояние машины ):