Уменьшить $ l_c={\ langle m_1 \ rugle, \ langle m_2 \ rungle): l (m_1) \ cap l (m_2) \ neq \ puredyset \} $ до $ a_ {tm} $

Question

Как уменьшить $ l_c={\ langle m_1 \ rangle, \ langle m_2 \ dangle): l (m_1) \ cap l (m_2) \ neq \ puredyset \} $ $ a_ {tm}={\ langle m, w \ rangle: m $ - это машина Turging, который принимает $ w $ }.

Моя попытка: Создайте Turging Machine $ n $ Использование машины Turing $ u $ , который решает универсальный язык как подпрограмма, чтобы решить $ l_c $ . $ n $ , на любом входе $ <\ lange m_1 \ rungle, \ langle m_2 \ dangle> $ :
$ 1. $ Создать программу, которая генерирует слово $ w \ in \ sum ^ \ ast $ в каноническом порядке .
$ 2. $ Run $ u $ на $ \ langle m_1 , w \ rungle $ и $ \ langle m_2, w \ pangle $ .

















$ 3. $ Если $ u $ принимает оба, принимают.
4 доллара. $ Если нет, обратно на $ 1 $ .

Кажется, не работает. Потому что если $ l (m_1) \ cap l (m_2)=prodset $ , $ n $ Цикл навсегда (он просто не может найти такой $ W $ ).

Answer 1

Направление сокращения, которое вы просите, немного странно. Как правило, мы уменьшаем от math-continer "> $ a_ {tm} $ , чтобы показать неразрешенность.

Возможно, вы подразумеваете спросить о другом направлении?

Во всяком случае, в ответ на ваш вопрос: ваша попытка была на самом деле довольно близко, ему просто нужно немного модификации. Вот как вы можете продолжить:

Учитывая $ m_1, m_2 $ в качестве ввода для $ l_c $ , построить новую машину $ N $ , который работает следующим образом: данный вход $ x $ , $ N $ игнорирует его (т. Е. Стирает $ x $ с его ленты), а затем начинает симулировать $ M_1 $ и $ m_2 $ на каждом сложности $ W \ in \ sigma ^ * $ в каноническом порядке. Обратите внимание, однако, что для моделирования $ m_1 $ и $ m_2 $ On Все / EM> Слова, мы не можем просто запустить их на каждое слово произвольно, так как мы могли бы застревать (мы не используем Oracle, чтобы $ a_ {Tm} $ ). Вместо этого мы запускаем их в Parallel : запустите $ m_1 $ и $ m_2 $ На каждом из первых $ k $ слова в $ \ sigma ^ * $ для шаги $ k $ , а затем увеличить $ K $ by 1. Это довольно распространенный трюк, но это совсем умно.

Теперь, если в любой момент как $ m_1 $ и $ m_2 $ Принять, то $ n $ принимает. В противном случае он продолжает работать и увеличивать $ k $ навсегда.

Сокращение дополняется отправкой $ $ на $ a_ {tm} $ < / span> Oracle (или, альтернативно, это завершено, если вы относитесь к этому как сопоставление-уменьшение).

Обратите внимание, что $ n $ принимает $ \ epsilon $ (и любое другое слово) iff есть Слово, которое принимается как $ m_1 $ и $ m_2 $ .