Основные понятия и определения дисциплины

p1	p2	…	pj	…
pm
a0
a1
a2
…
ai				{ax dy pz}
…
an

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

15. 
    Рекурсивные функции.
    

В результате исследований рекурсивных функций было выявлено, что они имеют непосредственную связь с алгоритмами, и можно утверждать, что любой алгоритм является рекурсией, и наоборот.
Пусть задана некоторая функция  = f(x₁, x₂, …, x _n).
Здесь f (или знак функционала) – это правило, задающее связь функции и аргумента. Функционал f может быть любым, в том числе и алгоритмом.
Тогда рекурсивными функциями называют частный случай вычислимых функций. Алгоритмы, являющиеся правилами задания функций, называют алгоритмами, сопутствующими рекурсивным функциям (АСФ).
В основе теории рекурсий лежат ограниченные множества базовых рекурсивных функций и операторов, с помощью которых, исходя из рекурсий, формируются новые функции. Если рассматривать операторы как алгоритмы, то соединение операторов позволяют получить новые алгоритмы.
Базовые рекурсивные функции могут быть трех типов:
1) Функции любого числа независимых переменных, тождественно равные нулю _n()=0,где n – число аргументов функции (n может быть равным нулю).
Например:

АСФ в данном случае гласит: если задана функция _n ,то для любой совокупности значений аргументов значение функции равно нулю.
2) Тождественные функции любого числа независимых переменных _n,i, где n – число аргументов функции, i – номер одного из аргументов.
АСФ гласит: если задана функция _n,i, то значение функции равно значению i-го аргумента (слева направо).
Например:
_3,2(5, 8, 0)=8
_1,1(6)=6
Для тождественных функций:

3) Функции следования одного независимого переменного (х).
АСФ гласит: если задана функция (х), то значением функции нужно считать число, непосредственно следующее за числом, являющимся значением аргумента.
При этом (х)=х’ – последователь аргумента.
Например: (5)=5’=6

16. 
    Алгоритмически неразрешенные проблемы.
    

Разделяют проблемы одиночные и массовые.
Например:
5+7=? – одиночная проблема.
х+у=? – массовая проблема.
Принципиально неразрешимыми должны быть алгоритмы получения объектов, которые парадоксальны, или решения задач, из которых вытекало бы существование парадоксальных объектов.
Например, парадоксами являются:
1) 5-ая аксиома Евклида (Лобачевский дал ей опровержение).
2) 2*2=5
Пример 1:
10-ая проблема Гильберта.
Д. Гильберт в 1901 г. при решении диофантовых уравнений выдвинул проблему, которая гласит:
Найти алгоритм, определяющий некоторое целочисленное решение для произвольного диофантового уравнения
F(x, y, …)=0
Это – полином с целыми показателями степеней и целыми коэффициентами при неизвестных
a_nxⁿ+a_n-1x^n-1+…+a₂x²+a₁x+a₀=0
Для приведенного уравнения существует частное решение, которое заключается в том, что всякий целочисленный корень x_i является делителем a₀. При этом a₀ раскладывают на простые множители и проверяют каждый множитель на соответствие корню.
В 1970 г. ленинградский математик Ю. Матиясевич математически доказал алгоритмическую невозможность решения диофантового уравнения в общем виде.
Пример 2:
Теорема Ферма:
Не существует таких целых чисел a, b, с, n (n>2), для которых справедливо равенство
aⁿ + bⁿ = cⁿ
Эта теорема была доказана для многих значений n и проверена для частных случаев, однако до сих пор не создано общее доказательство теоремы.
Пример 3:
Проблема Гольдбаха.
Х. Гольбах в 1742 г. в письме к Эйлеру сформулировал проблему:
Доказать, что каждое целое число N6 может быть представлено в виде суммы трех простых чисел
N=a+b+c
Это значит, что нужно найти алгоритм, который позволил бы для любого целого числа N6 найти хотя бы одно разложение на три простых слагаемых.
Частый случай решения этой проблемы предложил Эйлер: для четных N эта проблема разрешима и равносильна разложению на два простых слагаемых.
И. Виноградов в 1937 г. доказал, что для нечетных N можно найти три простых слагаемых, но для четных чисел решение не найдено до сих пор.

17.