이 기계는 고정된 입력 심볼 알파벳, 고정된 프로그램, 그리고 알파벳 심볼로 레이블이 지정된 화살표가 있는 가변적인 유향 그래프로 구성된다. 이 그래프가 기계의 저장소이다. 그래프의 각 노드는 각 심볼로 레이블이 지정된 정확히 하나의 바깥쪽 화살표를 가지지만, 이들 중 일부는 원래 노드로 되돌아갈 수 있다. 그래프의 한 고정된 노드는 시작 또는 "활성" 노드로 식별된다.
알파벳의 각 심볼 단어는 기계를 통한 경로로 변환될 수 있다. 예를 들어, 10011은 시작 노드에서 1번 에지를 취하고, 결과 노드에서 0번 에지를 취하고, 그 다음 0번 에지, 그 다음 1번 에지, 그 다음 1번 에지를 취하는 것으로 변환된다. 따라서 단어는 경로의 최종 노드인 노드를 식별하지만, 이 식별은 계산 중에 그래프가 변경됨에 따라 달라진다.
기계는 그래프의 레이아웃을 변경하는 명령을 받을 수 있다. 기본 명령은 다음과 같다.
(1) 새 w 명령어: 경로 w의 끝에 새 노드를 생성하며, 모든 에지는 w에서 끝에서 두 번째 노드를 가리킨다.
(2) w를 v로 설정 명령어: 에지를 다른 노드로 (재)지정한다. 여기서 w와 v는 단어를 나타낸다. 이 명령어는 경로 w의 마지막 에지의 대상을 변경한다.
2-심볼 {0,1} 기계의 명령어 실행 단계: (1) 새 ε; (2) 새 1; (3) 새 11. 명령어 #1은 저장 그래프를 단일 노드, 노드 1로 초기화한다.
(3) 만약v = w이면 명령어 z: 단어 w와 v로 표현된 두 경로가 같은 노드에서 끝나는지 비교하는 조건부 명령어이다. 같으면 명령어 z로 점프하고, 그렇지 않으면 계속 진행한다. 이 명령어는 모든 명령형 프로그래밍 언어의 if 명령과 동일한 목적을 수행한다.
2-심볼 {0,1} 기계에서 저장 그래프의 진화: (1) 새 ε; (2) 새 1; (3) 새 11; (4) 새 10; (5) 111을 10으로 설정. 이 시점에서 기계가 if 10=111 then xxx를 수행한다면, 테스트는 성공하고 기계는 실제로 xxx로 점프할 것이다.
(4) 입력/출력을 위한 읽기 및 쓰기 명령어: 읽기 전용 입력 테이프와 쓰기 전용 출력 테이프에 접근하며, 둘 다 알파벳의 심볼을 포함한다.
KUM은 SMM과 달리 역방향 포인터만 허용한다. 즉, 노드 x에서 노드 y로 가는 모든 포인터에 대해 y에서 x로 가는 역방향 포인터가 동일한 심볼로 레이블링되어 있어야 한다. 즉, 저장 그래프는 무방향이다. 나가는 포인터는 알파벳의 서로 다른 심볼로 레이블링되어야 하므로, KUM과 SMM 그래프는 모두 O(1)의 외부 차수를 갖는다. 그러나 KUM 포인터의 가역성은 내부 차수 또한 O(1)로 제한한다. 이는 물리적 현실성(순전히 정보적인 것과 반대되는)에 대한 일부 우려를 해소한다.
모델 간에는 프로그램의 형태(명령어 목록 대신 상태 테이블)와 같은 다른 사소한 차이점도 있다.
포인터 머신 모델에 대한 고려 사항
복잡성 이론에서의 모델 사용:
반 엠데 보아스 (1990)는 이러한 형태의 추상 모델에 대해 다음과 같은 우려를 표명한다.
"흥미로운 이론적 모델이지만, ... 복잡성 이론의 근본 모델로서의 매력은 의문이다. 그 시간 측정은 이 측정이 실제 시간 복잡성을 과소평가하는 것으로 알려진 맥락에서 균일한 시간에 기반을 둔다. 동일한 관찰이 기계의 공간 측정에도 적용된다" (반 엠데 보아스 (1990) p. 35)
구레비치도 우려를 표명한다.
"실용적으로 말해서, 쇤하게 모델은 현재 기술 수준에서 시간 복잡성을 잘 측정한다 (저는 앵글루인과 발리언트의 랜덤 접근 컴퓨터와 비슷한 것을 선호하겠지만)."[7]
포스트-튜링 기계—최소한의 단일 테이프, 양방향, 1 심볼 {공백, 표시} 튜링 유사 기계이지만, 기본 3-명령 카운터 머신과 유사한 방식으로 기본 순차적 명령어 실행을 갖는다.
더 읽어보기
대부분의 참조 및 참고 문헌은 레지스터 머신 문서에서 찾을 수 있다. 다음은 이 문서에 특히 해당한다.
아미르 벤-암람 (1995), What is a "Pointer machine"?, SIGACT News (ACM Special Interest Group on Automata and Computability Theory)", volume 26, 1995. 벤-암람은 유형과 하위 유형을 설명한다: (유형 1a) 추상 기계: 콜모고로프-우스펜스키 기계(KUM), 쇤하게의 저장 수정 기계(SMM), 커누스의 "연결 오토마톤", APLM 및 AFLM (원자론적 순수-LISP 기계) 및 (원자론적 전체-LISP 기계), 일반 원자론적 포인터 기계, 존의 I 언어를 포함한 원자론적 모델; (유형 1b) 추상 기계: 고수준 모델, (유형 2) 포인터 알고리즘.
유리 구레비치 (2000), Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, vol. 1, no. 1, (July 2000), pages 77–111. 구레비치는 쇤하게 [1980] "저장 수정 기계"를 커누스의 "포인터 기계"와 한 문장으로 비교한다. "랜덤 접근 기계"와 같은 더 유사한 모델에 대해서는 구레비치가 다음을 참조한다.
유리 구레비치 (1988), 콜모고로프 머신과 관련 문제에 관하여, "컴퓨터 과학의 논리" 칼럼, 유럽 이론 컴퓨터 과학 협회 회보, 35호, 1988년 6월, 71-82. 여기서 사용된 쇤하게와 콜모고로프-우스펜스키 기계의 통합 설명을 소개했다.
아놀드 쇤하게 (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. 쇤하게는 자신의 SMM이 "후계자 RAM"(랜덤 접근 기계) 등과 등가임을 보여준다. 그는 SMM을 소개한 이전 논문을 참조한다.
아놀드 쇤하게 (1970), Universelle Turing Speicherung, Automatentheorie und Formale Sprachen, Dörr, Hotz, eds. Bibliogr. Institut, Mannheim, 1970, pp. 69–383.
피터 반 엠데 보아스, Machine Models and Simulations pp. 3–66, 다음 책에 수록:
얀 반 레우웬, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. ISBN0-444-88071-2 (volume A).
반 엠데 보아스의 SMM 다루기는 32-35쪽에 나타난다. 이 다루기는 쇤하게 1980을 명확히 한다. — 쇤하게의 다루기를 밀접하게 따르지만 약간 확장한다. 효과적인 이해를 위해서는 두 참조가 모두 필요할 수 있다.
↑ 가나다라아놀드 쇤하게 (1980), Storage Modification Machines, SIAM Journal on Computing Vol. 9, No. 3, August 1980.
↑안드레이 콜모고로프와 V. 우스펜스키, On the definition of an algorithm, Uspekhi Mat. Nauk 13 (1958), 3-28. English translation in American Mathematical Society Translations, Series II, Volume 29 (1963), pp. 217–245.
↑피터 반 엠데 보아스, Machine Models and Simulations pp. 3–66 in: 얀 반 레우웬, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. ISBN0-444-88071-2 (volume A).
↑구레비치 (1988) p. 6, 앵글루인 D.와 발리언트 L. G.의 "Hamiltonian Circuits and Matchings를 위한 빠른 확률적 알고리즘", Journal of Computer and System Sciences 18 (1979) 155-193. 참조.
↑Cook, Stephen A.; Dymond, Patrick W. (March 1993). 《Parallel pointer machines》. 《Computational Complexity》 3. 19–30쪽. doi:10.1007/BF01200405.
↑Goodrich, M. T.; Kosaraju, S. R. (1996). 《Sorting on a parallel pointer machine with applications to set expression evaluation》. 《Journal of the ACM》 43. 331–361쪽. doi:10.1145/226643.226670.
