Perché $ A_ \ text {TM} \ le_m \ text {} ARRESTARE \ le_m \ text {} ^ ARRESTARE \ varepsilon $?

Question

ho un libro che dimostra il problema della terminazione con questa semplice affermazione:

$$ A_ \ text {TM} \ le_m \ text {} ARRESTARE \ le_m \ text {} ^ ARRESTARE \ varepsilon $$

Si afferma che problema della terminazione riduce al linguaggio che consiste di $ \ Langle M, \ omega \ rangle $ per il quale una macchina di Turing $ M $ accetta $ \ omega $ è indecidibile.

Che cosa significa? Che cosa significa la notazione $ \ le_m $ indicare?

Answer 1

Il simbolo $ \ leq_m $ mezzo molti-uno riducibile , il contrasto alla riduzione, come turing riducibile (indicato con $ \ leq_T $) e uno-uno riducibile (indicato $ \ leq_1 $).

A molti-uno riduzione da $ L $ a $ L '$ (dato un alfabeto $ \ Sigma $) è una funzione (calcolabile) $ f: \ Sigma ^ * \ a \ Sigma ^ * $ tale che per ogni $ w \ in \ Sigma ^ * $, si ha che $ w \ in L $ se e solo se $ f (w) \ a L '$. I "molti-uno" mezzi che ci permettono $ f (w) = f (w ') $ (non deve essere iniettiva). Nel vostro ambiente, fondamentalmente significa che è possibile trasformare un ingresso a $ A_ {TM} $ a $ ARRESTARE $ tale che $ A_ {TM} $ accetta un input $ w $ se e solo se $ ARRESTARE $ accetta in ingresso trasformato $ f (w) $.