튜링 머신의 예
Turing machine examples| 튜링 머신 |
|---|
| 기계 |
| 변형 |
| 과학 |
다음은 튜링 기계 기사를 보충하기 위한 예들이다.
튜링의 첫 번째 예
다음 표는 튜링의 첫 번째 예(Alan Turing 1937)이다.
- "1. 기계는 시퀀스 0 1 0 1 0 1을 계산하기 위해 구성될 수 있다. (0 < 공란> 1 < 공란> 0...) (결정할 수 없는 p 119)
| 배열 | 행동 | ||
|---|---|---|---|
| m-ray (주) | 테이프 기호 | 테이프 작업 | 최종 m-구성 (주) |
| b | 공란으로 하다 | P0, R | c |
| c | 공란으로 하다 | R | e |
| e | 공란으로 하다 | P1, R | f |
| f | 공란으로 하다 | R | b |
기계가 실제로 어떤 행동을 하는지와 관련하여, 튜링(1936) (미결정 가능 페이지 121)은 다음과 같이 기술하고 있다.
- "이 [예] 표(및 같은 종류의 모든 후속 표)는 처음 두 열에 기술된 구성에 대해 세 번째 열의 조작이 연속적으로 수행되고 그 후 기계가 최종 열의 m-구성 속으로 넘어가도록 이해되어야 한다."(미확정 페이지 121)
그는 위의 표를 "b"(미결정 가능 페이지 120)라는 단일 지시로 축소할 때 이 점을 매우 분명히 하지만, 그의 지시사항은 3행으로 구성되어 있다.명령 "b"에는 세 가지 다른 기호 가능성이 있다. {없음, 0, 1.각각의 가능성은 우리가 가장 오른쪽 열에 도착할 때까지 일련의 조치를 따른다. 여기서 최종 m- 구성은 "b"이다.
| 현재 m-구성(인스트레이션) | 테이프 기호 | 테이프 작업 | 최종 m-구성(인스트레이션) |
|---|---|---|---|
| b | 없음 | P0 | b |
| b | 0 | R, R, P1 | b |
| b | 1 | R, R, P0 | b |
튜링(1937) 본인을 포함한 다수의 논평가들이 관찰한 바와 같이(예: 포스트(1936), 포스트(1947), 클레네(1952), 왕(1954) 튜링 지침은 원자적이지 않다. 따라서 모델의 계산 능력을 줄이지 않고도 모델의 추가적인 단순화를 할 수 있다. 자세한 내용은 포스트 튜링 기기에서 참조한다.
Turing 기계에 기술된 바와 같이, Turing은 단 한 번의 인쇄/삭제 후에 단 한 번의 테이프 이동 L/R/N을 허용함으로써 그의 테이블을 더욱 원자화할 것을 제안했다. Turing은 우리에게 변환된 첫 번째 작은 테이블의 예를 제시한다(미결정 가능, 페이지 127).
| 현재 m-구성(튜링 상태) | 테이프 기호 | 인쇄 작업 | 테이프-모션 | 최종 m-구성(튜링 상태) |
|---|---|---|---|---|
| q1 | 공란으로 하다 | P0 | R | q2 |
| q2 | 공란으로 하다 | P blank, 즉 E | R | q3 |
| q3 | 공란으로 하다 | P1 | R | q4 |
| q4 | 공란으로 하다 | P blank, 즉 E | R | q1 |
튜링의 성명은 여전히 5개의 핵작전을 암시하고 있다.지정된 지침(m-configuration)에 따라 기계:
- 머리 밑의 테잎을 관찰하다.
- 관찰된 기호에 따라 적절한 지침으로 이동하여 사용
- 기호 S를j 인쇄하거나 지우거나 아무 것도 하지 않음
- 테이프를 왼쪽, 오른쪽 또는 전혀 이동하지 않음
- 그 기호에 대한 마지막 m-m-mages로 간다.
튜링 기계의 동작은 원자력이 아니기 때문에, 기계의 시뮬레이션은 각각의 5-튜플을 일련의 더 간단한 동작으로 원자화해야 한다.그의 기계의 "행동"의 다음 예에서 사용되는 한 가지 가능성은 다음과 같다.
- (qi) 머리 아래 테이프 심볼 테스트:기호가 S인0i 경우 Q.01로 가고, 기호 S가1 Q.11로i 가고, 기호 S가2 Q.21i 등으로 간다.
- (qi.01) 기호 S0을j 인쇄하거나 지우거나 아무 것도 하지 않고 Qi.02로 이동
- (qi.02) 테이프를 왼쪽 또는 오른쪽 또는 전혀 이동하지 않고 qm0으로 이동
- (qi.11) 기호 S1을j 인쇄하거나 지우거나 아무 것도 하지 않고 Qi.12로 이동
- (qi.12) 테이프를 왼쪽 또는 오른쪽 또는 전혀 이동하지 않고 qm1로 이동
- (qi.21) 기호 S2를j 인쇄하거나 지우거나 아무것도 하지 않고 Qi.22로 이동
- (qi.22) 테이프를 왼쪽 또는 오른쪽 또는 전혀 이동하지 않고 qm2로 이동
- (etc — 모든 기호를 설명해야 함)
소위 "수평적" 유한 상태 기계는 "병렬적으로" 기호 테스트를 한다. 마이크로프로그래밍에서 더 많은 것을 보라.
기계가 하는 일의 다음 예에서 우리는 튜링의 모델의 몇 가지 특수성에 주목하게 될 것이다.
- "그 수치들을 대체 정사각형에만 쓰는 관습은 매우 유용하다.나는 항상 그것을 이용할 것이다.(결정할 수 없는 페이지 121)
따라서 인쇄할 때 그는 다른 사각형을 모두 생략한다.인쇄된 정사각형은 F-제곱이라고 불린다. 그 사이의 빈 정사각형은 "마커"에 사용될 수 있으며 "삭제하기 쉬운"에서와 같이 "E-제곱"이라고 불린다.차례로 F-제곱은 그의 "그림 사각형"이며, 그가 "그림"이라고 불렀던 기호 1 또는 0만 표시된다.
이 예에서 테이프는 "빈칸"으로 시작하고, 그 위에 "그림"이 인쇄된다.간결성을 위해 TABLE 상태만 여기에 표시된다.
모든 중간 테이프 인쇄 및 이동과 동일한 "실행"이 여기에 표시된다.
표를 자세히 보면 튜링의 예와 관련된 특정한 문제들이 드러난다. 모든 상징들이 설명되는 것은 아니다.
예를 들어, 그의 테이프가 처음에 비어 있지 않았다고 가정해 보자.무슨 일이 일어날까?튜링 기계는 의도된 값과 다른 값을 읽을 것이다.
복사 서브루틴
이것은 "다중" 루틴에서 사용되는 매우 중요한 서브루틴이다.
튜링 기계 예제는 0과 1의 문자열을 처리하며, 0은 빈 기호로 표시된다.그 사이에 0을 적어 테이프에서 마주치는 1의 시리즈를 두 배로 늘리는 것이 과제다.예를 들어, 머리가 "111"이라고 읽으면 "111"이라고 쓰여진다.출력은 "1110111"이 될 것이다.
그 임무를 완수하기 위해서는 이 튜링 시스템은 {s1, s2, s3, s4, s5}라고 불리는 5개의 작동 상태만 필요로 할 것이다.각 상태는 다음과 같은 4가지 조치를 취한다.
- 머리 아래에 있는 기호 읽기
- 시/도에서 결정한 출력 기호
- 주에서 결정한 테이프를 왼쪽 또는 오른쪽으로 이동
- 현재 상태로 결정된 다음 상태로 전환
16개의 기계 구성을 통한 기계 시퀀스의 "실행" (일명 튜링 상태):
이 기계의 행동은 루프로:s1에, 0와 첫번째 1대체하면, 다시 오른쪽으로 움직이게 하는 것 1초에 줄넘기 s2을 사용하고 첫번째 0.s3 다음 1초(처음에는 아무것도 없)의 다음 순서를 극복하고 첫번째 0이 1과를 찾는다 대체한 거르s4 다시 왼쪽으로 움직일 때, 1초 불행에 줄넘기를 직면한 시작을 설명할 수 있다.참깨0을 찾아 s로55 전환한 다음 s에1 의해 원래 쓰여진 0을 찾을 때까지 1초를 건너뛰고 왼쪽으로 이동한다.
0을 1로 대체하고, 한 위치를 오른쪽으로 이동한 다음, 또 다른 루프를 위해 s를1 다시 입력한다.
이는 기계가1 정지할 때 s가 0(이것은 1초의 두 문자열 가운데 0)을 찾을 때까지 계속된다.
대체 설명
또 다른 설명은 문제를 "1"개가 얼마나 있는지 추적하는 방법으로 본다.가능한 각 숫자에 대해 하나의 상태(0,1,2,3,4,5,6 등)를 사용할 수 없다. 그러면 우리는 모든 자연 숫자를 나타내기 위해 무한한 상태가 필요하며 상태 기계는 유한하기 때문이다. 어떤 식으로든 테이프를 사용하여 이 상태를 추적해야 할 것이다.
기본적인 작동 방식은 각 "1"을 반대쪽으로 복사하고 앞뒤로 움직여서 - 여행의 어느 부분에 있는지 기억할 수 있을 만큼 충분히 똑똑하다.좀 더 자세히 설명하자면, 그것은 각각의 "1"을 반대쪽으로 가로질러 운반하고, 중간에 분리되는 "0"을 인식하고, 다른 쪽에 있는 "0"을 인식하여 그것이 종말에 이르렀음을 알 수 있다.같은 방법을 사용하여 되돌아와서 중간 "0"을 검출하고, 그 다음 원래 면의 "0"을 검출한다.원면의 이 '0'은 어떻게 1의 숫자를 추적하는지 퍼즐의 열쇠다.
비결은 "1"을 옮기기 전에 "0"으로 대체하여 그 숫자를 "테이큰"으로 표시하는 것이다.그것이 돌아오면, 그것은 그 "0"을 다시 "1"로 채우고, 다음 "0"으로 표시하고, 그 "1"을 가로지르는 등의 순환을 반복한다.각 주행에서 마커 "0"은 중앙으로 한 걸음 더 가까이 이동한다.이것이 그것이 얼마나 많은 "1"을 가로챘는지 추적하는 방법이다.
그것이 돌아오면, 마커 "0"은 그것에 대한 "1"의 컬렉션의 끝처럼 보인다. - 이미 가로지른 "1"은 ("0"의 반대편에) 보이지 않기 때문에, 마치 수학 유도에 의한 증거와 유사한 (N-1)의 1"의 숫자에 대해 작업하고 있는 것처럼 보인다.
중간 "운동"의 결과를 보여주는 전체 "실행".더 잘 보려면 이미지를 클릭한 다음 고해상도 다운로드를 클릭하십시오.
3주 통화량이 많은 비버
다음의 튜링 지침표는 피터슨(1988) 페이지 198, 그림 7.15에서 도출되었다.피터슨이 머리를 움직인다. 다음 모델에서는 테이프가 움직인다.
| 테이프 기호 | 현재 상태 A | 현재 상태 B | 현재 상태 C | ||||||
|---|---|---|---|---|---|---|---|---|---|
| 쓰기 기호 | 테이프 이동 | 다음 상태 | 쓰기 기호 | 테이프 이동 | 다음 상태 | 쓰기 기호 | 테이프 이동 | 다음 상태 | |
| 0 | 1 | R | B | 1 | L | A | 1 | L | B |
| 1 | 1 | L | C | 1 | R | B | 1 | N | STOP |
3 state business 비버의 "state" 도면은 실제로 "state"를 수행하는 데 필요한 이벤트의 내부 시퀀스를 보여준다.Turing(1937년) 위에서 언급한 바와 같이, 이것은 지시사항을 설명하는 5개의 튜플에 대한 적절한 해석이라는 것을 완전히 명확히 한다(미결정 불가, 페이지 119).튜링 5-tule의 분무에 대한 자세한 내용은 포스트-튜링 머신을 참조하십시오.
다음 표는 "압축된" 실행(Turing 상태만 해당)을 보여준다.
바쁜 3주 비버의 풀 「런닝」.결과 튜링 상태(Turing이 "m-configurements" - "machine-configures"라고 부른 것)는 A열 및 기계의 지침(컬럼ns AF-AU)에서도 회색으로 강조 표시된다.
참조
전체 참조는 튜링 시스템을 참조하십시오.
- Ivars Peterson, 1988, The Matheical Tourer: 현대 수학의 스냅숏, W. H. Freeman and Company, New York, ISBN0-7167-2064-7(pbk).튜링 기계는 페이지 194ff에 설명되어 있으며, 바쁜 비버의 예는 198페이지의 그림 7.15에 나와 있다.
- 마틴 데이비스 편집자, 1965년, 불해독성: 불해독성 제안, 불해독성 문제 및 계산 가능한 기능에 대한 기본 논문, 레이븐 프레스, 뉴욕, ISBN, 카드 카탈로그 번호 없음.
- 1937년, 앨런 튜링, On Computable Numbers, Entscheidungsprobroblem, 페이지 116f, 데이비스의 간략한 논평 115페이지.
- Alan Turing, 1937년 Entscheidungsproroblem에 응용한 On Computable Numbers. A 수정 페이지 152-154.