Вычислимые функции по Тьюрингу.

Выч. Функции. - это множество функций вида, f\colon N \to N, которые могут быть реализованы на машине Тьюринга.

(Пусть Df ⊆ Nk – область определения k-местной функции f: Df → N. Функция fназывается вычислимой по Тьюрингу, если существует машина Тьюринга M такая, чтокак только M начинает с инструкции q0, обозревая самой левый символ строки <n1> 0 <n2> 0... 0 <nk>,(вся остальная часть ленты пуста), тогда:• если f(n1, n2,..., nk) определено, то M, в конце концов, остановится, обозревая самый левый символ строки <f(n1, n2,..., nk)>, при этом часть, находящаяся справа от этой строчки, пустая;• если f(n1, n2,..., nk) не определено, то M никогда не останавливается.)

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

Машина Тьюринга T задаёт словарную функцию под некоторый алфавит V и представляет собой описание машины, т.е. набор объектов (V, Q, q₀, #, I).

V – алфавит машины.

Q – алфавит состояний, .

q₀ – начальное состояние, .

# - пустой символ, .

I – программа машины Тьюринга.

Программа – конечное множество цепочек вида qa→q΄a΄d,которые называются командами.

В каждой цепочке

Предполагается, что в программе никакие две команды не могут иметь одинаковую пару одинаковых символов.

Функционирование машины Тьюринга может быть описано следующим образом. Предполагается, что машина Тьюринга работает с потенциальной бесконечной в обе стороны лентой управления, по которой перемещается считывающая - записывающая головка. Лента разбита на ячейки, в которых могут быть записаны символы из алфавита V или пустой символ #. Расшифровав программу, которая однозначно определяет поведение машины и управление головкой, мы получаем работу машины Тьюринга. Головка в каждый момент времени расположена напротив одной ячейки ленты. Символ, находящийся в ячейке, считывается, после чего машина Тьюринга записывает некоторый символ и, либо остаётся на месте, либо сдвигается влево или вправо.

Машина работает по программе следующим образом.

В начальный момент времени на ленте записывается некоторая цепочка из множества V^*, все остальные клетки ленты заполнены символом #. Управление в начальный момент находится в состоянии q₀, считывающая – записывающая головка обозревает крайний слева символ записанной цепочки. Работа машины состоит в повторе следующего цикла элементарных действий:

1. Чтение головкой символа из ячейки напротив неё.

2. Поиск применимой команды, а именно команды qa → q’a’d, где q- некоторое состояние управления, a- считываемый символ.

3. Выполнение найденной команды, которая состоит в следующем. В обозреваемую головкой ячейку записывается символ a’, символ a- стирается, управление переходит в состояние q’ и головка смещается относительно d. Если d=r головка смещается на одну ячейку вправо, если l - смещается на одну ячейку влево, p – перемещение не производится. Остановка производится в том случае, если на очередном шаге ни одна команда программы не является применимой. Результатом работы машины Тьюринга является цепочка, записанная на ленте.

Дата добавления: 2015-10-24