Задавая задачу для фиксированного машины для вытеснения и фиксированного ввода

Question

Известно, что проблема остановки неразрешима, даже если мы исправим либо Turging Machine $ m $ или Вход $ W $ .

Что если мы исправим как машину , так и ввод?IE, это решительно для каждого фиксированного машины Turging $ m_0 $ и каждый фиксированный вход $ w_0 $ что $ m_0 $ остановится на $ w_0 $ в качестве ввода?

Answer 1

Известно, что проблема остановки неразрешима, даже если мы исправим либо Turging Machine $ m $ или Вход $ W $ .

Вы должны быть более осторожны об этом утверждении. Это не верно для какого-либо фиксированной машины Turing $ m $ что проблема остановки $ \ Text {Halt} _m $ (Решая ввод $ w $ w $ Если $ m $ останавливает на $ m $ - это машина, которая всегда останавливается, мы можем легко решить $ \ TEXT {HALT} _M $ просто путем вывода "да".

Что вы, вероятно, означали сказать, это следующие факты, которые верны:

1. Существует turging machine $ m $ такой, что проблема $ \ text {halt} _m $ (выбирая на вход $ W $ Если $ m $ останавливается на $ w $ ) неразрешен.

2. для всех слов $ W $ , проблема $ \ text { Halt} _w $ (выбирая ввод $ m $ Если $ m $ останавливается на < SPAN CLASS= «Математический контейнер»> $ W $ ) неразрешен.

В частности, для факта 1, мы можем взять $ M $ , чтобы быть универсальным автоматом.

Что если мы исправим как машину , так и ввод? IE, это решительно для каждого фиксированного машины Turging $ m_0 $ и каждый фиксированный вход $ w_0 $ что < SPAN CLASS= «Математический контейнер»> $ m_0 $ остановится на $ w_0 $ в качестве ввода?

Да, проблема становится тривиально разрешенной. Определить язык $ \ TEXT {HALT} _ {m_0, w_0} $ - быть проблемой решения о том, $ m_0 $ останавливаются на $ w_0 $ . Но обратите внимание, что эта проблема больше не имеет никакого входа, что ответ зависит от того, как и то, что ответ может зависеть от ( $ m_0 $ и $ w_0 $ ) теперь фиксируется, то есть часть языка определения, а не часть ввода. Это означает, что ответ - это просто «да» или «нет». Таким образом, мы можем триветично решить эту проблему либо с помощью программы, которая всегда говорит «да», либо программа, которая всегда говорит «нет».

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