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

Question

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

Предположим, что мы имеем Банкоматы = {(М, ш), где М представляет собой машину Тьюринга и ш является входным} и
HALTtm = {(М, ш), где М представляет собой машину Тьюринга останавливается с входом ш }

Я хочу доказать, что HALTtm < = м Банкоматы

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

Answer 1

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

Answer 2

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

1. {aibj | i≠j}

Answer 3

< Что такое = т? Я думаю, вы имеете в виду «many-one reduces to»? В таком случае, что вы просите в общей вычислимая функция F такая, что для всех строк х,

х принадлежит HALTtm тогда и только тогда, когда f (х) принадлежит банкомате

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