なぜ$ a_ text {tm} le_m text {halting} le_m text {halting}^ varepsilon $？

Question

私はこの簡単な声明で停止の問題を証明する本を持っています：

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

問題を止めることは、チューリングマシン$ m $が$ omega $を受け入れる$ langle m、 omega rangle $で構成される言語に減少すると述べています。

これは何を意味するのでしょうか？表記$ le_m $は何を示していますか？

Answer 1

シンボル$ leq_m $は意味します 多くの削減可能, 、チューリング削減可能（$ leq_t $で示される）や1対1の還元可能（$ leq_1 $と表）などの削減とは対照的です。

$ l $から$ l '$（アルファベット$ sigma $を与えられた）からの1つの減少は、（計算可能な）関数$ f： sigma^* to sigma^* $です。 sigma^*$では、$ f（w） in l '$の場合にのみ、$ w in l $があります。 「多くの」は、$ f（w）= f（w ′）$を許可することを意味します（注射する必要はありません）。設定では、基本的に、入力を$ a_ {tm} $に$ halting $に変換できるようにすることを意味します。 f（w）$。