Сводимость этм неразрешима

Question

Я хочу спросить о сокращении.

В доказательстве того, что Etm неразрешима в определении M1,

1. если x!= W, отклонить

2.Если x==w,запустите M на входе w и примите M, если

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

Я был бы более чем счастлив узнать, где я неправ.

Благодарю.

Answer 1

Принятие на машине Тьюринга означает остановку в принимающей конфигурации. Так что, если вы смоделируете M и оно примет, оно остановится, и вы сможете это заметить.

Если M не останавливается, это означает, что он не принимает w. В этом случае вы не должны принимать либо. Один из способов не принимать - работать вечно. Так что, если ваша симуляция М работает вечно, это заставляет вас бежать вечно, и это именно то, что вы должны делать.

Таким образом, вам не нужно знать, остановится ли М. Это не работает по-другому. запустите M на входе w и примите, если M отклонение будет невозможно вычислить, потому что вам нужно будет обнаружить бесконечные вычисления и принять их ввод.