Сопоставление сокращений в дополнение к $ _ {tm} $

Question

У меня есть общий вопрос о сокращении картирования. Я видел несколько примеров снижения функций до $ a_ {tm} $

где $ a_ {tm} = { langer m, w rangle: text {for} m text {is turing machine, который принимает строку} w } $

что отлично подходит для доказательства нерешительности. Но скажем, я хочу доказать неузнаваемость вместо этого. То есть я хочу использовать следствие, которое дает $ a le_ {m} b $, если $ a $ не является неузнаваемой, то $ b $ не признается.

Таким образом, для любого произвольного неузнаваемого языка $ c $, который может быть уменьшен до $ overline {a_ {tm}} $ (любого языка примера будет достаточно для примера), как я могу уменьшить $ overline {a_ {tm}} le_ {m} c $?

Для простоты достаточно просто рассмотреть TM в $ overline {a_ {tm}} $.

РЕДАКТИРОВАТЬ

Для разъяснения, $ overline {a_ {tm}} = { langle m, w rangle: m text {это машина Turing, которая не принимает String} w } $

Answer 1

Давайте возьмем $ l _ { yampleSet} = { langle m rangle mid l (m) = yetmeset } $, то есть все машины, которые не принимают слова (то есть, язык которого пуст).

Теперь мы показываем сокращение $ overline {a_ {tm}} le l_ ummentset $. Сокращение осуществляется путем взятия ввода $ ( langer m rangle, w) $ of $ overline {a_ {tm}} $ и преобразования в вход $ { langle tilde m rangle} $ для $ l_ pellyset $ такой, что

$$ ( langle m rangle, w) in overline {a_ {tm}} Quad text {iff} Quad langle tilde m rangle in l _ { yampset} $$

Учитывая $ ( langle m rangle, w) $, мы можем построить $ tilde m $ следующим образом. $ tilde M $ на входе Y делает следующее:

1. Удаляет ленту
2. пишет $ w $ на ленте
3. Занимает $ M $ на $ w $ и выполняет то же самое (если $ M $ принимает, $ tilde M $ также принимает).

Убедитесь, что можно построить кодирование $ tilde M $ из кодирования $ M $ и из $ W $. Теперь давайте убедимся, что это сокращение действительно:

• Если $ ( langle m rangle, w) in overline {a_ {tm}} $, тогда $ m $ либо отклоняет, либо не останавливается. Если это так, то также $ tilde M $ не принимает $ y $, для любого вклада $ y $. Это означает, что $ l ( tilde m) = pellyset $ Таким образом, $ langle tilde m rangle in l _ { umentset} $.
• Если $ ( langer m rangle, w) notin overline {a_ {tm}} $, тогда $ m $ принимает $ w $, таким образом, $ tilde m $ принимает $ y $ (за каждую $ y $). Отсюда следует, что $ l ( tilde m) = sigma^*$, что подразумевает, что $ langle tilde m rangle notin l _ { umptyset} $.

Условие «IFF» сохраняется, и мы успешно отобразили ввод $ overline {a_ {tm}} $ в ввод $ l_ ummentset $. В этом случае мы говорим, что уменьшили $ overline {a_ {tm}} $ до $ l_ pellyset $. То есть, если мы можем решить $ l_ ummentset $, мы также можем решить $ overline {a_ {tm}} $, сначала преобразовав вход, а затем запустив алгоритм, который решает $ l_ ummentset $ на преобразованном входе.

Answer 2

Вы не можете показать, для произвольного неузнаваемого языка $ c $, что $ overline {a_ {tm}} leq_m c $. Если $ overline {a_ {tm}} leq_m c $, то, в частности, степень Turing $ C $ больше или равна степенью Trow $ overline {a_ {tm}} $, потому что много один-один подразумевает уменьшенность Тьюринга. Степень turing $ overline {a_ {tm}} $ составляет 0 '$, так же, как и степень Turing $ a_ {tm} $. Существует множество неузнаваемых языков, чья степень Тьюринга несравнена с $ 0 '$ (ни больше, ни меньше $ 0' $).

Пример, который запустил G., дал работы, потому что $ l_ yetmentset $, в частности, является $ m $ -equivalent для $ overline {a_ {tm}} $. Существует общее явление, что большинство «естественных» проблем, как правило, сопоставимы друг с другом в $ M $-Degree. Но если вы посмотрите на произвольные проблемы, это больше не верно.