Вычислимость частично рекурсивных функций по Тьюрингу

Теорема 10.1. Для всякой ч.р.ф. f существует м.Т. вычисляющая функцию f.

Доказательство. Доказательство проведем индукцией по определению частично рекурсивной функции f.

Базис. Вычислимость простейших функций машинами Тьюринга очевидна.

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

Суперпозиция. Пусть F^m и fⁿ₁,…, fⁿ_m - ч.р.ф., вычислимые на м.Т. соответственно. Пусть функция Gⁿ получена из них с помощью суперпозиции: Gⁿ=[F^m;fⁿ₁,…, fⁿ_m]. Тогда м.Т. вычисляющая G, работает следующим образом:

1. m раз копирует вход отделяя одну копию от другой символом #;

2. на полученном слове вида

3. запускает параллельную композицию машин и получает конфигурацию вида где y_i=f_i(x₁,…,x_n) (i [1,m]).

4. заменяет все символы 0023 на *;

5. затем запускает программу м.Т. на получившемся после этапа 3) входе вида и вычисляет требуемое значение

Если обозначить м.Т., выполняющую копирование на этапе (1), через Коп^m, а м.Т., выполняющую замену # на * на этапе (3), через Зам_*^#, то требуемую для суперпозиции м.Т. можно представить как

Примитивная рекурсия. Пусть функция Fⁿ⁺¹(x₁,…,x_n,y) получена с помощью оператора примитивной рекурсии из функций gⁿ(x₁,…, x_n) и fⁿ⁺²(x₁,…,x_n, y, z), которые вычислимы на м.Т. и . Определим вспомогательные м.Т.:

· используя строит по входу вида конфигурацию на ленте

· используя строит по входу вида конфигурацию

· на входе вида выдает в качестве результата

· Φ на входе вида проверяет условие y u.

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

Минимизация. Пусть fⁿ(x₁,…, x_n) = μ y [ gⁿ⁺¹(x₁,…, x_n,y)=0] и м.Т. вычисляет функцию gⁿ⁺¹. Определим следующие вспомогательные м.Т.:

приписывает аргумент 0 ко входу, т.е. вход вида переводит в конфигурацию на ленте (напомним, что при унарном кодировании 0 соответствует пустой символ).

копирует свой вход с разделителем #, т.е. по любому входу w выдает w # w.

Через E обозначим м.Т., которая ничего не делает.

Пусть т.е. вход вида машина перерабатывает, используя в , гдеz= g(x₁,…,x_n, y)

Φ на входе вида w # v проверяет непустоту v (т.е. условие v > 0).

Таким образом, при v=g(x₁,…,x_n,y) машина Φ проверяет условие g(x₁,…,x_n,y) 0.

по входу вида стирает #w и прибавляет к y единицу, т.е. выдает результат:

Наконец, по входу выдает |^y, стирая ненужные блоки символов.

Ясно, что каждая из перечисленных м.Т. , , , и Φ легко реализуема. Построим теперь с их помощью следующую м.Т.

Из этого определения непосредственно следует, что вычисляет функцию fⁿ(x₁,…, x_n), заданную с помощью оператора минимизации.

Слово или цепочка употребляются в одном и том же смысле.

Алфавит – конечное, непустое множество символов.

V= { a₁, a₂, …, a_n }

Цепочкой в алфавите V называется конечный объект, получаемый выписыванием одного за другим символов из алфавита V.

Для V = {0, 1, 2, …, 9} цепочкой является натуральное число.

Длина цепочки есть количество символов в ней. |α| - длина цепочки.

Пустая цепочка не содержит ни одного элемента (ε) алфавита. Пустая цепочка не есть символ пробела.

Множество всех цепочек (включая и пустую) над алфавитом V обозначается V*.

n-местной словарной функцией над алфавитом V называется n-местная функция над множеством V^*× V^*×V^*×V^*×…×V^*→V^*.

В качестве двуместной словарной функции может выступать операция конкатенации. Цепочка γ называется подцепочкой цепочки α, если α представляет собой конкатенацию α=υγω, где ω,υ – возможные цепочки. При этом γ называется префиксом цепочки α, если цепочка υ пустая, или суффиксом, если ω пустая.

Существует взаимнооднозначное соответствие между неотрицательным целым числом и цепочкой в произвольном алфавите V. Символы алфавита V можно произвольным образом упорядочить, перенумеровать их числами {1,2,…,n}. Задаётся функция упорядочивания . Пустой цепочке поставим в соответствие число 0, а остальные цепочки упорядочим по следующим правилам.

Если |α|<|β|, то α располагается левее β.

Если цепочки имеют одинаковую длину, то они упорядочены в алфавитном порядке, т.е. с учётом порядковых номеров символов алфавита.

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

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

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

Машина Тьюринга 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 – перемещение не производится. Остановка производится в том случае, если на очередном шаге ни одна команда программы не является применимой. Результатом работы машины Тьюринга является цепочка, записанная на ленте.

Билет № 27

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