Cтраница 1
Теория рекурсивных функций наряду с алгеброй списков и лямбда-исчислением является еще одной опорой, на которой покоится Лисп. Под вычислимыми понимаются такие задачи, которые в принципе можно запрограммировать и решить с помощью вычислительной машины. [1]
Теория рекурсивных функций имеет как общематематиче-ское, так и прикладное значение. Ее методами доказывается и теорема Матиясевича, сформулированная выше. [2]
В теории рекурсивных функций сами функции ( алгоритмы) и их свойства рассматриваются и классифицируются в соответствии с тем, какие функции можно получить и вычислить, используя различные формы рекурсии. Основная идея рекурсивного определения заключается в том, что функцию можно с помощью рекуррентных формул ( recurrence formula) свести к некоторым начальным значениям, к ранее определенным функциям или к самой определяемой функции, но с более простыми аргументами. Вычисление такой функции заканчивается в тот момент, когда оно сводится к известным начальным значениям. [3]
Отметим, что теории рекурсивных функций и машин Тьюринга являются косвенными теориями алгоритмов, в отличие от теории нормальных алгоритмов, изучающей алгоритмы непосредственно. [4]
Исследования, проводимые в теории рекурсивных функций, можно условно разделить на две части. К первой части относятся исследования, в которых потенциально допускаются произвольные частично рекурсивные либо общерекурсивные функции. Исследования, входящие во вторую часть, напротив, имеют дело с рекурсивными функциями, которые подчиняются ограничениям различного типа. [5]
Эта теорема следует из теории рекурсивных функций. [6]
Помимо того, что теория рекурсивных функций дает удовлетворительный метод для подхода к задачам неразрешимости в языках управления кибернетических систем, она обладает еще одной интересной особенностью. Определяя число при помощи рекурсивной формулы, мы, по существу, задаем процесс, в результате которого ( как мы уже отметили выше) мы неизбежно наткнемся на это число. [7]
В противоположность обычным сводимостям теории рекурсивных функций наши сводимости должны быть вычислительно эффективными. Мы вводим особое понятие эффективной - сводимости, которое достаточно для наших целей. [8]
Таким образом, операции теории рекурсивных функций сводятся к логической последовательности воспроизведения чисел путем многократного применения всего двух правил: заменяй х на х 1, и в последнем шаге замени х нулем. Особое значение этого процесса для кибернетических машин будет показано в следующей главе. [9]
Читатели, знакомые с теорией рекурсивных функций, без труда увидят, что наши теоремы принадлежат этой теории и легко могут быть переведены на ее язык. Ввиду этого доказательства получают двоякое значение. [10]
Формальная теория вычислимости, или теория рекурсивных функций, занимается следующим вопросом: какие вычисления можно выполнить на машине, если игнорировать все технические ограничения, такие, как скорость выполнения операций и объем необходимой памяти. [11]
АЛГОРИТМИЧЕСКАЯ ТЕОРИЯ МНОЖЕСТВ - раздел теории рекурсивных функций, в котором рассматриваются и классифицируются подмножества натуральных чисел с алгоритмической точки зрения, а также исследуются структуры, возникающие в результате такой классификации. АЛГОРИТМИЧЕСКИЙ ЯЗЫК - 1) синоним программирования языка в применении к языкам, в к-рых программа записывается в виде предписаний ( команд, инструкций, операторов) выполнять последовательность. Совокупность обозначений и правил записи, расширяющая общепринятую арвфметико-алгебраич. [12]
Теория алгоритмов - в форме теории рекурсивных функций, машин Тьюринга и финитных комбинаторных процессов Поста - возникла в 30 - х годах, до кибернетики и ЭЦВМ. [13]
Чтение этого превосходного введения в теорию рекурсивных функций требует усердия, но вы будете вознаграждены полнотой и ясностью полученной картины. [14]
В следующем параграфе мы сформулируем некоторые основные результаты теории рекурсивных функций, которые представляют непосредственный теоретико-числовой интерес. После этого будут приведены точные определения и некоторые сведения о доказательствах. [15]