Проблема остановки машины Тьюринга

Question

У меня есть вопрос о машинах Тьюринга и проблеме остановки.

Предположим, что у нас есть Atm = {(M, w), где M - машина Тьюринга, а w - вход} и
HALTtm ={(M, w) где M - машина Тьюринга останавливается с вводом w}

Я хочу доказать, что HALTtm <= m Atm </p>

Я пробовал некоторые методы, но я думаю, что онидалеко от решения.Кто-нибудь может дать некоторые подсказки ??

Answer 1

Хорошо, заметьте, что для всех (M, w) в HALTtm должно быть, что (M, w) находится в Атм. Затем покажите, что существует некоторый (M ', w'), который является членом Atm, но который не останавливается, и поэтому его нет в HALTtm.

Answer 2

мы можем сделать сокращение от ATM до HALTTM, чтобы M2 был новым компьютером, например, на входе x. Когда M2 принимает x, если M2 принимает x, останавливается и принимает, если M2 отклоняет, тогда M2 идет на бесконечный циклтаким образом, существует топор, который не останавливает M2, поэтому ATm не находится в HALTTM

Answer 3

Что такое <= м? Я думаю, что вы имеете в виду «<a href="http://en.wikipedia.org/wiki/Many-one_reduction" rel="nofollow"> много-один уменьшается до »? В этом случае вы запрашиваете общую вычислимую функцию f такую, что для всех строк x,

x принадлежит HALTtm тогда и только тогда, когда f (x) принадлежит Atm

Если бы такой f существовал, мы могли бы решить проблему остановки: с учетом x вычислить f (x) и проверить, принадлежит ли f (x) к Atm (Atm легко рекурсивен / разрешим). Но так как проблема остановки не разрешима, такое f не может существовать. Таким образом, HALTtm не уменьшает много-один до Atm.

Answer 4

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

1. {aibj | i≠j}