포인터 머신

이론 컴퓨터 과학에서 포인터 머신(pointer machine)은 저장 구조가 그래프인 추상 계산 기계이다. 포인터 알고리즘은 포인터 머신 모델에 제한된 알고리즘일 수도 있다.

포인터 머신의 특정 유형은 연결 오토마톤, KU-머신, SMM, 원자론적 LISP 머신, 트리-포인터 머신 등으로 불린다.아미르 벤-암람 (1995). What is a "Pointer machine"?, SIGACT News (ACM Special Interest Group on Automata and Computability Theory), volume 26, 1995.

포인터 머신에는 산술 명령어가 없다. 계산은 입력 심볼을 읽고, 저장 구조(노드와 포인터의 패턴)를 수정하고 다양한 테스트를 수행하며, 테스트를 기반으로 심볼을 출력함으로써 진행된다. 이러한 점에서 이 모델은 튜링 기계와 유사하다.

 "포인터 머신"의 유형 

구레비치와 벤-암람 모두 여러 가지 매우 유사한 "추상 기계"의 "원자론적" 모델을 나열한다.유리 구레비치 (2000), Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, vol. 1, no. 1, (July 2000), pages 77–111. 벤-암람은 "원자론적 모델"이 "고수준" 모델과 구별되어야 한다고 믿는다. 다음 원자론적 모델이 아래에 제시될 것이다.

 쇤하게의 저장 수정 기계(SMM),아놀드 쇤하게 (1980), Storage Modification Machines, SIAM Journal on Computing Vol. 9, No. 3, August 1980.
 콜모고로프-우스펜스키 기계(KUM 또는 KU-Machines).안드레이 콜모고로프와 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.

벤-암람은 또한 이 문서에서 더 이상 논의되지 않는 다음 변형들을 제시한다.
 원자론적 순수-LISP 머신(APLM)
 원자론적 전체-LISP 머신(AFLM),
 일반 원자론적 포인터 머신,
 존의 I 언어(두 가지 유형).

 쇤하게의 저장 수정 기계(SMM) 모델 
다음 설명은 반 엠데 보아스에 따른다.피터 반 엠데 보아스, Machine Models and Simulations pp. 3–66 in: 얀 반 레우웬, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990.  (volume A).

이 기계는 고정된 입력 심볼 알파벳, 고정된 프로그램, 그리고 알파벳 심볼로 레이블이 지정된 화살표가 있는 가변적인 유향 그래프로 구성된다. 이 그래프가 기계의 저장소이다. 그래프의 각 노드는 각 심볼로 레이블이 지정된 정확히 하나의 바깥쪽 화살표를 가지지만, 이들 중 일부는 원래 노드로 되돌아갈 수 있다. 그래프의 한 고정된 노드는 시작 또는 "활성" 노드로 식별된다.

알파벳의 각 심볼 단어는 기계를 통한 경로로 변환될 수 있다. 예를 들어, 10011은 시작 노드에서 1번 에지를 취하고, 결과 노드에서 0번 에지를 취하고, 그 다음 0번 에지, 그 다음 1번 에지, 그 다음 1번 에지를 취하는 것으로 변환된다. 따라서 단어는 경로의 최종 노드인 노드를 식별하지만, 이 식별은 계산 중에 그래프가 변경됨에 따라 달라진다.

기계는 그래프의 레이아웃을 변경하는 명령을 받을 수 있다. 기본 명령은 다음과 같다.

(1) '새 w 명령어: 경로 w의 끝에 새 노드를 생성하며, 모든 에지는 w에서 끝에서 두 번째 노드를 가리킨다.

(2) w를 v로 설정 명령어: 에지를 다른 노드로 (재)지정한다. 여기서 w와 v는 단어를 나타낸다. 이 명령어는 경로 w의 마지막 에지의 대상을 변경한다.


(3) 만약 v = w 이면 명령어 z: 단어 w와 v로 표현된 두 경로가 같은 노드에서 끝나는지 비교하는 조건부 명령어이다. 같으면 명령어 z로 점프하고, 그렇지 않으면 계속 진행한다. 이 명령어는 모든 명령형 프로그래밍 언어의 if 명령과 동일한 목적을 수행한다.


(4) 입력/출력을 위한 읽기 및 쓰기 명령어: 읽기 전용 입력 테이프와 쓰기 전용 출력 테이프에 접근하며, 둘 다 알파벳의 심볼을 포함한다.

커누스는 SMM 모델이 컴퓨터 프로그래밍의 예술 1권에서 간략하게 설명된 "연결 오토마톤"의 한 유형과 일치한다고 언급했다.

 콜모고로프-우스펜스키 기계 (KU-머신) 모델 

KUM은 SMM과 달리 역방향 포인터만 허용한다. 즉, 노드 x에서 노드 y로 가는 모든 포인터에 대해 y에서 x로 가는 역방향 포인터가 동일한 심볼로 레이블링되어 있어야 한다. 즉, 저장 그래프는 무방향이다. 나가는 포인터는 알파벳의 서로 다른 심볼로 레이블링되어야 하므로, KUM과 SMM 그래프는 모두 O(1)의 외부 차수를 갖는다. 그러나 KUM 포인터의 가역성은 내부 차수 또한 O(1)로 제한한다. 이는 물리적 현실성(순전히 정보적인 것과 반대되는)에 대한 일부 우려를 해소한다.

모델 간에는 프로그램의 형태(명령어 목록 대신 상태 테이블)와 같은 다른 사소한 차이점도 있다.

 포인터 머신 모델에 대한 고려 사항 복잡성 이론에서의 모델 사용:
반 엠데 보아스 (1990)는 이러한 형태의 추상 모델에 대해 다음과 같은 우려를 표명한다.
"흥미로운 이론적 모델이지만, ... 복잡성 이론의 근본 모델로서의 매력은 의문이다. 그 시간 측정은 이 측정이 실제 시간 복잡성을 과소평가하는 것으로 알려진 맥락에서 균일한 시간에 기반을 둔다. 동일한 관찰이 기계의 공간 측정에도 적용된다" (반 엠데 보아스 (1990) p. 35)

구레비치도 우려를 표명한다.
"실용적으로 말해서, 쇤하게 모델은 현재 기술 수준에서 시간 복잡성을 잘 측정한다 (저는 앵글루인과 발리언트의 랜덤 접근 컴퓨터와 비슷한 것을 선호하겠지만)."구레비치 (1988) p. 6, 앵글루인 D.와 발리언트 L. G.의 "Hamiltonian Circuits and Matchings를 위한 빠른 확률적 알고리즘", Journal of Computer and System Sciences 18 (1979) 155-193. 참조.

쇤하게는 SMM과 랜덤 접근 기계의 두 가지 유형의 실시간 등가성을 입증한다.SMM 모델의 알고리즘: 쇤하게는 SMM이 선형 시간에 정수 곱셈을 수행할 수 있음을 입증한다.모델의 잠재적 용도: 구레비치는 병렬 KU 머신이 "인간 뇌와 다소 유사한지" 여부에 대해 궁금해한다.유리 구레비치 (1988), 콜모고로프 머신과 관련 문제에 관하여, "컴퓨터 과학의 논리" 칼럼, 유럽 이론 컴퓨터 과학 협회 회보, 35호, 1988년 6월, 71-82.병렬 컴퓨팅': 위에 언급된 모든 모델은 순차적이다. 병렬 (원자론적) 포인터 머신 모델은 쿡과 다이몬드가 제안했다. 고수준 (비원자론적) 병렬 포인터 머신 모델도 사용되었다.

 같이 보기 
레지스터 머신—일반적인 레지스터 기반 추상 기계 계산 모델
 카운터 머신—가장 원시적인 기계, 기본 모델의 명령어 집합은 레지스터 머신 클래스 전체에서 사용된다.
 랜덤 접근 기계—RAM: 간접 주소 지정 기능이 추가된 카운터 머신
 랜덤 접근 저장 프로그램 기계—RASP: 범용 튜링 기계 방식, 즉 폰 노이만 구조 방식으로 레지스터 자체에 "명령어 프로그램"이 있는 카운터 기반 또는 RAM 기반 기계.
튜링 기계—일반적인 테이프 기반 추상 기계 계산 모델
 포스트-튜링 기계—최소한의 단일 테이프, 양방향, 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] "저장 수정 기계"를 커누스의 "포인터 기계"와 한 문장으로 비교한다. "랜덤 접근 기계"와 같은 더 유사한 모델에 대해서는 구레비치가 다음을 참조한다.
 존 E. 새비지 (1998), Models of Computation: Exploring the Power of Computing. Addison Wesley Longman.
 유리 구레비치 (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.  (volume A).
반 엠데 보아스의 SMM 다루기는 32-35쪽에 나타난다. 이 다루기는 쇤하게 1980을 명확히 한다. — 쇤하게의 다루기를 밀접하게 따르지만 약간 확장한다. 효과적인 이해를 위해서는 두 참조가 모두 필요할 수 있다.

 각주 

분류:레지스터 머신