Универсальная машина Тьюринга U должна определить, останавливается ли M(x)

Question

Универсальная машина Тьюринга U должна определить, останавливается ли M(x)

Итак, у нас есть универсальная машина Тьюринга U, которая должна определить, остановится ли машина Тьюринга M с входом x. Решение должно быть представлено в псевдокоде.

Может ли кто-нибудь помочь мне немного, кто я должен решить это?

-2

turing-machines halting-problem

Источник

user2969401 08 ноя '13 в 14:58

1 ответ

Другие вопросы по тегам turing-machines halting-problem

user1711796 08 ноя '13 в 15:10 2013-11-08 15:10 · Answer 1 · 2013-11-08 15:10

Это звучит как проблема остановки:

Проблема остановки может быть сформулирована следующим образом: "Учитывая описание произвольной компьютерной программы, решите, будет ли программа завершена или будет работать вечно". Это эквивалентно проблеме принятия решения, учитывая программу и ввод, будет ли программа в конечном итоге остановлена при запуске с этим вводом или будет работать вечно.
Алан Тьюринг доказал в 1936 году, что общего алгоритма для решения проблемы остановки для всех возможных пар ввода программы не может быть. Ключевой частью доказательства было математическое определение компьютера и программы, которые стали называться машиной Тьюринга; проблема остановки неразрешима над машинами Тьюринга.

Так что нет, это невозможно.

Если вы хотите, вы можете запустить M на x какое-то время. Если это останавливается, мы знаем, что это останавливается. Если это не останавливается, мы действительно не знаем, останавливается ли это.