튜링 머신 갤러리
Turing machine gallery다음 글은 튜링 기계에 대한 보충물이다.
기계 장치로서의 튜링 기계
여기에 보이는 튜링 기계는 지울 수 있는 특수 종이 테이프와 "수평 표시"로 구성되어 있다.아마도 TABLE은 유사한 "읽기 전용" 종이 테이프 리더로 만들어졌거나, 펀치된 카드를 읽었을 것이다.튜링의 전기 작가 앤드류 호지스(1983)는 어릴 때 튜링이 타자기를 좋아했다고 썼다.힐버트의 의사결정 문제를 해결할 수 있는 기계적인 과정인 "기적의 기계" (Hodges 페이지 98)는 튜링의 선생님 중 한 명인 G. H. Hardy에 의해 제안되었다.그럼에도 불구하고, "그의 기계는 1936년에 존재했던 어떤 것에도 뚜렷한 모델을 가지고 있지 않았는데, 새로운 전기 산업의 일반적인 관점에서 보면, 텔레프린터, 텔레비전 '스캐닝', 그리고 자동 전화 교환 연결을 가지고 있었다.그것은 그 자신의 발명이었다." (호지 페이지 109)
데이비스(2000년)는 튜링이 전자기계 계전기(p. 170)로 2진수 승수를 만들었다고 말한다.알고리즘의 역사 부분에서 언급했듯이, 종이 테이프와 종이 카드를 펀칭하거나 인쇄하는 것은 1930년대에 흔한 일이었다.
볼로스와 제프리(1974년, 1999년)는 "한 주 또는 다른 주에 있는 것은 특정 기어의 톱니바퀴를 가장 위에 두는 문제일 수도 있다"고 지적한다.
궤간을 따라 상자를 끄는 상자 안의 "가난한 머그잔"으로 튜링 기계 사용
- "우리는 이 문제의 기계나 전자제품과는 관계가 없다.아마도 이 사물을 상상하는 가장 간단한 방법은 매우 조잡할 것이다.상자 안에는 읽고 쓰고 지우고 움직이는 모든 것을 하는 남자가 있다.(상자는 바닥이 없다: 불쌍한 머그잔은 그와 함께 상자를 당기면서 넥타이 사이를 걸어다닌다.)남자는 종이에 m 명령 목록을 적어 놓았다.그는 지시번호 i [etc.]"를 수행할 때 상태 상태에 있다(1974, 1999) (Boolos and Jeffrey (1974, 1999) p.21)
이 설명은 에밀 포스트의 "정확한 조합 과정"을 위한 "변환할 수 없는 고정된 명령 집합"을 장착하고 따르는 사람, "공간이나 상자의 무한 순서"를 통해 왼쪽이나 오른쪽으로 이동하는 사람, 그리고 상자 안에서 한 장의 "수직 스트로크"를 종이에 인쇄하거나 지우는 동안(19일 이후)의 "수직 스트로크"에 가깝게 따라 설명된다.36 불해독 페이지 289).Post의 공식은 출판된 첫 번째 유형이었다; 그것은 튜링에 몇 달 차이로 앞서 있었다.
Post, Boolos 및 Jeffrey의 설명 모두 프로세스의 'm-구성'(지침)을 정의하기 위해 5-tuple이 아닌 4-tuple을 사용한다.
로봇은 지시를 수행한다.
이 모델은 스톤(1972년)에 의해 제안되었다.
- "컴퓨터가 명령의 연속이라고 설명할 수 있는 모든 작업을 수행할 로봇이라는 관점을 채택하자."(3페이지)
스톤은 알고리즘에 대한 그의 개념을 발전시키기 위해 로봇을 사용한다.이것은 결국 그를 튜링 기계에 대한 그의 설명과 그의 진술로 이끈다.
- "만약 [처치의 논문]이 사실이라면, 튜링 기계는 얼마나 복잡한지 상관없이 다른 어떤 장치도 수행할 수 있는 모든 계산을 수행할 수 있다는 것이 그 증거에 의해 증명된 것 같다.우리가 선택하는 장치." (13 페이지)
기타 이미지
튜링 머신의 예술적 표현
튜링 머신의 모델
참조
참고문헌은 Turing machine의 주요 기사를 참조하십시오.
