Cтраница 1
Теория вычислимости - начало теории вычислений - была развита из работ Тьюринга, Клини, Геделя и Черча. Девис [69] и Минский [200] предлагают хорошие введения в нее. [1]
Теория вычислимости обычно излагается так, что речь идет лишь о вычислениях натуральных чисел. Это существенно упрощает изложение, но не ограничивает общности, так как любые данные, вводимые в ЭВМ или выдаваемые ею, будучи представлены в цифровом виде, могут рассматриваться как одно целое число, хотя, возможно, и очень большое. [2]
Наш основной курс теории вычислимости был построен таким образом, чтобы он мог служить трамплином более глубокого и более подробного изучения этой науки в одном из нескольких направлений. В этом кратком послесловии мы укажем ряд областей, с которыми желательно было бы ознакомиться, и дадим некоторые рекомендации для дальнейшего чтения. Предложенное ниже разделение не является жестким, и между различными областями, которые мы назовем, существуют многочисленные взаимосвязи. [3]
Для строгого изложения теории вычислимости необходимо точно определить вид машины, выбранной для выполнения вычислений. С чисто теоретической точки зрения удобно выбрать очень простую модель вычислительной машины, чтобы ее определение было кратким и понятным. Классическим примером такой модели является машина Тьюринга, в которой имеется конечный управляющий автомат, конечный набор символов и потенциально бесконечная лента, причем в каждый данный момент времени управляющий автомат может считывать с этой ленты один символ и записывать на ней также один символ. [4]
Уже поэтому основные понятия теории вычислимости ( или, как говорят, общей теории алгоритмов) достойны внимания математиков и программистов. Но эта теория имеет и более широкий культурный аспект. [5]
Тьюринг и другие первооткрыватели теории вычислимости были первыми, кто доказал, что некоторые корректно определенные математические задачи неразрешимы, т.е. что в принципе не существует алгоритма, способного к решению всех частных случаев таких задач. [6]
Этот результат является одним из двух основ теории вычислимости ( другой является s - m - n - теорема); оба результата опираются на нумерацию программ, данную в гл. [7]
Другой важной темой, которую теория сложности унаследовала от теории вычислимости, является различие между способностью решить задачу и способностью проверить решение. Даже несмотря на то, что не существует общего метода нахождения решения для диофантова уравнения, легко проверить предлагаемое решение. Например, чтобы проверить, является ли х 3, у 2, z - 1 решением приведенного выше диофантова уравнения, просто подставляют в него эти значения и выполняют арифметические действия. [8]
Недетерминированное вычисление восходит к раннему периоду развития математической логики и теории вычислимости: все модели вычисления, основанные на так называемых системах переписывания, неявно являются недетерминированными. [9]
Раздел 6.3 о логических ограничениях машин является кратким введением в теорию вычислимости, или теорию рекурсивных функций, основания которой были заложены в тридцатых годах такими логиками, как Пост, Тьюринг, Черч и Клини. [10]
Это относительно новая область исследования, в которой идеи, возникшие в теории вычислимости на N, переносятся на другие структуры, которые не являются простыми перекодированиями N. Успехи в таком построении достигнуты для некоторых множеств, называемых допустимыми ординалами. Статья Шора [1977] представляет собой введение в эту область и содержит аннотированную библиографию. [11]
Большая часть результатов и технических средств обычной теории вычислимости имеют аналогии в теории относительной вычислимости. [12]
Для иллюстрации того, в какой удивительной степени в теории сложности употребляются аналоги теории вычислимости, Ричард Карп построил эту концептуальную карту или головоломку. Чтобы собрать эту головоломку на плоскости, он использует алгоритм для плоских графов. Наиболее удаленные друг от друга части могут при первом рассмотрении казаться независимыми, но в конце концов теория NP-полноты собирает их вместе, говорит Карп. [13]
Мы ставим здесь своей целью лишь объяснение некоторых результатов, а не точное изложение теории вычислимости. [14]
Доказательство Кука было основано на понятии сводимости, которое мы упоминали ранее, когда говорили о теории вычислимости. Он показал, что всякий частный случай задачи из NP может быть преобразован в соответствующий случай проблемы выполнимости таким образом, что оба они одновременно или имеют, или не имеют решения. Более того, это преобразование может быть выполнено за полиномиальное время. Другими словами, проблема выполнимости является достаточно общей для фиксации структуры любой задачи из NP. Отсюда следует, что если бы мы умели решить проблему выполнимости за полиномиальное время, то мы сумели бы построить алгоритм, работающий полиномиальное время, для любой задачи из NP. [15]