チューリングマシンが決定機であるかどうかを知るには？

Question

これに簡単にアプローチできますか？チューリングマシンのダイアグラムを見て決定者であることが分かりますか？

Answer 1

deciderは、すべての入力を停止するマシンです。 There is no general way to prove whether a given machine halts on all inputs。

特定のマシンをお持ちの場合は、実行のすべてのパスが停止していることを正式に証明しようとすることができます。たとえば、マシンのリードヘッドが常に各トランジション（左にならない）で右に移動し、入力がなくなったら停止し、すべての有限インプットに対してマシンは停止します。もっと簡単な例は、停止状態が1つしかないマシンです。 2 - Lは拒否状態にMを入れていない文字列

Answer 2

は、TMがL状態受け入れにMを置く の1-弦場合に限っ言語Lを決定

TM Mは の1-弦場合に限っ言語Lを認識し、 Lは状態受け入れにMを置く 2 - 、NOT L 内の文字列 - あなたはTMの二つの状態との両方の間で変化する」と言っている ループ

@Wanhui橋にOR起こすM - 状態 を拒否にMを置くEITHER州は受諾も拒否もしていないが、これはチューリング決定可能な？ " それは間違いなく無限に進みます。つまりチューリングが認識可能なループに入っています。

Answer 3

あなたは

DECIDER_tm = { <M> : TM M is a decider } is undecidable. 

が矛盾によって証明することが一般的に証明することができます。それが決定可能であり、DECIDER_tmの場合にはRを決定子とする。

HALT_tmの場合はSデシリアライザを、Rをサブルーチンとして使用します。

S = on input <M,w> 
1. construct M_w = " on input x" 
    run M on w 
    if M accepts accept. if M rejects reject. 
2. Run R on M_w 
3. If R accept => accept, if R rejects => reject. 

Mは、すべての入力にM_w停止をwを受け入れまたは拒否した場合M_wが決定器であるので、Rが受け入れることに留意されたいです。 Mがwにループする場合、すべての入力にM_wループがある場合、Rは拒否M_wを拒否します。

我々はHALT_tmが我々の仮定は=>DECIDER_tmが決定不能である間違っていた決定不能である知っているので、我々はHALT_tmのためのサイダーを構築しています。