5
a list of Turing machine equivalents이라는 위키 백과 문서를 찾았습니다. 그러나 주어진 기계가 Turing machine equivalent인지 여부를 판별하는 방법에 대해서는 알려주지 않습니다.기계가 튜링 기계와 동일한 지 확인하는 방법
증명을 위해 튜링 기계의 정의를 사용해야합니까? 예를 들어 주시겠습니까?
감사합니다.
A
답변
3
튜링이 완전하다는 것을 증명하는 표준 방법은 시스템에 TM- 등가물 중 하나를 구현하는 것입니다. 그렇게 할 수 있다면, 당신의 기계는 튜링 완료입니다. 그렇지 않다면, 그렇지 않습니다. 따라서 새로운 프로그래밍 언어가 완성되었다는 것을 증명하려고 시도한다면 구현하기 가장 간단한 TM 등가물을 선택한 다음 프로그래밍 언어로 시뮬레이션 할 수 있다는 것을 보여줄 것입니다.
0
내 머리 꼭대기에서 : 귀하의 기계가 Turing machine equivalent machine 중 하나를 시뮬레이션 할 수 있다면 귀하의 기계도 Turing machine equivalent입니다.
아마 이런 식으로 할 수있는 가장 쉬운 방법입니다.
편집 : 나는이 기계가 튜링 기계에 상응하는 것임을 암시하는 것은 아닙니다. 아마도 이론적 인 정보학에 좀 더 숙련 된 사람이 나를 해결할 수 있을까요?
+0
표시하면 당신은 당신의 모델에서 튜링 기계를 시뮬레이션 할 수 있습니다. (당신의 모델은 튜링 기계보다 강력합니다) 동등성에 필요한 다른 의미는 (튜링 기계가 당신의 모델을 시뮬 레이팅 할 수 있습니다) 틀릴 수도 있지만, turing thesis] (https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis)는 두 번째 의미가 항상 참이라고 추측합니다. – Lapinot
1
실제로 실제로 입증 될 수는 없습니다. 적어도 이러한 공통 평등 증명을 공식화하는 것은 이론적 인 컴퓨터 과학에서도 기대되는 것보다 훨씬 공식적인 논리를 요구할 수 있습니다. (당신이 동의하지 않는다면, 이것에 대해 열렬히 토론하겠습니다.)
그러나 이것은 대부분 문맥에서 분명합니다. 당신은 계산 B의 또 다른 모델 내에서 계산 A 체계의 "기계"의 시뮬레이션을 만들려고합니다. 이것은 B가 A를 시뮬레이트 할 수 있고 따라서 A의 전체 힘을 가짐을 의미합니다. 반대의 경우,이 두 모델은 동등한.
이 질문을 확인하십시오. http://stackoverflow.com/questions/2550888/what-is-the-relationship-between-turing-machine-modern-computer – Cratylus
이것은 cstheory.stackexchange.com에 속한다고 생각합니다. – MSalters