Pourquoi le texte de $ A_ {TM} \ le_m \ texte {ENRAYER} \ le_m \ texte {ENRAYER} ^ \ varepsilon $?

Question

J'ai un livre qui prouve le problème de l'arrêt avec cette affirmation simple:

$$ Le texte de A_ {TM} \ le_m \ texte {} de ENRAYER \ le_m \ texte {ENRAYER} ^ \ varepsilon $$

Il précise que réduit à problème de l'arrêt de la langue composée de $ \ langle M, \ omega \ rangle $ pour lequel une machine de Turing $ M $ accepte $ \ omega $ est indécidable.

Qu'est-ce que cela signifie? Qu'est-ce que la notation $ \ le_m $ indiquer?

Answer 1

Le symbole $ \ leq_m moyen de $ beaucoup-un réductibles , contrairement à des réductions telles que turing réductible (notée $ \ $ leq_T) et un-un réductible (notée $ \ leq_1 $).

Un grand nombre-une réduction de $ L $ à $ L '$ (donné un alphabet $ \ Sigma $) est une fonction (calculable) $ f: \ Sigma ^ * \ à \ Sigma ^ * $ tel que pour tous les $ w \ in \ Sigma ^ * $, nous avons que $ w \ en L $ si et seulement si $ f (w) \ à L '$. Les moyens "beaucoup un" que nous autorisons $ f (w) = f (w ') $ (il ne doit pas être injective). Dans votre contexte, il essentiellement signifie que vous pouvez transformer une entrée à $ A_ {TM} $ à $ ENRAYER $ tel que $ A_ {TM} $ accepte un $ d'entrée w $ si et seulement si $ ENRAYER $ accepte l'$ d'entrée transformé f (w) $.