Cтраница 4
Таким образом, машина Мт останавливается тогда и только тогда, когда машина Мп не делает этого ( т.е. в точности тогда, когда Л ( п, п) 1), если обе их запустить в их начальных состояниях считывающими самую левую клетку сплошного блока из п единиц на ленте с пустыми символами во всех остальных клетках. Подставляя т п, мы убеждаемся, что существование машины Мт невозможно, а потому не существует и машины Я: функция Л невычислима по Тьюрингу независимо от того, справедлив тезис Черча или нет. Иными словами, проблема остановки не допускает решения с помощью машины Тьюринга. Если же принять тезис Черча, то она неразрешима и в абсолютном смысле. [46]
Мы доказываем неразрешимость логики первого порядка от противного: мы докажем, что если бы соответствующий тест существовал, то проблема остановки оказалась бы разрешимой, т.е. существовала бы эффективная процедура для ответа на вопрос, останавливаются ли в конце концов машины Тьюринга, если их запускать в состоянии gi на самой левой единице в некотором массиве единиц на ленте с пустыми символами в остальных клетках. Черча верен, проблема остановки неразрешима. В частности, мы доказали, что никакая машина Тьюринга не может реализовать процедуру, решающую проблему остановки, и отметили, что, согласно тезису Черча, это означает невозможность какой бы то ни было эффективной процедуры, решающей проблему остановки. [47]
Как известно, общим в постановке таких проблем является поиск ответа на вопрос, обладает ли исследуемый объект интересующим нас свойством, определяющим его принадлежность к множеству всех объектов, этим свойством обладающих. Известен ряд классических неразрешимых проблем. Так, неразрешимость проблемы остановки означает, что нельзя построить алгоритм, который устанавливал бы, остановится ли машина Тьюринга, начав работать над любым словом в заданном алфавите. Неразрешима и более частная проблема: остановится ли машина Тьюринга, работающая с пустой лентой, не содержащей никаких символов, кроме пустого. [48]
Но в некоторых случаях этого недостаточно. Мы показываем, что проблема остановки сводится к этой задаче. При этом нам важно, чтобы определение алгоритма было как можно проще. [49]
Дело в том, что, согласно главному результату предыдущей главы, некоторая данная машина не останавливается при данном входе тогда и только тогда, когда некоторое предложение ( конъюнкция отрицания предложения Я и всех членов множества А) выполнимо. Но алгоритмический позитивный тест для проблемы остановки очевидным образом существует, а именно, следует имитировать выполнение машинных операций, применив машину при заданном exodel Итак, если бы существовал алгоритмический позитивный тест для выполнимости, то для проблемы остановки имелись бы и позитивный, и негативный тесты и, значит, проблема остановки была бы разрешима. [50]
Один из фундаментальных инструментов, используемых в проведении границы между разрешимыми и неразрешимыми задачами, - понятие сводимости, которое было впервые выдвинуто на первый план благодаря работе логика Эмиля Поста. Задача А сводима к задаче В, если, исходя из процедуры, способной решить задачу В, можно построить алгоритм для решения задачи А. Например, большое значение имел следующий результат: проблема остановки сводима к 10 - й проблеме Гильберта. Отсюда следует, что 10-я проблема Гильберта должна быть неразрешимой, так как в противном случае мы могли бы использовать это сведение, чтобы построить алгоритм для проблемы остановки, которая, как известно, неразрешима. [51]
Рассмотренная в теореме 1.1 неразрешимая проблема х Wx важна по нескольким причинам. Одна из них состоит в том, что неразрешимость многих проблем можно доказать, показав, что они по крайней мере не проще, чем эта. Именно таким путем мы без большого труда доказали, что проблема остановки ( теорема 1.3) неразрешима: этот процесс называется сведением одной проблемы к другой. [52]
Возникает естественный вопрос: каким образом следует определять, остановится какая-то определенная машина Тьюринга ( в которую введены конкретные начальные данные) или нет. Для многих машин Тьюринга ответить на этот вопрос нетрудно, но, как мы видели выше, иногда для ответа может потребоваться решение какой-нибудь до сих пор не решенной математической задачи. Так существует ли некая алгоритмическая процедура для решения общей проблемы - проблемы остановки - полностью механическим путем. [53]