Объяснение проблемы остановки машины Тьюринга

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

Рассмотрим следующую задачу: напишите программу, которая, учитывая программу P и входные данные для этой программы, определяет, завершится ли программа при получении этого входа. (Для простоты мы предположим, что программа не запрашивает ввод данных пользователем и не использует случайность, поэтому запуск одной и той же программы на одном и том же вводе всегда делает одно и то же). Можно ли написать программу, отвечающую этому описанию? Ответ - нет. Чтобы показать это, мы воспользуемся доказательством от противного. Мы предположим, что каким-то образом кому-то удастся написать программу, а затем покажем, что в этом случае случится что-то ужасное.

Представьте, что кто-то пишет функцию, которая выглядит так:

function willHalt(program, input)

Эта функция имеет следующие свойства:

1. Он всегда возвращает значение.
2. Если функция возвращает истину, то указанная программа в конечном итоге завершается (останавливается) при запуске на указанном входе.
3. Если функция возвращает false, указанная программа никогда не завершается при запуске на указанном входе (циклах).

На этом этапе мы можем начать скептически относиться к тому, кто написал эту функцию.

Они: «Эй! Я только что написал программу, которая может принимать любую программу и ввод, и она сообщит вам, остановится ли программа на этом вводе!»

Мы: «Да правда? Он может принимать любую программу? Любую программу вообще?»

Они: «Ага! Я так и сказал».

Нас: "Ну, а что насчет вот этой программы?"

А потом даем им эту программу:

function trickyTricky(input) {
    /* Ask whether this program (named trickyTricky) is going to halt
     * on its input.
     */
    if (willHalt(trickyTricky, input)) {
        /* If so, loop infinitely! */
        while (true) { }
    } else {
        /* If not, do nothing and stop running! */
    }
}

Итак, давайте подумаем, что делает эта программа.

• Во-первых, представьте, что эта программа, получив конкретный ввод, в конечном итоге завершает свою работу при запуске на этом входе. Внимательно проследите за программой и посмотрите, что будет дальше. Во-первых, он спрашивает willHalt, будет ли он завершен, и ответ будет «да, да, будет». Это означает, что оператор if оценивается как истина ... поэтому программа переходит в бесконечный цикл! Упс - программа должна была остановиться, но вместо этого она зацикливалась бесконечно!

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

Итак, теперь у нас есть проблема. Если вы действительно можете написать функцию, которая сообщает вам, остановится ли программа на каком-либо вводе, тогда вы можете использовать эту программу для создания программы, которая делает противоположное тому, что она должна делать, - а это невозможно!

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

Если вам интересно, для курса, который я преподавал в прошлом году, я собрал руководство по самооценке и неразрешимости, которое может дать вам немного больше информации о том, как работает этот стиль аргументации.

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

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

Проблема остановки - это ранний пример проблемы принятия решения.

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