나는 TM = DFA는 정지에서 감소를 사용하여 결정 불가능하다는 것을 증명하고있다 이론적으로 Turing Machine은 계산 가능한 모든 기능을 캡처하고 DFA는 상수로 계산할 수있는 기능 만 캡처한다는 것을 이해합니다. 공간 따라서 TM = DFA는 결정 불가능하다. 여기 증명 동등성의 TM과 DFA
내 단계는 : 결정하는 R L (M) = L (D)를 가정EQ_DM = {[D, M] | L (M)가 L (D)}
=
을 우리는 튜링 머신을 생성
HALT_TM = {[M, w] | (→ w 입력에 M 정지는
이 M 승 입력을 중단하지 않았다 수락 → 거부)} R [D, M은] w에 경우 M 정지를 지시하는 방법은 D &를 구성 할 M 있도록
?
TM과 DFA가 동일한 언어를 허용하는지 여부를 결정할 수 있다고 가정합니다. 이것을 사용하여 일반적인 TM에 대한 중지 문제를 해결할 수 있습니다.
어떤 TM M과 단어 w가 주어지면 M이 정지 거부 상태가 될 때마다 M '이 정지 허용 상태가되도록 M'을 구성하십시오. 이제 M '은 M이 멈추게하는 모든 문자열을 받아들이는 TM입니다. L (M ")이 L (M ')와 {w}의 교차점이되도록 M을 M에서 구성하십시오. 여기서 w는 임의의 단어입니다. {w}와 M '에 대해 DFA가 주어지면 항상 직교 좌표계를 사용하여 M' '을 구성 할 수 있습니다.
L (M ")가 DFA의 것과 같은지, 즉 {w}의 DFA와 같은지 여부를 판단 할 수 있으므로 M은 '{w}를 허용 할 수 있습니다. 그것이 w를 받아들이면, L (M ')은 w를 포함하고, L (M')이 w를 포함한다면, M은 w에서 정지한다. M ''이 w를 받아 들일 수 없다면 L (M ')은 w를 포함하지 않으므로 M은 w에서 정지하지 않는다.