Правильно ли сказать L, если я могу отобразить сокращение от LH на L?

Question

Я, кажется, не правильно понимает, какие снижения означает языки.

Например, позволяет сказать, что есть язык называется LM.

Я хочу посмотреть, является ли LM рекурсивным или нет, чтобы сделать это, скажем, я нахожу восстановление от L-остановки задачи в LM.

И я предполагаю, что ЛМ рекурсивна, поэтому я показываю, что тогда проблема L-остановки также рекурсивна, что, конечно, является ложным, поэтому LM не рекурсивна.

Но могу ли я сказать, что LM - это, потому что я нашел способ уменьшить LH к ЛМ? Если нет, как я могу показать, что lm re?

Answer 1

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

.

• Вы можете показать, что язык $ l $ рекурсивный, построив рекурсивную функцию $ \ chi_l $ (или машина Turging или любая другая эквивалентная модель вычислений), которая решает ее, то есть $$ \ chi_l (x)=begin {Casse} 1 & \ Quad; x \ in l \\ 0 & \ Quad; \ Text {OTW}. \ end {случаи} $$ Обратите внимание, что $ \ chi_l $ должен быть определен для всех входов.

• Вы можете показать этот язык $ l $ не рекурсивный, найдя "сокращение" стригации "из не - Известный язык к нему. Это, вероятно, что вы подразумеваете под уменьшению, и он определяется следующим образом:

  Мы говорим, что язык $ A $ - это резервное значение для языка $ B $ , Записано $ a \ le_t b $ , если мы можем построить рекурсивную функцию (или Turging Machine), которая решает $ A $ < / span> При предположении о том, что существует такая функция для $ B $ .

  Как вы видите по определению, сокращение Turing как-то «передает рекурсивность» из $ B $ на $ A $ .

  Для любого $ a $ и $ b $ такое, что $ A \ leq_t b $ , если $ B $ рекурсив, то так это $ a $ .

  Следовательно, если мы уже знаем, что некоторые $ a $ не рекурсивят, то нахождение уменьшения $ A \ leq_t b $ для любого $ B $ делает его нерекурсивным тоже.

• Вы можете показать, что язык $ l $ Re, by constructionG a Rexursive Functions $ \ varphi_l $ (или turging machine), который $ DOM (\ varphi_L)= l $ (или останавливает / принимает его), Например $$ \ varphi_l (x)=begin {Cass} 1 & \ Quad; x \ in l \\ \ uparrow & \ Quad; \ Text {OTW.} \ end {face} $$

  Где $ \ uparrow $ означает «не определено» (или «не HALT»). Существуют и другие определения RE-NES, как его тезка «Перечислимость», которую вы можете легко наблюдать, что эквивалентны этому.

• Но в показывать язык $ l $ не Re, сокращение вытекания не помогает, поскольку это не обязательно Передача RE-NES. Например, соблюдайте, что $ \ uverline {l_ {halt}} \ leq_t l_ {halt} $ (Действительно, какой-либо язык предназначен для его дополнения и наоборот), Но мы знаем, что $ l_ {halt} $ Re, в то время как $ \ uverline {l_ {halt}} $ нет.

  Но есть другие виды, которые более сильны , которые делают перевод RE-NES. Одним из таких сокращений называется «Многие-одна ресилимость»:

  Мы говорим, что язык $ a $ много-один-приводимый к языку $ b $ , Записано $ a \ leq_m b $ , если есть полная рекурсивная функция $ f $ такой, что Для любого ввода $ x $ $$ x \ in \ iff f (x) \ in b $$

  Это более сильнее уменьшение в том смысле, что $ a \ leq_m b $ подразумевает $ A \ leq_t b $ (и не обязательно наоборот). Итак, как уменьшенное уменьшение, он передает рекурсивность. У нас также есть

  Для любого $ a $ и $ b $ такое, что $ B $ Re, то, как и $ a $ .

  Чтобы увидеть, как это правда, просто возьмите $ \ varphi_a (x)=varphi_b (f (x)) $ .

  Следовательно, правильный способ показать язык $ B $ не рекомендуется, чтобы найти много - один редуктор $ A \ leq_m b $ для некоторого языка non-red $ a $ . Обратите внимание, что вышеприведенный пример не работает здесь, потому что $ \ udverline {l_ {halt}} \ nleq_m l_ {halt} $ .

Для дальнейшего чтения см. В разделе

l="nofollow noreferrer"> Теория вычислимости с помощью s.Барри Купер pt.Я, гл.7.