Словарь основных терминов.

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

Массовая (алгоритмическая) проблема - проблема построения алгоритма, обладающего теми или иными свойствами.

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

Конструктивный объект – объект формальной системы F.S = <L, D> = <A, S, A_x, R>, где L – формальный язык, D – дедуктивные средства конструктивного процесса построения конструктивных объектов, A_x – аксиомы(исходные данные), A_x принадлежит L, R – отношения на множестве объектов(продукции, правила вывода, правила построения объектов) исходных объектов.

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

Алгоритмический язык L = <A, S₁, S₂> предназначен для записи алгоритмов и при этом . Алгоритмический язык называется универсальным, если он содержит алгоритмически полный набор предписаний. Задание универсального алгоритмического языка равносильно заданию алгоритмической системы, т.е. общего способа записи алгоритма.

Алгоритмические процессы – процессы, которые могут имитироваться на подходяще построенной абстрактной машине, описываемой в точных математических терминах

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

Тезис Черча-Тьюринга: «Любая теоретически разрешимая вычислительная задача может быть решена при помощи машины Тьюринга».

Машина Тьюринга (МТ) – алгоритмически полная система побуквенной обработки словарной информации. Эта гипотетическая машина является формой существования и записи алгоритма.

Рекурсивное (разрешимым) множество - множество слов, для которого МТ однозначно решает задачу принадлежности или не принадлежности данного слова языку, т.е. машина либо переходит в состояние q_z1, соответствующее заключению о принадлежности слова языку, либо в состояние q_z2 – слово не принадлежит языку.

Рекурсивно-перечислимое (частично-разрешимое) множество – такое множество, если МТ останавливается в заключительном состоянии для лексем (слов заданного алфавита) и «зависает» (зацикливается) или останавливается в состоянии q_i q_z (безрезультатная остановка) для непринадлежащих языку слов.

Тезис Черча: “Всякая функция, значение которой может вычисляться эффективно, является частично-рекурсивной” (т.е. вычислимыми функциями являются частично-рекурсивные функции – функции, получаемые за конечное число шагов из простейших с помощью суперпозиции, примитивной рекурсии и μ-оператора).

Базисные (простейшие элементарные) функции – числовые вычислимые функции , сопутствующие алгоритмы которых – одношаговые (очевидно, что это всюду определенные рекурсивные функции)

Нуль-функция Z(x₁, x_2,…,x_k)=0 – k-арная функция (оператор аннулирования Z), соответствующий алгоритм вычисления которой: “Любой совокупности значений аргументов x_i функции Z ставится в соответствие ее значение 0”.

Функция тождества (x₁, x_2,…,x_m,…,x_n)= x_m ( - оператор проектирования) – n-арная функция, алгоритм вычисления которой: “Значением функции принять значение m-го аргумента.” (m, n>0, mn).

Функция следования (λ – оператор сдвига) – унарная функция, для которой: “Значением принять натуральное число, следующее за числом, являющимся значением аргумента x”.

Оператором суперпозиции(подстановки) Sⁿ_m называется операция подстановки в функцию от m переменных m функций от n переменных. , а сопутствующий алгоритм которого: «Значения m –арных функций принять за значения аргументов n–арной функции и вычислить её значение».

Оператором примитивной рекурсии R_n[f₁^n-1,f₂ⁿ⁺¹,x₁(n)]=f_mⁿ называется процесс определения функции f (n+1) переменных через n-местную функцию g и (n+2)- местную функцию h в следующем виде:

f(x₁, x_2, …, x_n, 0)= g(x₁, x₂,…, x_n)

f(x₁, x_2, …, x_n, y+1)=h(x₁, x₂,…, x_n, y, f(x₁, x_2, …, x_n, y)),

где g и h – две различные функции соответственно n и n+2 аргументов.

Эта пара равенств называется схемой примитивной рекурсии.

Оператором минимизации  (наименьшего числа оператора) называется преобразование (n+1)-местной функции (в общем случае частичной)  в n-местную f, такую, что для любых х₁, х₂, …х_n, у равенство f(х₁, х₂, …х_n)=у имеет место лишь в том случае, если определены и не равны нулю значения ( х₁, …, х_n, 0), …, ( х₁, …, х_n, у-1) и при этом ( х₁, х₂, …х_n, у)=0

Базисные функции для всех натуральных n, m, где nm являются примитивно-рекурсивными;

• если g₁(x₁,…, x_n), …g_m(x₁,…, x_n), h(x₁,…, x_m) - примитивно-рекурсивные функции, то Sⁿ_m(h, g₁,…, g_m) - примитивно-рекурсивные функции для любых натуральных n, m;

• если g(x₁,…, x_n) и h(x₁,…, x_m, у, z) - примитивно-рекурсивные функции, то R_n(g, h) – примитивно-рекурсивная функция;

• других примитивно-рекурсивных функций нет.

Нормальные алгорифмы U=<A, > - класс словарных алгоритмов, то есть алгоритмов (применимых к словам некоторого алфавита А), элементарными действиями которых являются подстановки в слова (их кортеж есть схема ).

Ассоциативное исчисление (система Туэ) U – формальная система F.S., задающая конечно определенные ассоциативные системы (полугруппы) K_u.

Теорема (Маркова-Поста):

“Существует ассоциативное исчисление, в котором проблема распознавания эквивалентности слов алгоритмически неразрешима”

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

Теоремы Геделя: