4
튜링 기계의 정의에 따르면 명령 표 (프로그램)를 읽거나 수정할 수 없다고 정의되어 있습니다. 바로 Turing Machine은 자체 프로그램에 대한 액세스 권한이 없습니다.튜링 기계 명령 표
이 제한을 약화시킬 수 있다면 어떤 이점이 있습니까? 기계가 프로그램을 분석하고 수정할 수있는 경우. 튜링 계산 작업의 범위를 확장 할 수 있을까요?
A
답변
4
튜링 기계는 이미 다른 튜링 기계를 구현할 수 있으며 의 규칙을 입력으로 수정 가능한 프로그램으로 변경합니다. 특히 튜링 기계는 계산 가능한 모든 기능을 계산할 수 있습니다. 이론 상으로는 매크로, "자체 수정"코드 등을 가진 lisp 인터프리터를 구현할 수 있습니다.
그래서 대답은 입니다. 기억해라, 아무도, 그리고 절대적으로 아무도 아무도, 이제까지, 실제로, 을 원했다 의심 할 여지없이 시뮬레이터의 zillions가 쓰여지고 있었지만 튜링 기계. (나는 그것을 인정하지 않을 것이다. 그러나 학부생으로서 나는 그런 것을했을지도 모른다. ..) 그것은 중요한 중요한 증거들이 기초를 두는 것일 뿐이다.
1
더 완벽하게 : "Universal Turing Machine"과 "Turing"Machine의 차이점이 있습니다. 일반적인 Turing Machine에는 하드 배선 된 규칙 집합이 있으므로 자체 수정이 불가능합니다. 유니버설 튜링 머신 (Universal Turing Machine)은 I/O 용 테이프와 동일한 테이프에서 규칙 세트를 읽고 해당 룰 세트를 수정할 수있는 기능을 제공합니다. 실제로 이미 자체 수정 중임
+1
누군가 왜 이것이 downvoted 것 알고 있었나요? 나는 내가 잘못한 것으로 여겨지는 것을 듣는 것에 관심이있다. 그러나 코멘트없이 downvoting하는 것은 나에게나 또는 읽는 다른 누군가에게 많은 정보를 제공하지 않는다. – stevegt
고마워. – Bubba88
실제로 TM의 요점을 기억하지 않고 좋은 질문입니다. 전체 존재의 배후에있는 핵심 질문에 대해 질문 할 수있었습니다. – DigitalRoss
나는 그 계산상의 이점이 없다고 거의 확신했다. dification,하지만 귀하의 대답은 크게 명확하게. – Bubba88