Теория рекурсивных функций

Похоже, ничто не может так раздразнить человеческую натуру, как утверждение, что что-то сделать невозможно. Как только исследователи обнаружили нерешаемые задачи (в смысле отсутствия для них алгоритмического решения), другие ученые сразу же приступили к изучению этих задач, чтобы понять, в чем состоит сложность. Сегодня это поле исследований является основной частью дисциплины, известной как теория рекурсивных функций, и многое уже известно об этих сверхсложных проблемах. Действительно, как только математики разработали системы счисления, для которых «количественные» уровни — далекое прошлое, ученые, занимающиеся теорией рекурсивных функций, открыли множество уровней сложности этих проблем, которые выходят далеко за пределы возможностей алгоритмов.

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

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

Машины Тьюринга

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