É correto dizer que eu é re se posso mapear redução de lh para l?

Question

Eu pareço não ser entendido corretamente quais meios de reduções para idiomas.

Por exemplo, digamos que haja uma linguagem chamada LM.

Eu quero ver se a LM é recursiva ou não, para fazer isso, digamos que encontre uma redução do problema L-Halting para LM.

e eu suponho que a LM é recursiva, então eu mostro que então o problema da parada L também é recursivo, o que é claro que é falso, portanto, lm não é recursivo.

Mas posso dizer que a LM é re, porque encontrei uma maneira de reduzir o LH para lm? Se não como posso mostrar que a LM é re?

Answer 1

Vamos limpar as coisas um pouco, já que há muitas definições equivalentes / similares que poderiam levar a mal-entendidos.

• você pode mostrar que uma linguagem $ l $ é recursivo construindo uma função recursiva $ \ chi_l $ (ou uma máquina de Turing ou qualquer outro modelo de computação equivalente) que decide, ou seja, $$ \ chi_l (x)=begin {casos} 1 & \ quad; x \ in l \\ 0 & \ quad; \ text {OTW}. \ fim {casos} $$ Observe que $ \ chi_l $ deve ser definido para todas as entradas.

• Você pode mostrar uma linguagem $ l $ não é recursivo, encontrando uma "redução de Turing" de um não -Recursive linguagem para isso. Este é provavelmente o que você quer dizer com redução, e é definido da seguinte forma:

  .

  Dizemos que uma linguagem $ a $ é reduzível para uma linguagem $ B $ , Escrito $ a \ le_t b $ , se pudermos construir uma função recursiva (ou máquina de Turing) que decide $ A $ < / span> por suposição de que existe tal função para $ b $ .

  Como você vê por definição, a redução de Turing de alguma forma "transfere a recursividade" da $ b $ para $ a $ .

  .

  Para qualquer $ a $ e $ B $ tal que $ A \ leq_t b $ , se $ b $ é recursivo, então é $ a $ .

  Portanto, se já sabemos que alguns $ a $ não é recursivo, então encontrar uma redução $ a \ leq_t b $ para qualquer $ b $ torna não recursivo também.

• Você pode mostrar que uma linguagem $ l $ é re, por construir uma função recursiva $ \ varphi_l $ (ou máquina de Turing) que $ Dom (\ varphi_l)= l $ (ou interrompe / aceita), por exemplo $$ \ varphi_l (x)=begin {casos} 1 & \ quad; x \ in l \\ \ utarrow & \ quad; \ text {otw.} \ end {casos} $$

  Onde $ \ utoarrow $ significa "não definido" (ou "não pare"). Existem outras definições de re-ness, como sua "enumerabilidade" homônima, que você pode facilmente observar que são equivalentes a este.

• mas ao mostrar uma linguagem $ l $ não é re, a redução de Turing não ajuda, já que não necessariamente transferir re-ness. Por exemplo, observe que $ \ overline {l_ {halt}} \ leq_t l_ {halt} $ (na verdade qualquer idioma é redutível para o complemento e vice-versa), Mas sabemos que $ l_ {halt} $ é re, enquanto $ \ overline {l_ {halt}} $ não é.

  Mas há outros tipos de Redução de que transferem re-ness. Uma dessas reduções é chamada de "Rezicibilidade de muitas e uma":

  .

  Dizemos que uma linguagem $ a $ é muito redutível para uma linguagem $ B $ , escrito $ a \ leq_m b $ , se houver uma função recursiva $ F $ tal que Para qualquer entrada $ x $ $$ x \ em A \ IFF F (x) \ in B $$

  Este é um Redução mais forte no sentido de que $ a \ leq_m b $ implica $ A \ leq_t b $ (e não necessariamente vice-versa). Assim, como a redução de Turing, transfere a recursividade. Nós também temos

  .

  Para qualquer $ a $ e $ B $ tal que $ A \ leq_m b $ , se $ b $ é re, então é $ a $ .

  Para ver como isso é verdade, basta pegar $ \ varphi_a (x)=varphi_b (f (x)) $ .

  Portanto, o método correto para mostrar uma linguagem $ B $ não é para encontrar uma redução de muitos um $ A \ LEQ_M B $ Para alguma idioma não-re $ a $ . Observe que o exemplo acima não funciona aqui, porque $ \ overline {l_ {halt}} \ nleq_m l_ {halt} $ .

para leitura adicional, consulte

l="Nofollow Noreferro"> Teoria de computabilidade por s.Barry Cooper pt.Eu, ch.7.