Проблема остановки и проблема разрешимости

share the uri
  • Проблема остановки и проблема разрешимости

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

    Формально проблема остановки – это ответ на вопрос о существовании характеристической функции, задаваемой следующими условиями:

    fS((M),x)={1,еслиfM(x)определена0,еслиfM(x)неопределена}

    Если машина M в применении ко входным данным x останавливается, т.е. значение функции fM(x)  определено, то значением функции fS((M),x) является 1. В противном случае, если машина M в применении ко входным данным x никогда не завершает процесс вычисления, то значением функции fS((M),x)  является 0.

    Допустим, что характеристическая функция fS(x,y) вычислима, т.е. существует машина S, которая ее вычисляет. Тогда мы можем определить машину D, которая будет вычислять функцию fD(x) по следующему правилу:

    fD(x)={1,еслиfS(x,x)=0неопределена,еслиfS(x,x)=1}

    Это приводит к противоречию, если применить машину D к ее собственному закодированному описанию (D) .

    fD((D))=1fS((D),(D))=0fD((D))неопределена

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

    Тьюринг показал также, что не существует вычислимой характеристической функции, которая по произвольной машине и произвольному набору исходных данных распознавала бы, печатает ли она в ходе вычисления на ленте конкретный символ, например “0”. Если бы такая вычислимая характеристическая функция существовала, то существовала бы вычислимая характеристическая функция и для проблемы остановки. А поскольку такой функции нет, то нет вычислимой характеристической функции и для появления на рабочей ленте конкретного символа (printing problem).

    В 11 параграфе статьи Тьюринга дается ответ на вопрос о проблеме разрешимости для математики.

    Для этого в языке логики предикатов первого порядка он определяет формулу Un(m), смысл которой заключается в том, что машина m на некотором шаге вычисления печатает на рабочей ленте символ “0”. Затем он показывает, что формула Un(m) доказуема в логике предикатов первого порядка, если и только если машина m на некотором шаге вычисления печатает на рабочей ленте символ “0”. Если бы существовал метод, которые позволял бы по каждой формуле определить, доказуема она или нет, то проблема появления на рабочей ленте символа “0” была бы разрешима вопреки ранее доказанной теореме. Отсюда следует, что не существует такой машины, которая могла бы по произвольной формуле языка первого порядка определить, доказуема она или нет. Таким образом, была окончательно опровергнута уверенность Гильберта в том, что в математике нет непознаваемого (Ignorabimus) [Гильберт, 1969, c. 22].

  • Bibliography

  • Copeland J. Computable Numbers: A Guide // The Essential Turing / Ed. by B. Jack Copeland. Oxford; N. Y., 2004. P. 5–57.
  • Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. 1936–1937. Vol. 42. P. 230–265.
  •  
  • Гильберт Д. Математические проблемы // Проблемы Гильберта / Под ред. П.С. Александрова. М., 1969. С. 11–64.