L = { <M> | M is a Turing machine over {0, 1}, and <M>||<M> (not in) L(M)}
L을 인식 할 수 없다는 것을 어떻게 증명할 수 있습니까? 어떤 아이디어?다음 언어가 결정할 수 없음을 증명하는 방법은 무엇입니까?
나는 L compliment 알아볼 입증했습니다
Set Turing machine to J
1. Run J on input <M>||<M>
2. TM J accepts then accept, it reject the reject.
<M>||<M> is the concatenation of the encoding of the Turing machine.
당신은이 문제에 (대각선) 수용 문제를 줄일 수 있습니다. 나는, 자신의 표기법을 기계 M의 인코딩을 해결하기 위해 가정
D = { <M> | M is a Turing machine over {0, 1}, and <M> (not in) L(M)}
를 사용하려고 및 입력 w 문자열에 소요 경우를 <M> in L(M) 그것을 받아들이는 새로운 프로그램을 고려 (그래서 일정한 행동을 가지고 입력 문자열과 독립적이며 <M>에만 종속). 이전 프로그램은 매개 변수를 사용하여 <M>으로 효과적으로 만들 수 있습니다. 즉, 이전 프로그램의 코드가 h(<M>) 인 총 계산 기능 h가 있습니다. 공식적으로, 나는 여기서 smn 정리를 사용하고있다. 그러나 당신이 그것에 확신을 가지고 있는지 확신 할 수 없기 때문에, 나는 그것을 언급하는 것을 선호하지 않는다.
지금 질문은 h(<M>) is in L입니다.
<M> in D 경우 건설하여 기계 h(<M>)는 임의의 문자열을 허용하지 않으며, 특히 <M> not in D 경우, 다음 건설하여 기계 h(<M>) 어떤을 받아 들일 않습니다
역 L. 그렇게, h(<M>)을 h(<M>)||h(<M>)를 허용하지 않습니다 문자열이고 특히 h(<M>)||h(<M>)을 받아 들일 수 있으므로 은 L이 아닙니다.
L을 결정할 방법이 있다면 우리는 D를 결정할 수있는 방법을 가지게되며 D는 결정할 수 없습니다. 사실 L과 유사하게 생산적이다).