¿Por qué $ a_ text {tm} le_m text {halting} le_m text {halting}^ varepsilon $?

Question

Tengo un libro que prueba el problema de detención con esta simple declaración:

$$ a_ text {tm} le_m text {halting} le_m text {halting}^ varepsilon $$

Establece que el problema de detención se reduce al lenguaje que consiste en $ langle m, omega rangle $ para el cual una máquina turing $ m $ acepta $ omega $ es indecidible.

¿Qué significa esto? ¿Qué indica la notación $ le_m $?

Answer 1

El símbolo $ leq_m $ significa muchos reducibles, contrasta con reducciones como Turing reducible (denotado por $ leq_t $) y un uno reducible (denotado $ leq_1 $).

Una reducción de muchos uno de $ L $ a $ L ′ $ (dado un alfabeto $ sigma $) es una función (computable) $ f: sigma^* a sigma^* $ tal que por cada $ w En Sigma^*$, tenemos ese $ w en l $ si y solo si $ f (w) en l ′ $. El "Many-One" significa que permitimos $ F (W) = F (W ') $ (no tiene que ser inyectivo). En su configuración, básicamente significa que puede transformar una entrada a $ a_ {tm} $ a $ deteniendo $ de modo que $ a_ {tm} $ acepta una entrada $ w $ si y solo si $ detiene $ acepta la entrada transformada $ f (w) $.