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

Question

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

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

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

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

Answer 1

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

Answer 2

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

1. {aibj | i≠j}

Answer 3

Что такое <= м? Я думаю, что вы имеете в виду " много-один сводится к"? В этом случае вы запрашиваете полную вычислимую функцию f, такую ​​что для всех строк x,

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

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

Answer 4

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

поэтому существует топор, который не останавливает M2, поэтому ATm не находится в HALTTM