23.161. Вычислимость

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

где указывает перемещение вправо или влево.

Для того чтобы использовать в вычислении функции должно быть принято некоторое условное обозначение для исходных данных (аргументов и результатов (значений Простейшее видно на рисунке начинает в состоянии до на крайней левой 1 блока на противоположной пустой ленте, и останавливается на крайней левой 1 блока на противоположной пустой ленте. останавливается посредством ввода состояния остановки, то есть,

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

Рисунок 23.1: Вычисление функции при помощи машины Тьюринга

Отсюда следует, что имеется только счетное число вычислимых функций поскольку имеется только счетное число машин Тьюринга. Действительно, мы можем вычислить список всех машин Тьюринга, сначала составив список конечного числа машин с одним переходом, затем машин с двумя переходами и т. д. Это может показаться противоречием открытию предыдущего раздела о том, что список всех вычислимых функций нельзя вычислить, но, как осознал Тьюринг (1936), это не так. Хитрость заключается в том, что не все машины определяют функции, и невозможно выбрать те, которые определяют. Конечно, можно исключить любую машину, которая останавливается в ситуации, непохожей на изображенную на рисунке 23.1; трудность состоит в том, что неизвестно, случится ли остановка. Именно эта трудность препятствует вычислению диагональной функции.

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

Это противоречие показывает, что проблема принятия решения, при наличии машины и исходного элемента, будет ли, в конце концов, иметь место остановка, неразрешима. Эта проблема называется проблемой остановки, и неразрешимость как раз означает, что ни одна машина Тьюринга не может ее решить. То есть, если вопросы «Остановится ли, в конце концов, на исходном элементе формулируются на некотором постоянном конечном алфавите, то нет машины, которая, при наличии этих вопросов в качестве исходных данных, даст на них ответы в качестве результатов. Важность этого вывода заключается в том, что, насколько нам известно, все возможные правила или алгоритмы решения задач можно реализовать при помощи машин Тьюринга. Это «почти что чудо», которое имел в виду Гёдель (1946).

Теперь, когда компьютеры находятся повсюду, считается само

собой разумеющимся, что вычислимость имеет точное, абсолютное значение, синонимичное вычислимости машины Тьюринга. И даже привычен тот факт, что все вычисления можно выполнить на одной, достаточно мощной машине; это соответствует открытию Тьюрингом (1936) универсальной машины Тьюринга. Однако в 1930-х гг. эти утверждения вызывали удивление, особенно у Гёделя, который ранее показал (1931), что родственное понятие «доказуемости» не абсолютно. Его мы обсудим дальше в следующем разделе. Кратко, причина этого различия в том, что новые вычислимые функции нельзя создавать при помощи приведения к диагональному виду, тогда как новые теоремы можно.

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

Это задача принятия решения, при наличии конечного множества определяющих соотношений для группы (раздел 19.6) и слова ли в Между проблемой тождества групп и проблемой остановки есть нечто большее, чем поверхностная аналогия. соответствует машине слова в соответствуют выражению на ленте и соответствует остановке. Определяющие соотношения приблизительно соответствуют функции перехода но, к сожалению, не существует машины, эквивалентной сокращению обратных элементов в Это создает сильные технические трудности, но их преодолел Новиков (1955). Он добился успеха, установив справедливость аналогии, и, следовательно, неразрешимости проблемы тождества групп. Это привело к результатам о неразрешимости множества важных математических задач, среди них задачи о гомеоморфизме, о которой говорилось в разделе 22.7. [Ссылки на литературу даны там, Стиллуэлл (1993) включает также доказательство неразрешимости проблемы тождества.]

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

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

Упражнения

(см. скан)