如何顯示從RE到HP的每種語言的縮減

Question

如果對於RE中的每個L'，存在從L'到L的減少（L'< = L） L被認爲是Hard-RE如果L id Hard-RE並且L在RE中則認爲是完全RE。

我如何證明HP是完整的RE？我需要出示從RE到HP每一種語言還原..

Answer 1

（假設RE表示recursively enumerable和惠普表示halting problem）

HP是平凡的RE

考慮，鑑於圖靈機描述圖靈機的M [A]和一些輸入b，只是會模擬運行M [A]輸入室內用b直到它停止;當它出現時，它輸出TRUE。本機將輸出TRUE IFF M [A]暫停爲b，並將發散時M [A]發散;所以它是暫停問題的一個部分決定因素。

HP是RE-硬

即，給定語言L的RE，它是可還原到HP：因爲L是在RE中，存在一個圖靈機M [M（L）]這樣是，對於任何輸入b，M [M（L）]（b）中會做下列之一：

1. 如果b∈L，然後M [M（L）]（ b）停止輸出TRUE
2. b∉L和M [M（L）]（b）中暫停與輸出FALSE
3. b∉L和M [M（L）]（b）中發散

那麼我們如何將它轉化爲適當的惠益分配給L？十分簡單！只需在（m（L），b）上運行HP oracle！

• 如果HP（M（L），B）返回TRUE，我們知道M [M（L）]（二）收斂，所以只要運行它，並返回任何TRUE/FALSE答案它導致英寸
• 如果HP（M（L），b）中返回s_FALSE_，我們知道，M [M（L）]（b）中發散，其只允許如果b∉L（參見案例3 abo陽離子）。所以我們不要運行M [m（L）]（b）;相反，我們只輸出FALSE。

因此，HP是RE-完整

證明完畢