포인터 머신

Pointer machine

이론 컴퓨터 과학에서 포인터 머신은 랜덤 액세스 머신과 유사한 "원자론적" 추상 계산 머신 모델입니다.포인터 알고리즘은 포인터 머신 [1]모델로 제한된 알고리즘입니다.

포인터 머신은 종류에 따라 링크 오토마톤, KU 머신, SMM, 아토믹 LISP 머신, 트리 포인터 머신 등으로 불릴 수 있다(cf Ben-Amram 1995).문헌에는 Kolmogorov-Uspenski 모델(KUM, KU-machine), Knuth 링크 오토마톤 및 Schönhage Storage Modification Machine 모델(SMM)의 세 가지 주요 변종이 있습니다. SMM이 가장 일반적인 것으로 보입니다.

포인터 머신은, 「읽기 전용 테이프」(또는 동등한 테이프)로부터, 적어도 2개의 기호(예를 들면 {0, 1})로 이루어진 입력(바운딩 심볼 시퀀스(「워드」)을 수신해, 출력 심볼 시퀀스를 출력 「쓰기 전용」테이프(또는 동등한 것)에 쓴다.심볼 시퀀스(입력 워드)를 출력 심볼 시퀀스로 변환하기 위해 기계는 유한 상태 기계(메모리 및 명령 목록)인 "프로그램"을 갖추고 있습니다.이 프로그램은 상태 머신을 통해 입력 기호를 읽고 스토리지 구조(예를 들어 { 0, 1 } 기호가 표시된 포인터)에 의해 상호 연결된 "노드"(레지스터) 모음으로 작동하며 출력 테이프에 기호를 씁니다.

포인터 머신은 정상적인 방법으로 계산을 수행할 수 없습니다.계산은 입력 기호를 읽고, 스토리지 구조(노드 및 포인터 패턴)를 수정 및 다양한 테스트를 수행하며, 테스트를 기반으로 기호를 출력하는 방식으로만 진행됩니다."정보"는 스토리지 구조에 있습니다.

포인터 머신의 종류

Gurevich와 Ben-Amram 둘 다 매우 유사한 "추상 기계"의 "원자학적" 모델을 열거하고 있습니다. Ben-Amram은 6개의 "원자학적 모델"이 "고급" 모델과 구별되어야 한다고 생각합니다.이 문서에서는 특히 다음 3가지 원자론적 모델에 대해 설명합니다.

  • Schönhage의 스토리지 변경 머신(SMM),
  • Kolmogorov – Uspenskii 기계(KUM 또는 KU-기계),
  • Knuth의 '링크 오토마톤'

그러나 Ben-Amram은 다음과 같이 덧붙입니다.

  • Atomistic Pure-LISP 머신(APLM)
  • Atomistic Full-LISP Machine(AFLM)
  • 일반적인 원자론적 포인터 기계,
  • Jone's I 언어 (2종류)

포인터 머신 모델의 문제

복잡성 이론에서의 모델 사용: van Emde Boas(1990)는 이러한 추상적 모델의 형태가 다음과 같은 우려를 표명한다.

"흥미로운 이론 모델이지만...복잡성 이론의 기본 모델로서의 그것의 매력은 의심스럽다.이 시간 측정치는 실제 시간 복잡성을 과소평가하는 것으로 알려진 상황에서 균일한 시간을 기반으로 합니다.기계의 공간 측정에도 동일한 관찰이 적용됩니다.(van Emde Boas(1990) 페이지 35)

Gurevich 1988도 우려를 표명합니다.

"개략적으로 말하면, Schönhage 모델은 최신 기술 수준에서 시간 복잡성의 좋은 측정을 제공한다(나는 앵글루인과 발리안트의 랜덤 액세스 컴퓨터 라인을 따라 무언가를 선호한다). (Gurevich (1988) 페이지 6은 "확률론적 알고리즘"에 대한 "Galliantic Algorithms"를 참조한다.컴퓨터 및 시스템 과학 저널 18(1979) 155-193).

§3과 §4 (페이지 494–497)에서 Schönhage 본인은 두 개의 랜덤 액세스 기계 모델 "RAM0"과 "RAM1"의 실시간 동등성을 입증한다는 사실은 복잡성 연구를 위한 SMM의 필요성을 의심하게 만든다.

모델의 잠재적 용도:그러나 Schönhage(1980)는 §6에서 선형 시간에서의 정수 곱셈을 보여준다.그리고 구레비치는 "병렬 KU 기계"가 인간의 뇌를 어느 정도 반영하는지 궁금해한다(구레비치(1988년) 페이지 5).

Schönhage의 스토리지 수정 기계(SMM) 모델

Schönhage의 SMM 모델이 가장 일반적이고 가장 많이 받아들여지는 것으로 보인다.레지스터 머신 모델과 다른 일반적인 계산 모델(테이프 기반 튜링 머신 또는 카운터 [2]머신의 라벨이 붙은 구멍과 구별할 수 없는 조약돌 등)과는 매우 다르다.

컴퓨터는 입력 기호의 고정 알파벳과 알파벳 기호로 표시된 화살표가 있는 가변 방향 그래프(상태 다이어그램이라고도 함)로 구성됩니다.그래프의 각 노드에는 각 기호가 라벨로 표시되어 있는 발신 화살표가 정확히1개 있습니다만, 이들 중 일부는 원래의 노드에 루프백 할 수 있습니다.그래프의 1개의 고정 노드가 시작 노드 또는 "활성" 노드로 식별됩니다.

알파벳 기호의 각 단어는 머신을 통과하는 경로로 변환할 수 있습니다.예를 들어 10011은 시작 노드에서 경로 1을, 그 결과 노드에서 경로 0을, 경로 0을, 경로 1을, 경로 1을, 경로 1을 차례로 택하는 것으로 변환됩니다.경로도 결과 노드로 식별할 수 있지만 계산 중에 그래프가 변경됨에 따라 이 식별이 변경됩니다.

기계는 그래프의 레이아웃을 변경하는 지침을 수신할 수 있습니다.기본 명령어는 문자열 w에 이어 "결과"가 되는 새 노드를 생성하는 new w 명령과 엣지를 다른 노드로 향하는 w-v 명령입니다.여기서 w와 v는 단어를 나타냅니다.v는 이전 단어(즉, 이전에 생성된 기호 문자열)이므로 리다이렉트된 에지가 해당 문자열의 "결과"인 오래된 노드를 가리킵니다.

2-심볼 {0,1} 시스템에서 새 "노드"를 생성하는 단계는 다음과 같습니다.새로운 단어(여기서 "11")에 직면했을 때, 기계는 (i) 새로운 노드 3을 생성하고 적절한 1-에지를 가리킨 다음 (ii) 이전 노드(여기서 "2")를 가리키는 두 개의 새로운 포인터(0-에지" 및 1-에지)를 만드는 것을 책임진다.

(1) new w: 새로운 노드를 만듭니다.w는 새로운 노드를 작성하는 새로운 단어를 나타냅니다.기계는 w라는 단어를 읽고 w의 기호에 의해 나타나는 경로를 따라 마지막 "추가" 기호에 도달합니다.대신 추가 기호를 사용하면 마지막 상태가 새 노드를 만들고 해당 화살표(기호가 표시된 화살표)를 이전 위치에서 새 노드를 가리키도록 "플립"합니다.새 노드는 모든 에지를 이전 마지막 상태로 되돌립니다. 여기서 다른 새 노드 또는 세트에 의해 리디렉션될 때까지 "정지"됩니다.어떤 의미에서 새 노드는 할당을 기다리는 "sleeping" 상태입니다.시작 노드 또는 중앙 노드의 경우에도 마찬가지로 양쪽 가장자리가 자신을 가리키는 것으로 시작합니다.

  • 예: "w"는 10110[1]로 합니다.여기서 마지막 문자는 특수 상태를 나타내는 괄호로 둘러싸여 있습니다.10110에 의해 도달한 노드의 1엣지(5-엣지, 즉 6-노드, 경로의 끝에서)를 새로운 7번째 노드를 포인트 합니다.이 새로운 노드의 2개의 가장자리는 패스의 6번째 노드를 "뒤로" 가리킵니다.

(2) w를 v로 설정: 워드 w로 표시되는 경로에서 워드 v를 나타내는 이전 노드로 에지(화살표)를 리다이렉트(이동)합니다. 다시 리다이렉트되는 경로의 마지막 화살표입니다.

  • 예:1011011 에서1011 로 설정하면, 상기의 명령 후에, 101101 에 있는 새로운 노드의 1 개의 화살표가, 1011 에 도달한 패스의 5 번째 노드를 가리키도록 변경됩니다.따라서 패스 1011011은 1011과 같은 결과가 됩니다.

(3) v = w이면 명령 z : 단어 w와 v로 표현되는 두 경로를 비교하여 같은 노드에서 끝나는지를 확인하는 조건부 명령. 같은 노드일 경우 명령 z로 이동하거나 계속한다.이 명령어는 레지스터 머신 또는 Wang b-machine의 상대 명령어와 동일한 목적을 수행하며, 새로운 상태로 점프하는 튜링 머신의 능력에 대응합니다.

2-심볼 {0,1} 시스템에서 새 "노드"를 생성하는 단계입니다.단어(기호 0과 1의 문자열)가 기계에 들어오면 기계가 그래프를 만듭니다.여기에 나타나 있듯이 5번째 스텝의 두 단어인 "111"과 "10"은 모두 노드 4를 가리킵니다.이때 기계가 if 10=xxxx를 실행한다면 테스트는 성공하고 기계는 xxx로 점프합니다.

Knuth의 '링크 오토마톤' 모델

Schoenhage에 따르면, Knuth는 SMM 모델이 컴퓨터 프로그래밍의 예술(The Art of Computer Programming, cf) 제1권에 간략하게 설명되어 있는 특별한 유형의 "링크 오토마타"와 일치한다고 언급했다.[4, 페이지 462~463]

Kolmogorov-Uspenskii 기계(KU-machine) 모델

KUM은 반전 포인터만 허용하는 점에서 SMM과 다릅니다.노드 x에서 노드 y로의 포인터마다 y에서x까지의 역방향 포인터가 존재해야 합니다.발신 포인터는 알파벳의 구별된 기호로 라벨을 붙여야 하기 때문에 KUM 그래프와 SMM 그래프 모두 O(1) 아웃도입니다.그러나 KUM 포인터의 반전성은 인 도를 O(1)로 제한합니다.이는 위의 반 엠데 보아스의 인용문처럼 (순수하게 정보적인 것과 반대되는) 물리적 사실주의에 대한 몇 가지 우려를 해결한다.

또 다른 차이점은 KUM이 튜링 머신의 일반화로 의도되었기 때문에 현재 "액티브" 노드를 그래프 중심으로 이동할 수 있다는 것입니다.따라서 노드가 단어 대신 개별 문자로 지정될 수 있고, 명령의 고정 리스트가 아닌 상태 테이블에 의해 실행되는 액션을 결정할 수 있다.

「 」를 참조해 주세요.

Register machine: 범용 레지스터 기반의 추상 머신 계산 모델

튜링 머신 - 일반 테이프 기반 추상 머신 계산 모델

  • Post-Turing 머신—최소한의 단테이프, 양방향, 1 기호 {blank, mark } 튜링 유사 머신이지만 기본 3개의 명령 카운터 머신과 유사한 방식으로 기본 순차 명령 실행.

레퍼런스

  1. ^ Cloteaux, Brian; Ranjan, Desh (2006). "Some Separation Results Between Classes of Pointer Algorithms".
  2. ^ 치료법은 예가 없는 Schönhage가 아닌 van Emde Boas 1990이다.

대부분의 참고 자료와 참고 문헌은 기사 등록 기계에서 찾을 수 있습니다.다음은 이 기사에 특화된 내용입니다.

  • Amir Ben-Amram(1995), "포인터 머신"이란 무엇인가?, SIGACTN: SIGACT News(Automata 및 Computability Theory에 관한 ACM Special Interest Group)", 제26권, 1995년도:DIKU, 코펜하겐 대학 컴퓨터 과학부, amirben@diku.dk.여기서 Ben-Amram은 (type 1a) Abstract Machines: (type 1a)Kolmogorov-Uspenski Machine(KUM), Schönhage의 스토리지 수정 머신(SMM), Knuth의 "Linking Automaton", APLM 및 AFLM(Atomistic Pure-LISP 머신) 및 일반 ISP(Atomistic Full-ISP 머신)를 포함한 원자론적 모델고급 모델, (타입 2) 포인터 알고리즘.
  • 안드레이 콜모고로프와 브이 Uspenskii, 알고리즘의 정의에 따르면 Uspekhi Mat.Nauk 13(1958), 3-28.미국 수학회 번역의 영어 번역, 시리즈 II, 제29권(1963), 페이지 217–245.
  • Yuri Gurevich(2000), 순차 추상 상태 기계 캡처 순차 알고리즘, ACM 트랜잭션, 계산 로직, vol.1, no.1, (2000년 7월), 77~111페이지.구레비치는 한 문장에서 Schönhage[1980]의 "스토리지 수정 기계"를 Knuth의 "포인트 기계"와 비교합니다."랜덤 액세스 머신"과 같은 유사한 모델의 경우 Gurevich는 다음을 참조합니다.
  • 유리 구레비치(1988년), 콜모고로프 기계와 관련 문제에 대하여, 유럽이론컴퓨터과학협회 회보, 1988년 6월, 71-82.여기서 사용하는 Schönhage 머신과 Kolmogorov-Uspenski 머신에 대한 통일된 설명을 소개합니다.
  • Arnold Schönhage(1980), 스토리지 수정 기계, 산업 및 응용 수학 협회, SIAM J. Compute.제9권 제3호 1980년 8월여기서 Schönhage는 SMM과 "후계자 RAM"(랜덤 액세스 머신)의 동등성을 나타냅니다.그는 SMM에 대해 소개한 이전 논문을 언급하고 있습니다.
    • Arnold Schönhage(1970), Universelle Turing Speicherung, Automatentheory und Formale Sprachen, Dörr, Hotz, eds.독서자.Institut, Manhheim, 1970, 페이지 69-383.
  • Peter van Emde Boas, 기계 모델 및 시뮬레이션 페이지 3-66에 나오는 내용:
얀 반 리우웬, ed. "이론 컴퓨터 과학 핸드북"A권: 알고리즘과 복잡성, MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2(볼륨 A). QA 76.H279 1990.
SMM에 대한 Van Emde Boas의 치료는 페이지 32-35에 나와 있습니다.이 처리는 Schönhage 1980을 명확히 합니다. Schönhage 처리는 거의 따라오지만 약간 확장됩니다.효과적인 이해를 위해서는 두 가지 참고 자료가 모두 필요할 수 있습니다.