나는 최근에 문제를 모순적인 증거를 찾아 냈습니다. 증명에서 우리는 튜링 기계에 프로그램 사본과 입력 사본을 입력하여 해당 프로그램이 입력에서 중단되는지 여부를 결정해야합니다. 모순에서 왜 프로그램과 입력으로 프로그램이되어야합니까? 혼란 스러울 경우 미안 해요. 컴퓨터에 프로그램과 임의의 입력을 간단하게 공급할 수 있으며 동일한 결론을 내릴 수 있습니다."haltingproblem"모순 증명
아무도 말해 줄 수 있습니까? 내가 생각지 못했던 특별한 이유가 있습니까?
먼저 증명을 다시 보겠습니다.
HALT_TM는
어떤 기계 문자열의 형태를 취 설명 있다고 가정 결정 불가능하다. HALT_TM = {<M, w>| M is a TM and M halts on input w} 및 A_TM = {<M,w>| M is a TM and accepts w}으로 지정하십시오. 여기서 우리는 A_TM이 결정 불가능하다는 것을 알고 있다고 가정합니다 (대각 화를 통해 증명할 수 있고 튜링 머신보다 더 많은 언어가 있고 주어진 TM이 하나의 언어 만 결정하면 어떤 언어는 결정되지 않습니다).
HALT_TM은 결정할 수 있다고 가정합니다.이 언어에 대해 결정자는 D입니다. 그러면 을 결정하는 기계 M을 만들 수 있습니다. (!이 D 거부하지 않았기 때문에 우리가 알고있는, 정지 할 때까지) D 거부하는 경우 <M',w>
w에 M'을 실행 입력에
D<M', w>에서
M는 다음을 수행
M'이 수락하면 거부하고 거부하면 수락합니다. 당신이 실제로 필요하지 <M> 자체 M에게 유효한 기계 설명 M'를 공급 :이 우리는 지금 당신의 질문의 핵심은 우리의 가정
범용 튜링 기계
와 모순을 참조하십시오. TM과 "프로그램"이 실제로 동등한 것을 기억하십시오. 자세한 내용은 answer을 참조하십시오. 이 같은 대답을 인용하면 : "튜링 기계는 알고리즘의 공식 아날로그입니다". Turing Machine의 한 가지 힘은 다른 튜링 기계 ("Universal Turing Machine")가 문자열을 실행할 수 있도록 문자열로 인코딩 할 수 있다는 것입니다. 주어진 머신이 알고리즘이기 때문에 실제로 "최상위"TM 프로그램과 원하는 입력을 제공하고 있음을 알 수 있습니다.