Вычислимость и сложность задач на примере машин Тьюринга

Размещено на http://www.allbest.ru/

Содержание

Предисловие переводчика………………………………….….………….….…..2

1. Вычислимость и сложность…………………………………………………...5

1.1. Какие задачи являются вычислимыми? Введение и история……………..5

2. Машины Тьюринга…………………………………….……………………….9

2.1 Универсальные машины Тьюринга……………………………………..…10

2.2 Проблема остановки………………………………….……………………..11

2.3 Вычислимые функции и перечислимость…………..……………………..12

2.4. Неразрешимость проблемы остановки…………………………………….13

3. Примитивные рекурсивные функции………………………………………..16

3.1 Рекурсивные функции……………………………………………………….19

4. Сложность вычислений: функции, вычислимые на практике………..……21

Список используемой литературы……………………………………….……..25

Предисловие переводчика

Что такое алгоритм? Без сомнения, любой человек, даже незнакомый с математикой, ответит, что алгоритм - это некоторая последовательность действий. Однако определить это понятие формально, в математических терминах, не так просто. В начале 20-ого века, в связи с развитием вычислительной техники, этот вопрос стал особенно острым.

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

Эта задача вызвала немалый ажиотаж в математике. Прежде всего, следовало дать формальное определение алгоритма. Сразу несколько ученых почти в одно и то же время разработали свои определения. Алонзо Чёрч ввёл л-исчисление, Курт Гёдель определил рекурсивные функции, Стивен Клине определил формальные системы, Марков - то, что в последствии стало известным как алгоритмы Маркова, Эмиль Пост и Алан Тьюринг определили абстрактные машины, в настоящее время известные как машины Поста и машины Тьюринга. Удивительно, что эти определения, несмотря на внешние различия, эквивалентны, то есть, определяют один и тот же класс вычислимых функций. В связи с этим, Чёрч предположил, что интуитивное понятие “вычислимости” совпадает с тем, которое было введено при помощи точных определений. Это предположение, называемое теперь “Тезисом Чёрча-Тьюринга”, безоговорочно принимается математиками.

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

С помощью машин Тьюринга удалось доказать, что не всякая математическая задача вычислима. Очевидно, число машин Тьюринга счетно и каждой машине можно присвоить некоторый номер. Кроме того, каждой машине Тьюринга можно взаимно однозначно сопоставить ее код - код ее полного набора инструкций. Следует заметить, что любая машина Тьюринга на некотором входе может останавливаться после конечного числа шагов или работать бесконечно долго.

К 1960 году компьютеры были распространены в промышленности и университетах. Постепенно были изобретены алгоритмы для множества задач. Стало ясно, что важно не только существует ли алгоритм для данной задачи, но и то, на сколько он эффективен. Основными параметрами, определяющими сложность алгоритма, стали время и память

Время, требующееся алгоритму, зависит от входа и машины, на котором он выполняется. Хорошей мерой сложности алгоритма является асимптотическая функция времени в худшем случае (как функция от длины входа, n).

Алан Кобхэм и Джек Эдмондс определили класс сложности P как все задачи, решаемые за полиномиальное время, и это отличное математическое определение задач, решаемых на практике

P = ?_i=1,2,… TIME[nⁱ?].

Кроме этого класса, были определены множество других классов сложности, в частности, класс NP. Одна из известнейших нерешенных проблем математики состоит в том, равен ли класс NP классу P. Известно, что класс NP включает в себя класс P. Более того, для всех трудных задач, принадлежащих NP/P, найти полиномиальный алгоритм кажется невозможным. Но и доказать, что такого алгоритма не существует, пока тоже не удается. Несмотря на всю известность такой постановки этой задачи, многим математикам она кажется спорной. Дело в том, что решение этой задачи может повлиять на современное состояние науки совершенно по-разному в зависимости от того, какие нижняя (в случае P?NP) или верхняя (в случае P=NP) оценки на время работы алгоритма будут доказаны.

1. Вычислимость и сложность

вычислимость задача машина рекурсивный

Задача считается вычислимой, если она может быть решена в принципе каким-либо вычислительным устройством. Гильберт верил в то, что все математические задачи вычислимы, но в 30-х годах прошлого века Гёдель, Тьюринг и Чёрч показали, что это не так. Были проведены обширные исследования вычислимости математических задач. В дополнение к этому, существует разделение вычислимых задач на классы сложности, в соответствии с тем, сколько времени - как функции от длины входа - требуется на вычисление ответа. Удивительно, насколько понятно, элегантно и точно классифицируются задачи.

1.1. Какие задачи являются вычислимыми? Введение и история.

В 1930-х, задолго до появления компьютеров, несколько математиков разных стран независимо ввели точные определения вычислимости. Алонзо Чёрч ввёл л-исчисление, Курт Гёдель определил рекурсивные функции, Стивен Клине определил формальные системы, Марков - то, что в последствии стало известным как алгоритмы Маркова, Эмиль Пост и Алан Тьюринг определили абстрактные машины, в настоящее время известные как машины Поста и машины Тьюринга.

Удивительно, но все эти модели в точности эквивалентны: все, вычислимое в л - исчислении вычислимо с помощью машины Тьюринга, то же выполняется и для остальных пар моделей вычисления. После того, как это было доказано, Чёрч предположил, что интуитивное понятие “вычислимости” совпадает с тем, которое было введено при помощи точных определений. Это предположение, называемое теперь “Тезисом Чёрча-Тьюринга”, безоговорочно принимается математиками.

Частично, интерес к этой теме возник благодаря Дэвиду Гильберту. Гильберт верил в то, что вся математика может быть аксиоматизирована. Он чувствовал, что как только математика будет аксиоматизирована, можно будет построить эффективную процедуру, т.е. алгоритм, который будет на вход принимать точное математическое утверждение, и, после конечного числа шагов, будет давать ответ, истинно оно или ложно. Гильберт интересовался тем, что сейчас бы назвали проблемой разрешимости для всей математики.

Как специальный случай проблемы разрешимости, Гильберт рассматривал задачу проверки общезначимости формул логики первого порядка. Логика первого порядка - математический язык, на котором может быть сформулировано большинство математических утверждений. Любое утверждение логики первого порядка имеет точное значение в каждой подходящей логической структуре, т.е. оно либо ложно, либо истинно в каждой такой структуре. Утверждения, истинные в любой структуре, называются общезначимыми. Утверждения, верные в какой-нибудь из структур, называются выполнимыми. Заметим, что формула общезначима, если ее отрицание, , выполнимо.

Гильберт называл задачу проверки общезначимости формул логики первого порядка entscheidungsproblem. В книге Гильберта и Аккермана Principles of Mathematical Logic авторы писали: “Задача проверки общезначимости формул логики первого порядка будет решена, если нам будет известна процедура, позволяющая по любому логическому выражению за конечное число шагов определить его выполнимость или общезначимость. Эта задача должна рассматриваться как основная задача математической логики” (Бергер, Грейдель и Гуревич 1997).

В 1930 году в своем тезисе Гёдель привел полную систему аксиом для логики первого порядка, основанной на Principia Mathematica Уайтхеда и Рассела (Гёдель 1930). Гёдель доказал теорему полноты, а именно, формула выводима из аксиом тогда и только тогда, когда она общезначима. Теорема полноты Гёделя стала шагом к решению entscheidungsproblem Гильберта.

В особенности, так как аксиомы и правила вывода очень просты, то существует алгоритм, который может выписать все доказательства. Заметим, что каждая строка в доказательстве является либо аксиомой, либо следует из предыдущих строк по одному из правил вывода. Для любой последовательности символов мы можем сказать, является ли она доказательством. Тем самым, можно по очереди выписывать все строки длины 1, 2, 3, и так далее, и проверять, является ли каждая из этих строк выводом какой-нибудь формулы. Если это так, то мы можем добавить последнюю строку вывода к нашему списку теорем (выводимых формул). Таким способом мы можем перечислить все теоремы, т.е. в точности все общезначимые формулы логики первого порядка, с помощью простого алгоритма. Более точно, множество общезначимых формул является областью значений вычислимой функции. Пользуясь современной терминологией, можно сказать, что множество общезначимых формул логики первого порядка рекурсивно перечислимо.

Теоремы полноты Геделя недостаточно для того, чтобы предложить алгоритм для решения entscheidungsproblem. Данная формуле Ц будет выводима, описанная выше процедура в какой-то момент выпишет эту формулу, и, тем самым, сможет дать ответ: “Да, Ц выводима”. Тем не менее, если Ц не выводима, то мы можем так никогда и не понять этого. Для решения entscheidungsproblem не хватало процедуры, выписывающей все невыводимые формулы, или, что эквивалентно, все выполнимые формулы.

Год спустя, в 1931, Гедель шокировал математическое общество, доказав свою теорему неполноты: не существует полной и вычислимой системы аксиом для логики первого порядка, в которой будут выводимы все теоремы натуральных чисел. То есть, не существует разумного списка аксиом, из которого выводимы все утверждения, верные для натуральных чисел (Гедель, 1931).

Несколькими годами позже Черч и Тьюринг независимо показали, что entscheidungsproblem неразрешима. Черч использовал методы, использующиеся для доказательства теоремы неполноты, чтобы доказать, что множество выполнимых формул языка логики первого порядка рекурсивно неперечислимо, то есть, это множество не может быть систематически выписано функцией, вычислимой в - исчислении. Тьюринг ввел понятие машин Тьюринга и доказал много интересных теорем, часть из которых мы обсудим в следующем разделе. В частности, он доказал неразрешимость проблемы остановки. Неразрешимость entscheidungsproblem он получил как следствие из этого факта.

Гильберт был очень расстроен из-за того, что его программа по построению процедуры разрешимости для всей математики оказалась невозможной. Но, как мы увидим позже, это помогло понять многое об основах вычислимости.

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

В своей работе 1936 года “О вычислимых числах, с приложением к Entscheidungsproblem ” Алан Тьюринг ввел понятие машин Тьюринга.

Он очень четко представлял, что должна делать машина для вычисления чего-либо. Машины Тьюринга состоят из:

· конечного множества Q возможных состояний, потому что любое устройство в фиксированный момент времени может находиться только в одном из конечного числа состояний;

· потенциально бесконечной ленты, состоящий из последовательных ячеек, у₁, у₂, у_3, из некоторого конечного алфавита У; (У может быть любым алфавитом, состоящим из хотя бы двух различных символов. Удобно фиксировать алфавит У = {0, 1, b}, то есть бинарный алфавит и символ, обозначающий пустую ячейку. Обычно предполагается, что конечный участок ленты заполнен символами бинарного алфавита, а все остальные ячейки пустые.)

· головка чтения/записи в ячейку, обращающаяся к ячейке у_h , h ? 1, и, наконец,

· функция перехода, д: Q Ч У > Q Ч У Ч {-1,0,1} (смысл функции перехода состоит в том, что в текущем состоянии, с головкой указывающей на ячейку с символом у_h , функция перехода определяет следующее состояние, символ, который надо записать в текущей ячейке, и новую позицию головки, h? = h + d, где d ? {-1,0,1} определяется функцией перехода.)

Линейная природа ленты памяти, в отличие от машин с произвольным доступом к памяти, является ограничением на скорость вычисления, но не мощность машин Тьюринга: любую ячейку памяти можно прочитать, но это может занять больше времени, так как придется двигать головку шаг за шагом вдоль ленты.

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

2.1 Универсальные машины Тьюринга

Каждую машину Тьюринга можно однозначно задать ее таблицей переходов: для каждого состояния q, и каждого символа у, д(q,у) содержит новое состояние, новый символ и смещение головки. Эти таблицы переходов могут быть записаны как конечные строки символов, представляющие полный набор инструкций для машины Тьюринга. Далее, эти строки могут быть выписаны в лексикографическом порядке следующим образом: M₁, M₂, M₃, …, где M_i - таблица переходов, т.е. полный набор инструкций (или программа), для машины с номером i.

Тьюринг показал, что можно построить универсальную машину Тьюринга, U, которая выполняет программу любой другой машины Тьюринга. Именно, для i и входного слова w, U будет выполнять ровно то же, что и машина Тьюринга с номером i на входе w, в символьной записи

U(i,w) = M_i(w)

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

2.2 Проблема остановки

Поскольку машины Тьюринга были сконструированы так, чтобы производить все возможные вычисления, то они имеют один недостаток, которого нельзя избежать: некоторые машины на некоторых входных данных не останавливаются. Некоторые машины не останавливаются по глупым причинам, например, мы можем ошибиться в написании программы, и программы зациклится, например, в состоянии 17 с головкой, указывающей на ячейку в которой записана 1, машина останется в состоянии 17, запишет 1, и не сместится. Немного менее глупо, мы можем достичь ячейки, в которой и правее которой ничего не записано, и все же оставаться в том же самом состоянии двигаться по одному шагу вправо до тех пор, пока не встретиться ячейка, в которой записана 1. Обе эти ситуации будут обнаружены и исправлены хорошим компилятором. Однако, рассматривая машину Тьюринга M_F , которая на входе “0” систематически ищет первый контрпример к теореме Ферма, и, как только найдет, останавливается и печатает контрпример. Пока недавно Эндрю Вильс не доказал теорему Ферма, все математики мира в течение трех веков были неспособны определить, останавливается ли M_F на входе “0”. Теперь мы знаем, что нет.

2.3 Вычислимые функции и перечислимость

Так как машина Тьюринга на некоторых входах может не останавливаться, то мы должны быть очень внимательны, определяя функции, вычислимые машинами Тьюринга. Обозначим за множество натуральных чисел и рассмотрим машины Тьюринга как частичные функции из в .

Пусть M - машина Тьюринга, а n - натуральное число. Мы говорим, что лента M содержит число n, если лента M начинается с бинарного представления числа n (начальные нули не обязательны), за которым следуют только пустые клетки.

Если мы запустим машину Тьюринга M на ленте, содержащей n, и она остановится с лентой, содержащей m, то мы говорим, что M вычисляет m на входе n. Если же M на входе n никогда не останавливается, или, когда она останавливается, но на ленте написано не натуральное число (например, когда на ленте есть лидирующие нули или между цифрами есть пустые клетки), тогда мы говорим, что M(n) неопределенно, в символах, M(n) = . Тогда мы можем каждой машине Тьюринга поставить в соответствие частичную функцию M: N > N ? {}. Мы говорим, что функция M везде определена, если для всех n?N, M(n) ? N.

Теперь мы можем формально определить рекурсивно перечислимое множество, которое до этого мы определили интуитивно. Пусть S ? N. Тогда S рекурсивно перечислимо, если существует машина Тьюринга, M, такая, что S является образом функции, вычислимой машиной M, в символьной записи,

S = {M(n) | n ?N; M(n) ? }.

Тем самым, S рекурсивно перечислимо, если оно выписывается какой-нибудь машиной Тьюринга. Предположим, что S рекурсивно перечислимо и все его элементы перечислимы машиной M, как описано выше. Затем мы можем описать другую машину Тьюринга P, которая, на входе n, выполняет M параллельно на всех входах, пока на каком-нибудь из входов M не выдаст n. Если это случилось, P останавливается и выдает “1”, то есть, P(n) = 1. Если n ? S, то M никогда не выдаст n, то есть P(n) никогда не остановится.

Если машина Тьюринга P на входе n останавливается, то обозначим это как P(n)v. Определим множество L(P) как множество всех натуральных чисел, на которых P останавливается.

L(P) = {n | P(n)v}.

Приведенное выше утверждение показывает, что любое рекурсивное множество S есть подмножество натуральных чисел, на которых останавливается какая-нибудь машина Тьюринга P, то есть, S = L(P). Обратное утверждение также верно. Тем самым, S рекурсивно перечислимо тогда и только тогда, когда на нем останавливается какая-нибудь машина Тьюринга P.

Мы называем множество разрешимым, если и только если существует машина Тьюринга M, останавливающаяся на всех входах и для каждого n определяющая, принадлежит ли n множеству S. Если принадлежит, то она выдает “0”, если не принадлежит - “1”.

Множество S ? N разрешимо, если и только если оно само и его дополнение перечислимы. В этом случае мы можем выписать элементы S и N-S в две отдельные колонки, и, тем самым, понять, принадлежит ли n множеству S: если n в первой колонке, то принадлежит, если во второй - то нет.

2.4. Неразрешимость проблемы остановки

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

Тьюринг привел явную конструкцию такого множества. Как мы увидим, он использовал метод, разработанный Кантором для доказательства несчетности множества действительных чисел. Гедель использовал этот же метод для доказательства теоремы неполноты, с помощью которого он построил утверждение J, смысл которого для натуральных чисел моет быть трактован как “J не теорема”.

Тьюринг сконструировал диагональное множество K следующим образом:

K = {n | M_n(n)v}.

То есть, K состоит из машин Тьюринга, которые останавливаются на своих собственных программах. Легко понять, что K является рекурсивно перечислимым. Пусть дополнение к K также является рекурсивно перечислимым, и d - номер машины Тьюринга, останавливающейся на дополнении к K. То есть, для любого n,

n ? K ? M_d?(n)v .

Подставим d вместо n:

d ? K ? M_d?(d)v .

По определению d:

d ? K ? M_d?(d)v .

Тем самым, мы получаем

d ? K ? d ? K,

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

3. Примитивные рекурсивные функции

Теперь мы определим класс примитивных рекурсивных функций. Это очень интересный класс функций, определенный Геделем для доказательства теоремы неполноты. Нам интересны функции из N^r в N, для r = 0, 1, 2, … Здесь r называется валентность функции, то есть, количество аргументов, которое она принимает. Гедель начал с трех очень простых функций и двух естественных операций над функциями, композиции и примитивной рекурсии, каждая из которых берет очень простые функции и определяет новую. Далее мы приведем определения. Этот раздел технический, и его вполне моно пропустить. Важная идея состоит в том, что примитивные рекурсивные функции составляют очень большой класс вычислимых функций, который может быть построен очень просто.

Мы начнем с трех функций:

· ж, нулевая функция валентности 0, ж( ) = 0;

· з, тождественная функция валентности 1, з(n) = n; and,

· у, функция валентности 1, у(n) = n +1.

Теперь рассмотрим две операция над функциями:

· Композиция: если f - примитивная рекурсивная функция валентности a, и g₁, …, g_{a -} примитивные рекурсивные функции валентностей r₁, …, r_a, и k? N, тогда h - примитивная рекурсивная функция валентности k:

h(x₁, …, x_k) = f?(g₁(w₁), …, g_a(w_a)),

где каждый w_i является списком из r_i аргументов, возможно, с повторами, из x₁, …, x_k; и,

· Примитивная рекурсия: если f и g - примитивные рекурсивные функции валентности k и k+2, соответственно, то существует примитивная рекурсивная функция h валентности k+1, удовлетворяющая следующему соотношению:

o h(0,x₁,…,x_k) = f?(x₁,…,x_k); и,

o h(n+1,x₁,…,x_k) = g(h(n,x₁,…,x_k), n,x₁,…,x_k).

Композиция является естественным способом подстановки функций, а примитивная рекурсия - ограниченный тип рекурсии, в котором h с первым аргументом n+1 определяется через h с первым аргументом n, а остальные аргументы остаются такими же.

Определим класс примитивных рекурсивных функций как минимальный класс, содержащий начальные функции и замкнутый относительно композиции и примитивной рекурсии.

Примитивные рекурсивные функции очень просто определяются, но очень полезны. Гедель индуктивно доказал, что каждая примитивная рекурсивная функция может быть просто представлена в теории первого порядка. Затем он использовал примитивные рекурсивные функции для того, чтобы закодировать формулы и даже последовательности формул числами.

Чтобы показать, насколько мощно понятие примитивных рекурсивных функций, нужно доказать много лемм. Ниже мы приведем несколько примеров, в частности, докажем, что сложение, умножение и возведение в степень являются примитивными рекурсивными функциями.

Определим сложение P(x,y) следующим образом:

· P(0,y) = з(y)

· P(n+1,y) = у(P(n,y))

·

Заметим, что это соответствует определению примитивных рекурсивных функций, поскольку функция g(x₁,x₂,x₃) = з(у(x₁)) определяется с помощью начальных функций з и у с помощью композиции.

Далее, определим умножение T(x,y):

· T(0,y) = ж( )

· T(n+1,y) = P(T(n,y),y)

Следующей мы определим функцию возведения в степень, E(x,y). (Обычно 0⁰ считается неопределенным, но так как примитивные рекурсивные функции должны быть всюду определены, мы определим E(0,0) равным 1.) Нам нужно два шага, чтобы определить возведение в степень:

· R(0,y) = у(ж( ))

· R(n+1,y) = T(R(n,y),y)

Наконец, мы можем определить E(x,y) = R(з(y),з(x)) с помощью композиции. (Напомним, что з - тождественная функция, то есть можно просто записать E(x,y) = R(y,x).)

Экспоненциальная функция, E, растет очень быстро, например, E(10,10) равно 10 биллионам, а E(50,50) больше 10⁸⁴ (и это значительно превышает оценку числа атомов во вселенной). Однако, существуют примитивные рекурсивные функции, которые растут гораздо быстрее. Как мы видели, E было определено с помощью медленно растущей функции, у, с помощью трех применений примитивной рекурсии: одна для сложения, вторая - для умножения, третья - для экспоненты. Мы можем продолжать применять примитивную рекурсию для построения очень быстро растущих функций. Давайте сделаем еще один шаг для построения гиперэкспоненциальной функции H(n,m) равной 2 в степени 2 в степени 2 … и так далее, n раз. H примитивная рекурсивная, потому что ее можно определить с помощью E и еще одного применения примитивной рекурсии:

· H(0,y) = y

· H(n+1,y) = E(2,H(n,y))

Тем самым, H(2,2) = 2⁴ = 16, H(3,3) = 2²⁵⁶, что больше чем 10⁷⁷ и сравнимо с числом атомов во вселенной. Если это недостаточно большое число для вас, то подумайте о числе H(4,4).

3.1 Рекурсивные функции

Множество примитивных рекурсивных функций - это огромный класс вычислимых функций. На самом деле, их можно описать как множество функций, вычислимых за то же время, что и некоторая примитивная рекурсивная функция от n, где n - длина входа. Например, так как H(n,n) - примитивная рекурсивная функция, примитивная рекурсивная функция включает все функции из класса TIME[H(n,n)]. (в следующем разделе обсуждаются классы вычислимых функций, в том числе и TIME.) Тем самым, примитивные рекурсивные функции включают все функции, вычислимые в смысле любой более-менее разумной меры, и даже больше этого.

Однако, примитивные рекурсивные функции не включают все функции вычислимые в принципе. Чтобы доказать это, мы снова можем использовать диагонализацию. Мы можем закодировать все определения примитивной рекурсивной функции валентности 1, обозначив их p₁, p₂, p₃, и так далее.

Мы можем построить машину Тьюринга для вычисления диагональной функции D(n) = p_n(n) + 1.

Заметим, что D всюду определенная вычислимая функция из N в N, но она не является примитивной рекурсивной функцией. Почему? Предположим, что D - примитивная рекурсивная функция. Тогда D будет равна p_d для какого-нибудь d? N. Тогда из этого будет следовать, что

p_d(d) = p_d?(d) +1,

противоречие. Тем самым, D не примитивная рекурсивная функция.

Приведенный выше метод работает для любого класса всюду определенных функций. Единственный способ обойти это, если мы хотим получить множество всех функций вычислимых в принципе, а не только на практике, - добавить что-то типа неограниченной операции поиска. Это то, что сделал Гедель для расширения класса примитивных рекурсивных функций до рекурсивных функций.

Определим неограниченный оператор минимизации м. Пусть f - возможно частично определенная функция валентности k+1. Тогда м[f] определяется как следующая функция валентности k. На входе x₁, …, x_k:

For i = 0 to ? do {

if f(i,x₁,…,x_k) = 1, then return i

}

То есть, если f?(i,x₁,…,x_k) = 1, и для всех j < i, f?(j,x₁,…,x_k) определена но не равна 1, то м [f?](x₁, …, x_k) = i. Иначе м[f?](x₁, …, x_k) не определена.

Гедель определил множество рекурсивных функций как замыкание начальных примитивных рекурсивных функций относительно композиции, примитивной рекурсии и м. Определяя рекурсивные функции таким образом, мы получаем в точности множество частично определенных функций, вычислимых в - исчислении, в формальных системах Клине, алгоритмами Маркова, машинами Поста и машинами Тьюринга.

4. Сложность вычислений: функции, вычислимые на практике

Во время второй мировой войны Тьюринг помогал проектировать специальное вычислительное устройство, называемое Bombe. Он использовал его, чтобы взломать немецкий код “Энигма”. К 1960 году компьютеры были распространены в промышленности и университетах. Постепенно были изобретены алгоритмы для множества задач, и математики начали классифицировать алгоритмы в соответствии с их эффективностью и искать наилучшие алгоритмы для конкретных проблем. Это послужило началом современной теории вычислений.

В этом разделе мы обратимся к сложности взамен вычислимости, и все машины Тьюринга, которые мы будем рассматривать, будут останавливаться на своих входах. Вместо того, чтобы рассматривать множество входов, на которых машина останавливается, мы будем рассматривать множество входов, на котором машина Тьюринга выдает 1. Для везде определенной машины Тьюринга M мы определим множество входов, которые она принимает, как

L(M) = {n | M(n) = 1}.

Время, требующееся алгоритму, зависит от входа и машины, на котором он выполняется. Хорошей мерой сложности алгоритма является асимптотическая функция времени в худшем случае (как функция от длины входа, n).

Для входа w обозначим n = |w|. Следуя [Hartmanis, 1989], мы говорим, что машина Тьюринга M работает за время T(n) , если для всех w длины n, вычисление M(w) требует максимум T(n) шагов, а затем машина останавливается. Это так называемая функция времени в худшем случае, так как машина может работать на каком-нибудь входе длины n.

Для всякой функции T : N > N, пусть

TIME[T(n)] = { A | A = L(M) для какой-нибудь машины M, работающей T(n)}

Алан Кобхэм и Джек Эдмондс определили класс сложности P как все задачи, решаемые за полиномиальное время, и это отличное математическое определение задач, решаемых на практике

P = ?_i=1,2,… TIME[nⁱ?]

Всякая задача, не принадлежащая классу P, конечно неосуществима. С другой стороны, у задач, принадлежащих этому классу, обычно есть осуществимые алгоритмы.

Кроме P было изучено много других важных классов, некоторые из них это NP, PSPACE, и EXPTIME. PSPACE состоит из задач, решаемых на полиномиальной памяти. EXPTIME - множество задач, решаемых за время 2^p(n) для некоторого полинома p.

Возможно, один из самых интересных описанных выше классов - это NP. Недетерминированная машина Тьюринга, N, выбирает между двумя возможными действиями на каждом шаге. Если на входе w некоторая последовательность шагов приводит к тому, что это вход принимается, тогда мы говорим, что N принимает w, и мы говорим, что недетерминированное время, необходимое N на входе w - это всего лишь количество шагов в последовательности, которая ведет к принятию w. Мы не учитываем длины всех возможных последовательностей шагов, только той, которая ведет к принятию.

NP иногда определяется как класс проблем S, которые имеют короткие доказательства принадлежности множеству. Например, нам дано множество из m больших натуральных чисел a₁, …, a_m и число t. Проблема Subset Sum формулируется следующим образом: существует ли подмножество данного нам множества, члены которого в сумме дают ровно m? Эту задачу легко решить с помощью недетерминированной машины Тьюринга: для каждого i мы решаем, включить a_i в подмножество или нет. Затем мы суммируем все числе в подмножестве и проверяем, равна ли сумма t. Тем самым, недетерминированное время линейно зависит от длины входа. Однако, не известно (детерминированного) алгоритма, который бы решал эту задачу за менее чем экспоненциальное время.

Алгоритмы хорошо изучены, и известна сложность многих задач. В частности, было определено сведение одной задачи к другой, что используется для сравнения сложности задач. Неформально, можно сказать, что A сводится к B (A ? B), если существует простое преобразование ф, которое преобразует элементы A в элементы B, так что ф(w) ? B ? w ? A.

Довольно большое число задач оказываются полными для одного из выше описанных классов (Задача A полна для класса сложности C, если , и все остальные задачи этого класса не сложнее, чем A. Две полные задачи одного и того же класса имеют одинаковую сложность).

Причина существования полных проблем непонятна. Одно из возможных объяснений состоит в том, что естественные задачи в каком-то смысле выполняют роль универсальных машин Тьюринга. Универсальная проблема в определенном классе сложности может заменить любую другую. Причина того, что класс NP хорошо изучен, состоит в том, что многие задачи принадлежат NP, включая Subset Sum. Ни одна из этих проблем не имеет известного полиномиального алгоритма, хотя некоторые NP-полные задачи имеют приближенные решения.

Многое еще неизвестно о сложности вычислений. Мы знаем, что строго большее количество вычислительных ресурсов позволяет нам решать строго более сложные задачи. Однако, с разными вычислительными ресурсами все не так просто. Очевидно, что P содержится в NP. Далее, NP содержится в PSPACE, поскольку в PSPACE мы можем систематически пробовать каждую ветвь NP вычислений. PSPACE содержится в EXPTIME, поскольку, если для PSPACE требуется более, чем полиномиальное число шагов, то одна и та же конфигурация встретится дважды, и работа машины зациклится. Вот известные отношения между классами:

P ? NP ? PSPACE ? EXPTIME

И хотя кажется очевидным, что все эти неравенства строгие, ни одно из них не было доказано. Единственное, что было доказано - это то, что P строго содержится в EXPTIME. Оставшиеся задачи - это фундаментальные нерешенные задачи теории сложности вычислений.

Список используемой литературы

1. Верещагин. Лекции по математической логике и теории алгоритмов.

2. Гетманова А.Д. Учебник по логике. - М.: ЧеРо, 1997.

3. Ершов Ю.Л. Определимость и вычислимость. - Новосибирск: Научная книга, 2000.

Размещено на Аllbest.ru

...