Доказать, что следующие функции вычислимы 5 страница

3. Оператор минимизации (m - оператор)

Пусть задана некоторая функция . Зафиксируем и выясним, при каком у функция . Если значений , при которых , будет несколько, то отыщем минимальное значение , при котором . Поскольку минимальное значение будет зависеть от х, то

функция определяется следующим образом: . Аналогично определяется функция нескольких переменных.

Переход от функции к функции называют применением - оператора. Алгоритм вычисления функции включает в себя следующие шаги:

1. Вычислим . Если это значение , то полагаем . Если , то переходим к следующему шагу.

2. Вычислим . Если = 0, то полагаем . В противном случае переходим к следующему шагу.

Если для всех , то

считается неопределенной.

Рассмотрим функцию , которая может быть получена с помощью оператора минимизации

Для вычисления положим , а переменной будем последовательно придавать значения:

Таким образом .

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

Определение 2. Функция - называется общерекурсивной, если она частично рекурсивна и всюду определена.

Тезис А.Черча. Каждая интуитивно вычислимая функция является частично рекурсивной.

Этот тезис нельзя доказать, так как он связывает нестрогое понятие интуитивно вычислимой функции со строгим математическим понятием частично-рекурсивной функции. Однако этот тезис можно опровергнуть, если построить пример функции интуитивно вычислимой, но не являющейся частично рекурсивной.

2.2. Машинная математика. Машина Тьюринга

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

Машина Тьюринга включает в себя:

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

2) Внутренний алфавит состоит

- из множества символов { , ,…, }, которое определяет состояния машины Тьюринга;

- символов: - вправо, - влево, - на месте.
Символы называются операторами сдвига. Начальное состояние машины Тьюринга обозначается символом . Конечное состояние – символом .

3) Внешняя память, состоит из бесконечной в обе стороны ленты.

Память состоит из регистров, в каждый из которых

можно вписать одну букву алфавита. Принято, что в

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

4) Управляющая головка. Управляющая головка передвигается вдоль ленты за 1 такт на 1 ячейку. В одном такте работы машины управляющая головка может сдвигаться влево, вправо, либо оставаться на месте.

В зависимости от того, какой была начальная информация, возможны два случая:

1) после обработки информации машина переходит в состояние (иначе говорят - машина применима к начальной информации);

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

где – буквы внешнего алфавита; - состояния машины; - операторы сдвига.

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

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

Пусть на ленте записано число

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

После выполнения команды на ленте появится следующая информация

На следующем такте после выполнения команды

После выполнения команды машина переходит в состояние и завершает работу с получением результата 834.

Функциональная схема машины Тьюринга для сложения двух чисел в унарной системе счисления будет выглядеть так

		+
		-

Пусть исходная информация на ленте представлена так

В состоянии устраняется самая правая единица и машина переходит в состояние . В состоянии управляющая головка перемещается, не изменяя состояния регистров, до тех пор, пока не будет достигнут символ . Символ заменяется на и машина переходит в конечное состояние .

2.3. Тезис Тьюринга

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

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

3. КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

Задание 1

Доказать, что следующие функции вычислимы

1. ;