Артур Дент, используя технологию космической эры, еще не доступную на земле, разработал алгоритм, который определяет, останавливается ли TM M1 или нет, когда запускается на чистой ленте.Но потом он обнаружил, что смысл жизни, вселенной и всего остального равен 42.
(a) [5] Получив ТМ М2, докажите, что Артур может определить, останавливается М2 или нет на входе.42, используя уже разработанную им программу, которая определяет, останавливается ли TM M1 или нет при запуске на чистой ленте.Если вы создаете новую TM в своем доказательстве, дайте схему ее машины.
(b) [5] Предположим, что есть программа, которая работает быстрее, чем у Артура, но она отвечает на вопрос, останавливается ли TM M2 на входе 42. Объясните, как Артур может использовать этот алгоритм, чтобы определить, есть ли у некоторого TM M1останавливается при запуске на пустой ленте.Если вы создаете новую TM в своем доказательстве, дайте схему ее машины.
(c) [5] В классе мы доказали, что проблема определения того, останавливается ли TM M при запуске на чистой ленте, не разрешима.Является ли это частью (а) или частью (б), которую можно использовать для доказательства того, что также невозможно определить, останавливается ли ТМ М на входе 42?
Может ли кто-нибудь помочь мне расшифровать то, о чем говорит мой профздесь