Вопрос: машина Тьюринга:

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

Тезис Тьюринга:

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

Вопрос: рекурсивные функции:

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

Вопрос: временная и вычислительная сложность алгоритмов:

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