¿Es correcto decir que es re si puedo modificar la reducción de LH a L?

Question

Parece que no entiendo correctamente qué significa las reducciones para los idiomas.

Por ejemplo, digamos que hay un idioma llamado LM.

Quiero ver si LM es recursivo o no, para hacerlo, digamos que encuentro una reducción del problema de detección de LM a LM.

Y asumo que LM es recursivo, por lo que muestro que el problema de Hallo, también es recursivo, lo que, por supuesto, es falso, por lo tanto, LM no es recursivo.

¿Pero puedo decir que LM es RE porque encontré una manera de reducir a LH a LM? Si no, ¿cómo puedo mostrar que LM es RE?

Answer 1

Vamos a limpiar un poco las cosas, ya que hay muchas definiciones equivalentes / similares que podrían llevar a malentendidos.

• Puede mostrar que un idioma $ l $ es recursivo al construir una función recursiva $ \ chi_l $ (o una máquina de Turing o cualquier otro modelo de cálculo equivalente) que lo decide, es decir, $$ \ chi_l (x)=comienzan {casos} 1 & \ quad; x \ en l \\ 0 & \ quad; \ Texto {OTW}. \ End {casos} $$ Observe que $ \ chi_l $ debe definirse para todas las entradas.

• Puede mostrar un idioma $ l $ no es recursivo, al encontrar una "reducción de Turing" de un no -El lenguaje recursivo a ello. Esto es probablemente lo que quiere decir con la reducción, y se define de la siguiente manera:

  Decimos que un idioma $ a $ está reducido a un idioma $ b $ , escrito $ a \ le_t b $ , si podemos construir una función recursiva (o máquina de turing) que decida $ a $ < / SPAN> suponiendo que existe tal función para $ b $ .

  Como se ve por definición, la reducción de Turing de alguna manera "transfiere la recursividad" desde $ b $ a $ a $ .

  para cualquier $ a $ y $ b $ de tal que $ A \ leq_t b $ , si $ b $ es recursivo, entonces también lo es $ a $ .

  Por lo tanto, si ya sabemos que algunos $ a $ no son recursivos, luego encontrando una reducción $ a \ leq_t b $ para cualquier $ b $ lo hace no recursivo también.

• Puede mostrar que un idioma $ l $ es re, por Constructiong una función recursiva $ \ varphi_l $ (o máquina de turing) que $ dom (\ varphi_l)= l $ (o se detiene en / lo acepta), por ejemplo $$ \ varphi_l (x)=comienzan {casos} 1 & \ quad; x \ en l \\ \ uprowrow & \ quad; \ Texto {OTW.} \ End {casos} $$

  Donde $ \ UPARROW $ significa "no definido" (o "no se detiene"). Hay otras definiciones de reescense, al igual que su "enumerabilidad" ", que puede observar fácilmente que son equivalentes a este.

• Pero en mostrar un idioma $ l $ no es re, la reducción de Turing no ayuda, ya que no necesariamente Re-ness de transferencia. Por ejemplo, observe que $ \ overline {l_ {halt}} \ leq_t l_ {halt} $ (de hecho, cualquier idioma es curado para su complemento y viceversa), Pero sabemos que $ l_ {halt} $ es re, mientras que $ \ overline {l_ {halt}} $ no lo es.

  Pero hay otros tipos de reducción que realizan la reestructura. Una de esas reducciones se llama "Muchas de una rendibilidad":

  Decimos que un idioma $ a $ es muchos-uno-uno-un-one-one-one-one-one-one-one, un idioma $ b $ , escrito $ a \ leq_m b $ , si hay una función recursiva total $ f $ tal que Para cualquier entrada $ x $ $$ X \ en A \ IFF F (x) \ en B $$

  Esta es una reducción en el sentido de que $ A \ leq_m b $ implica $ A \ leq_t b $ (y no necesariamente viceversa). Entonces, como la reducción de Turing, transfiere la recurtividad. También tenemos

  para cualquier $ a $ y $ b $ de tal que $ A \ leq_m b $ , si $ b $ es re, entonces también es $ A $ .

  Para ver cómo es esto, solo tomar $ \ varphi_a (x)=varphi_b (f (x)) $ .

  Por lo tanto, el método correcto para mostrar un idioma $ b $ no es RE, es encontrar una reducción de muchos-uno $ A \ leq_m b $ para un idioma que no sea un idioma $ A $ . Observe que el ejemplo anterior no funciona aquí, porque $ \ overline {l_ {halt}} \ nleq_m l_ {halt} $ .

Para leer más, consulte

l="nofollow noreferrer"> Teoría de la computabilidad por s.Barry Cooper PT.Yo, cap.7.