Est-il correct de dire que l est re si je peux mapper la réduction de LH à L?

Question

Je semble ne pas comprendre correctement quelles réductions signifie pour les langues.

Par exemple, disons qu'il y a une langue appelée LM.

Je veux voir si LM est récursif ou non, pour que cela permet de dire que je trouve une réduction du problème de halte de LM à LM.

Et je suppose que LM est récursif, alors je montrais que le problème de l'arrêt L est également récursif, ce qui est bien sûr faux donc lm n'est donc pas récursif.

Mais puis-je dire que LM est redevable parce que j'ai trouvé un moyen de réduire LH à LM? sinon comment puis-je montrer que LM est re?

Answer 1

Clairons un peu les choses, car il existe de nombreuses définitions équivalentes / similaires pouvant conduire à des malentendus.

• vous pouvez montrer qu'une langue $ l $ est récursif en construisant une fonction récursive $ \ chi_l $ (ou une machine de Turing ou tout autre modèle de calcul équivalent) qui en décide, c'est-à-dire $$ \ chi_l (x)=commence {cas} 1 & \ quad; x \ in l \\ 0 & \ quad; \ Text {otw}. \ fin {cas} $$ Notez que $ \ chi_l $ doit être défini pour toutes les entrées.

• Vous pouvez montrer à une langue $ l $ n'est pas récursif, en trouvant une "réduction de la tutière" d'un non -Récours à celui-ci. C'est probablement ce que vous entendez par réduction, et il est défini comme suit:

  Nous disons qu'une langue $ a $ est en train de réductible à une langue $ B $ , écrit $ a \ le_t b $ , si nous pouvons construire une fonction récursive (ou une machine de Turing) qui décide $ A $ A $ / span> par hypothèse qu'il existe une telle fonction pour $ B $ .

  Comme vous le voyez par définition, la réduction de la tumile «Transferez la récursivité» de $ B $ to $ A $ A $ .

  pour tout $ A $ A $ et $ b $ tel que $ A \ leq_t b $ , si $ b $ est récursif, alors est donc $ a $ .

  Par conséquent, si nous savons déjà que certains $ a $ ne sont pas récursifs, puis trouvant une réduction $ a \ leq_t b $ pour tout $ B $ le rend non récursif aussi.

• Vous pouvez montrer qu'une langue $ l $ est re, par Constructiong une fonction récursive $ \ varphi_l $ (ou machine de Turing) que $ DOM (\ varphi_l)= l $ (ou s'arrête sur / l'accepte / l'accepte), par example $$ \ varphi_l (x)=begin {cas} 1 & \ quad; x \ in l \\ \ unearrow & \ quad; \ texte {otw.} \ fin {cas} $$

  où $ \ unearrow $ $ signifie "non défini" (ou "ni" ne pas arrêter "). Il existe d'autres définitions de la re-Ness, comme son "énumérabilité" de l'homologue, que vous pouvez facilement observer qui sont équivalentes à celle-ci.

• mais dans la montrage d'une langue $ l $ n'est pas re, la réduction de Turing ne vous aide pas nécessairement, car il ne peut pas nécessairement Transférer la re-Ness. Par exemple, observez que $ \ overline {l_ {halt}} \ leq_t l_ {halt} $ (En effet, toute langue est réductible à son complément et inversement), Mais nous savons que $ l_ {halt} $ est re, tandis que $ \ overline {l_ {halt}} $ n'est pas.

  Mais il existe d'autres types de réduction plus forte transférer la re-ness. Une telle réduction est appelée «nombre-on une reddicabilité»:

  Nous disons qu'une langue $ a $ est plusieurs-un-réductible à une langue $ B $ , écrit $ a \ leq_m b $ , s'il y a une fonction récursive totale $ f $ telle que Pour toute entrée $ x $ $$ x \ in a \ iff f (x) \ in b $$

  Ceci est un réduction de la réduction du sens que $ a \ leq_m b $ implique $ A \ LEQ_T B $ (et pas nécessairement inversement). Donc, comme la réduction de la conservation, elle transfère la récursivité. Nous avons aussi

  pour tout $ A $ A $ et $ b $ tel que $ A \ Leq_m b $ , si $ b $ est re, alors est donc $ a $ a $ .

  Pour voir comment cela est vrai, prenez juste $ \ varphi_a (x)=varphi_b (f (x)) $

  .
  .

  D'où la méthode correcte pour afficher une langue $ B $ n'est pas re, est de trouver une réduction de $ A \ LEQ_M B $ pour une langue non-re $ a $ . Notez que l'exemple ci-dessus ne fonctionne pas ici, car $ \ overline {l_ {halt}} \ nleq_m l_ {halt} $

.

Pour plus de lecture, voir

l="Nofollow NOREFERRER"> THÉORIE DE CUISSABILITÉ BY S.Barry Cooper pt.Je, ch.7.