Основные элементарные АФ. Рекурсивные функции.

 

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

 

2) К основным элементарным арифметическим функциям относятся:

а) Нуль-функция: О(x₁, x₂,…,x_n)=0;

б) Функция следования: S(x)=x+1; (продвижение по поступательному ряду на 1 вправо по отношению к выбранному x.

в) Проектор (на j координатную плоскость): П_j(x₁,…,x_j,…,x_n)=x_j; (выбор указанной j координаты в данном целочисленном векторе).

Эти функции являются арифметическими и определенными на всем Z₊ⁿ и четко определенными, т.е. к каждой из них «прилагается» алгоритм ее вычисления.

 

3) Основные операторы, с помощью которых строятся так называемые частично рекурсивные функции (общерекурсивные функции), т.е. задаются на некотором D Z₊ⁿ (или на всем Z₊ⁿ). Такими операторами являются операторы суперпозиции, операторы примитивной рекурсии. Оператор наименьшего корня.

 

4) Оператор суперпозиции определяется с помощью одной M-местной функции g(x₁,x₂,…,x_n) и m-n-местные функции φ(x₁, x₂,…,x_n), (j=1,2,…,m). Теперь на основе функций g и φ строится новая функция f(x₁, x₂,…,x_n)=g(φ₁(x₁, x₂,…,x_n),…, φ_m(x₁, x₂,…,x_n)). Т.е. аргументы функции g заменяем на соответствующие значения функции φ_j и тем самым получаем новую сложную функцию f.

 

5) Оператор примитивной рекурсии. Задается (n-1)-местная функция φ(x₁, x₂,…,x_n-1) и (n+1)-местная функция g(x₁, x₂,…,x_n,x_n+1) Новая n-местная функция строится так: f(x₁,…,x_n-1,0)= φ(x₁, x₂,…,x_n-1) и f(x₁, x₂,…,x_n-1,y,f…). Т.е. для каждого фиксированного аргумента функции f значения при этом аргументе равные нулю берется как значение φ, а значения при этом y=1,2,… вычисляются через 0,1…значение путем указанной суперпозиции функций g и f.

 

6) Оператор наименьшего корня определяется с помощью (n+1)-местной функции g следующим образом: функция f(x₁, x₂,…,x_n) каждому набору (x₁, x₂,…,x_n) сопоставляет тот y (неотрицательный целый), который является наименьшим корнем уравнения g(x₁,x₂,…,x_n,y)=0.

Уточнение понятия алгоритма:

1) Два алфавитных оператора называют равносильными А⁽¹⁾ ≡ А⁽²⁾, если совпадают их область определения и их области значений, а также способы их задания.

 

2) Два оператора называют эквивалентными А⁽¹⁾ ~ А⁽²⁾, если совпадают их области определения и их области значений, но они заданы разными способами.

 

3) В математике под алгоритмом понимают алфавитный оператор вместе со своим способом задания (конструктивно заданный оператор).

 

4) Алгоритмическая система есть общий способ задания алфавитных операторов, обладающий так называемым свойством универсальности: Для каждого данного алфавитного оператора в рамках этой системы найдется свой алфавитный оператор, эквивалентный данному (алгоритм эквивалентных данных).

Теорема Тьюринга.

 

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

Примеры алгоритмов:

1. Сконструировать машину Тьюринга, вычисляющую функцию следования S(x)=x+1.

Сконструировать – значит ввести внешний алфавит и записать программу. А={0,1}. Поскольку х – целое неотрицательное число, то на ленте машины можно записать столько единиц, чтобы их сумма составляла х (если х=0, то не писать ничего, пустые ячейки заполнены нулями).

 

…

…

…

Программа должна быть устроена таким образом, чтобы на месте какого-то нуля она написала 1 и остановилась. Для определенности выберем положение головки на крайней правой ненулевой ячейке.

q₁1→q₁1(Л)

…

q₁0→q₁1

В результате появилась еще 1 единица, т.е. число увеличилось на единицу, а значит, функция следования вычислена.

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

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

 

3) Пример словесного алгоритма: Вычислить произведение вида А=∏a_j.

1. Присвоить А значение 1 (А=1), перейти к п.2.

2. j=1, перейти к п.3.

3. А=А a_j, перейти к п.4.

4. Если j=n, то п.3. – ответ, иначе если j<n, то j=j+1, перейти к п.3.

Машина Тьюринга(МТ).

1) Машина Тьюринга – это алгоритмическая система, реализующая алфавитный оператор.

а) Имеется так называемый внешний алфавит G={ a₀, a₁,…..,a_n}, символы которого, сформированные в слов, записываются в соседних ячейках некоторой бесконечной в обе стороны ленты.

a0

a0

a1

aj

ar

a0

ar

a0

б) В каждый момент на ленте машины записано одно и только одно слово.

в) Все остальные ячейки ленты заполнены «пустым символом» (a₀).

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

д) Имеется также так называемый алфавит внутренних состояний Q = {q₀, q₁, …, q_m,….}и в каждый момент при обозрении определенной ячейки машина находится в некотором состоянии q_j. Так, например, обозревая ячейку с символом a_k в состоянии q_i, запишем q_ia_k.

 

2) Как работает машина Тьюринга:

Задается программа, т.е. система команд вида q_ia_k → q_ja_l(S) (1) Каждая команда (1) означает, что обозревая ячейку a_k в состоянии q_i, машина стирает символ a_k и записывает в эту ячейку символ a_l (возможно, что k=l). После этого машина переходит в состояние q_j и затем со считывающей головкой происходит процесс S, а именно, либо головка передвигается на одну ячейку вправо, что обозначается символом П, либо влево (Л), лтбо головка остается на прежнем месте, что обычно не обозначают никаким символом. Принято обозначать первую команду символом q_1, а завершающую символом q_0, так что в команде 1 i≠0.

Итак, задано слово, задано начальное положение головки (как правило задано) и задана программа, т.е. система команд вида (1), среди которых самая первая начинается с символа q₁. Выполняя последовательно указанные команды, машина преобразует каждый символ заданного слова в другой или этот же символ до тех пор, пока не придем к команде вида (1), в которой j=0. На этом преобразование слова завершается, и мы получаем выходное слово в том же алфавите.

 

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

 

4) Как же вычисляет арифметические операции машина Тьюринга? Пусть имеется функция n-переменных y=f(x₁, x₂,…,x_n), где все x_jÎZ₊. В этом случае в качестве алфавита внешних символов можно задать алфавит G={0,1}, где 0-пустой символ. На ленте машины записывается любой x_j в виде стольких последовательностей единиц, число которых равно x_j. Пробелы между двумя соседними наборами единиц (двумя соседними аргументами) могут быть обозначены заданным количеством нулей. В результате каждое написанное слово будет означать вектор x =(x₁, x₂,…,x_n). Теперь начинается действие программы. Считая вычислимую функцию однозначной, мы получаем в результате некоторый набор единиц, который и будет составлять число y.

Замечание. Один из возможных способов записи аргументов, включая нулевое значение, состоит, например, в том, что аргументу 0 соответствует 1, аргументу x_j >0 соответствует количество единиц x_j+1. В этом случае робел можно обозначить одним нулем.

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

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

 

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