카운터 머신

Counter machine

카운터 머신은 형식 논리 및 이론 컴퓨터 과학에서 계산을 모델링하기 위해 사용되는 추상 기계입니다.이것은 네 가지 유형의 레지스터 기계 중 가장 원시적입니다.카운터 머신은 각각이 하나의 음이 아닌 정수를 유지할 수 있는 하나 이상의 무제한 레지스터 세트와 기계가 따라야 할 (통상 순차적) 연산 및 제어 명령 목록을 포함한다.카운터 머신은 일반적으로 상호 배타 원리와 관련하여 병렬 알고리즘을 설계하는 과정에서 사용됩니다.이 방법으로 사용할 경우 카운터 머신은 메모리 액세스와 관련된 계산 시스템의 이산 시간 단계를 모델링하는 데 사용됩니다.각 연산 스텝에 대한 메모리 액세스에 관한 연산을 모델링함으로써 병렬 알고리즘은 동일한 메모리 주소에 대한 2개 이상의 스레드에 의한 동시 쓰기 동작을 인터록하는 것을 회피하도록 설계할 수 있다.

기본 기능

주어진 카운터 머신 모델의 경우 명령 집합은 1개부터 6개 또는 7개까지 매우 작습니다.대부분의 모델은 몇 가지 산술 연산과 하나 이상의 조건부 연산을 포함합니다(조건이 참이면 점프).다음 컬렉션에서 각각 세 가지 명령을 사용하여 세 가지 기본 모델을 추출합니다.(약어는 임의입니다).

  • CLR(r): CLEAR 레지스터 r. (r을 0으로 설정)
  • INC(r): 레지스터 r의 내용을 변경합니다.
  • DEC(r): 레지스터 r의 내용을 디크리먼트 한다.
  • CPY(rj, rk): 레지스터j r의 내용을 CoPY하여 r의 내용을j 그대로 두고 레지스터k r을 등록한다.
  • JZ(r, z): 레지스터 r에 Zero THEN Jump to instruction z(지시 z로 점프)가 포함되어 있으면 순서대로 계속 진행합니다.
  • JE(rj, rk, z): 레지스터j r의 내용이 레지스터k r의 내용과 같으면 명령 z ELSE로 점프합니다.

또한 보통 머신에는 HALT 명령이 있어 머신을 정지합니다(보통 결과가 계산된 후).

위에서 설명한 지침을 사용하여 다양한 저자가 특정 카운터 머신에 대해 설명했습니다.

  • 세트 1: { INC(r), DEC(r), JZ(r, z) }, (Minsky(1961, 1967), Lambek(1961)
  • 세트 2: {CLR(r), INC(r), JE(rj, rk, z)}, (Eshov(1958), Peter(1958)(1964); Minsky(1967); Schönhage(1980)
  • 세트 3: { INC(r), CPY(rj, rk), JE(rj, rk, z)}, (Elgot-Robinson(1964), Minsky(1967)

한 모델의 명령이 다른 모델의 명령에서 파생될 수 있기 때문에 세 개의 카운터 기계 기반 모델은 동일한 계산 능력을 갖습니다.모두 튜링 기계의 계산 능력과 동등합니다.단항 처리 스타일 때문에 카운터 머신은 일반적으로 동등한 튜링 머신보다 기하급수적으로 느립니다.

대체 이름, 대체 모형

주요 기사:카운터 머신 모델

카운터머신 모델에는 그 특성에 따라 구분할 수 있는 여러 가지 다른 이름이 있습니다.다음 명령어 "JZDEC ( r )"는 레지스터 r이 비어 있는지 여부를 테스트하는 복합 명령어입니다.그렇다면 명령어z I로 건너뛰고 그렇지 않으면 r의 내용을 DECrement합니다.

  • 셰퍼드슨-스터기스 기계, 왜냐하면 이 저자들이 쉽게 접근할 수 있는 설명에서 그들의 모델을 공식적으로 언급했기 때문이다(1963년).추가 편의 지침으로 증강된 명령어 세트 (1)을 사용합니다(JNZ는 "Jump if Not Zero, JZ 대신 사용됨):
    { INC ( r ) 、 DEC ( r ) 、 CLR ( r ) 、 CPY ( rj , rk ) 、 JNZ ( r , z ) }
  • Minsky 기계, 왜냐하면 Marvin Minsky(1961)가 모델을 공식화했기 때문이다.보통 명령어 세트(1)를 사용하지만 명령어 실행은 기본 시퀀셜이 아니기 때문에 추가 파라미터 'z'는 INC 이후의 다음 명령어와 JZDEC의 대체 명령으로 지정됩니다.
    { INC ( r , z ) , JZDEC ( r , ztruefalse ) }
  • 프로그램 기계, 프로그램 컴퓨터, 민스키(1967)라는 이름이 모델에 붙여진 이유는 컴퓨터처럼 조건부 점프가 성공하지 않는 한 명령이 순차적으로 진행되기 때문입니다.(일반적으로) 명령 집합 (1)을 사용하지만 Shepherson-Sturgis 모델과 유사하게 증강될 수 있습니다.JZDEC는 종종 분할됩니다.
    { INC ( r ) 、 DEC ( r ) 、 JZ ( r , ztrue ) }
  • 멜작(1961년) 모델을 단순화해 람베크라는 이름을 붙인 주판기(2002년)다.명령 집합 (1)을 사용하지만 추가 매개 변수 z를 사용하여 Minsky(1961) 모델의 방식으로 다음 명령을 지정합니다.
    { INC ( r , z ) , JZDEC ( r , ztruefalse ) }
  • 주판기계에 붙여진 다른 이름인 람베크 기계(2002년).명령 세트(1-reduced)와 추가 매개 변수를 사용하여 다음 명령을 지정합니다.
    { INC ( r , z ) , JZDEC ( r , ztruefalse ) }
  • 후계기, Peano 공리의 '승계기 연산'을 사용하고 매우 유사하기 때문입니다.후속 RAM 모델의 베이스로 사용됩니다.예를 들어 명령 집합(2)을 사용합니다.포인터 머신의 SMM 모델로 이어지는 RAM0 및 RAM1 모델의 기반으로서 Schönhage는 또한 van Emde Boas(1990)에서 간략히 논의되었다.
    { CLR ( r ) , INC ( r ) , JE ( rj , rk , z ) }
  • RASP 모델을 정의하는 데 사용되는 Elgot-Robinson 모델(1964).이 모델은 시작할 때 빈 레지스터가 하나 필요합니다(예: [r0] =0). (이 모델에서는 "인덱스" 레지스터로 사용할 추가 레지스터를 사용하여 간접 주소 지정으로 동일한 모델을 증강했습니다.)
    { INC (r), CPY (rs, rd), JE (rj, rk, z ) }
  • 기타 카운터 머신:Minsky(1967)는 이 기사의 선두 단락에서 설명된 사용 가능한 명령의 슈퍼셋에서 세 가지 기본 모델(프로그램/Minsky/Lambek-abacus, 후계자 및 Elgot-Robinson)을 구축하는 방법을 시연합니다.Melzak(1961) 모형은 '증가'와 '감소'가 아닌 '추가'와 '감소'를 포함하기 때문에 위와 상당히 다르다.단일 레지스터가 튜링 등가성에 충분하다는 민스키(1961, 1967년)의 증명은 계산을 나타내는 레지스터의 괴델 수를 인코딩하고 디코딩하기 위한 두 명령어 MULtiply k와 DIV k를 필요로 한다.Minsky는 두 개 이상의 레지스터를 사용할 수 있다면 더 단순한 INC, DEC 등이 충분하다는 것을 보여준다(그러나 Gödel 숫자는 튜링 등가성을 입증하기 위해 여전히 필요하며, Elgot-Robinson 1964에서도 입증된다).

형식적 정의

카운터 머신은 다음과 같이 구성됩니다.

  1. 라벨이 없는 정수값 레지스터: 각각이 음이 아닌 단일 정수(0, 1, 2, ... - 즉, 무제한)를 유지할 수 있는 유한(또는 일부 모델에서는 무한) 레지스터0 세트 r...rn.레지스터는 자체 연산을 수행합니다. "어큐뮬레이터"와 같은 하나 이상의 특수 레지스터가 있을 수도 있고 없을 수도 있습니다(자세한 내용은 랜덤 액세스 머신 참조).
  2. 실행할 현재 명령을 저장/식별하는 상태 레지스터.이 레지스터는 유한하며 위의 레지스터와 분리되어 있습니다. 따라서 카운터 머신 모델은 하버드 아키텍처의 예입니다.
  3. 라벨이 부착된 순차적 지침 목록:명령의0 유한 목록 I...Im. 프로그램 스토어(유한 상태 머신의 명령)가 레지스터와 같은 물리적 "공간"에 있지 않습니다.보통 컴퓨터 프로그램과 마찬가지로 명령어는 순서대로 나열되며 점프가 성공하지 않는 한 기본 시퀀스는 숫자 순서로 계속됩니다.목록의 각 명령은 (매우) 작은 집합에서 가져온 것이지만 이 집합에는 간접이 포함되어 있지 않습니다.지금까지 대부분의 모델은 이 집합에서 명령을 따왔습니다.
{ 증분(r), 감소(r), 삭제(r), 복사(rj,rk), r=0인 경우 조건부 점프, r=r인k 경우j 조건부 점프, 무조건 점프, HALT}
일부 모델은 위의 명령 중 일부를 파라미터가 없는 명령으로 더 세분화하거나 조건부 점프 if 제로 "JZ ( r , z )" 뒤에 이어지는 "Decrement"와 같은 단일 명령으로 결합합니다.명령어를 원자화하거나 편의 지침을 포함해도 개념적 파워에 변화가 생기지 않습니다.이는 한 변종에서 다른 변종으로 프로그램을 쉽게 번역할 수 있기 때문입니다.
대체 명령 집합은 보충 레지스터-기계 모델에서 설명합니다.

예: 레지스터 #2에서 #3으로 카운트를 복사합니다.

다음으로 clear, 무조건 점프 및 copy의 3가지 유용한 명령어를 작성하는 예를 나타냅니다.

  • CLR(j): 레지스터j r의 내용을 0으로 클리어합니다.
  • J(z): 무조건 명령z I으로 이동합니다.
  • CPY ( s , d ): 소스 레지스터s r의 내용을 대상 레지스터d r에 복사합니다.(일명 명령 집합 컴퓨터 #Transport 트리거 아키텍처 참조)

이후s r은 원래 카운트를 포함합니다(소스 레지스터를 비우는 MOVE와 달리 0으로 지웁니다).

기본 세트(1)는 다음과 같이 사용됩니다.

설명 레지스터 "j"에 대한 영향 지시 카운터 레지스터 ICR에 미치는 영향 요약
INC ( j ) [j] +1 → j [IC] +1 → IC 레지스터 j의 내용을 늘립니다.다음 명령
DEC ( j ) [j] -1 → j [IC] +1 → IC 레지스터 j의 감소 내용; 다음 명령
JZ(j, z) IF [j] = 0 THENz I → IC ELSE [IC] +1 → IC 레지스터 j=0의 내용인 경우 명령 z, 다음 명령인 경우
정지하다

초기 조건

처음에 레지스터 #2에는 "2"가 포함되어 있습니다.레지스터 #0, #1 및 #3이 비어 있습니다('0' 포함).레지스터 #0은 무조건 점프를 위해 사용되기 때문에 계산 내내 변경되지 않는다.레지스터 #1은 스크래치 패드입니다.프로그램은 순서 1부터 시작합니다.

최종 조건

HALT 프로그램은 레지스터 #2의 내용이 원래 카운트이며 레지스터 #3의 내용이 레지스터 #2의 원래 내용과 동일하다.

[2] = [3].

프로그램 개요 설명

프로그램 COPY (#2, #3)는 2개의 파트로 구성되어 있습니다.제1부에서는 소스 레지스터 #2의 내용을 스크래치 패드 #1과 행선지 레지스터 #3 양쪽으로 이동시키기 때문에 #1과 #3은 서로 복사하고 #2의 원래 카운트를 복사하지만 #2는 0으로 감산하는 과정에서 클리어된다.무조건 점프 J(z)는 항상 숫자 0을 포함하는 레지스터 #0의 테스트를 통해 이루어진다.

[#2] →#3; [#2] →#1; 0 →#2

두 번째 부분에서는 프로그램이 스크래치 패드 #1의 내용을 #2로 이동(복귀, 복원)하여 프로세스에서 스크래치 패드 #1을 지웁니다.

[#1] →#2; 0 →#1

프로그램.

노란색으로 강조 표시된 프로그램은 오른쪽 상단에 왼쪽에서 오른쪽으로 표시됩니다.

프로그램의 "실행"은 다음과 같습니다.시간이 지났다.설명은 노란색, 레지스터는 파란색으로 되어 있습니다.프로그램이 90도 뒤집히고 맨 위에 있는 명령 번호(주소), 주소 아래에 있는 명령 니모닉 및 니모닉 아래에 있는 명령 파라미터(셀당 1개)가 표시됩니다.

1 2 3 4 5 6 7 8 9 10 ←지시번호(주소)
JZ DEC 주식회사 주식회사 JZ JZ DEC 주식회사 JZ H ← 사용방법
2 2 3 1 0 1 1 2 0 ←등록번호
6 1 10 6 ← Jump-to 지침 번호
걸음 IC 인스톨 번호 등록 번호 J주소 재작성 레그1 레그2 레지3 레그4 IC
개시하다 0 0 2 0 0 1 [#2]를 #1 및 #3으로 이동합니다.
1 1 JZ 2 6 0 0 2 0 0 1→2 JZ 점프 실패: 레지스터 #2에 2가 포함되어 있습니다.
2 2 DEC 2 0 0 0 2→1 0 0 2→3 DEC 2부터 1까지 감소 레지스터 #2
3 3 주식회사 3 0 0 0 1 0→1 0 3→4 주식회사 레지스터 #3을 0에서 1로 늘립니다.
4 4 주식회사 1 0 0 0→1 1 1 0 4→5 주식회사 레지스터 #1을 0에서 1로 늘립니다.
5 5 JZ 0 1 0 1 1 1 0 5→1 JZ U-점프: 레지스터 #0이(가) 비어 있습니다.
6 1 JZ 2 6 0 1 1 1 0 1→2 JZ 점프 실패: 레지스터 #2에 1이 포함되어 있습니다.
7 2 DEC 2 0 0 1 1→0 1 0 2→3 DEC 1 ~ 0의 디크리먼트 레지스터
8 3 주식회사 3 0 0 1 0 1→2 0 3→4 주식회사 레지스터 #3을 1에서 2로 늘립니다.
9 4 주식회사 1 0 0 1→2 0 2 0 4→5 주식회사 레지스터 #1을 1에서 2로 늘립니다.
10 5 JZ 0 1 0 2 0 2 0 5→1 JZ U-점프: 레지스터 #0이(가) 비어 있습니다.
11 1 JZ 2 6 0 2 0 2 0 1→6 JZ 점프!: 레지스터 #2가 비어 있습니다.
[1]을(를) 2로 이동합니다.
12 6 JZ 1 10 0 2 0 2 0 6→7 JZ 점프 실패: 레지스터 #1에 2가 포함되어 있습니다.
13 7 DEC 1 0 0 2→1 0 2 0 7→8 DEC 2에서 1까지 감소 레지스터 #1
14 8 주식회사 2 0 0 1 0→1 2 0 8→9 주식회사 레지스터 #2를 0에서 1로 늘립니다.
15 9 JZ 0 6 0 1 1 2 0 9→6 JZ U-점프: 레지스터 #0이(가) 비어 있습니다.
16 6 JZ 1 10 0 1 1 2 0 6→7 JZ 점프 실패: 레지스터 #1에 1이 포함됨
17 7 DEC 1 0 0 1→0 1 2 0 7→8 DEC 1 ~ 0의 감소 레지스터 #1
18 8 주식회사 2 0 0 0 1→2 2 0 8→9 주식회사 레지스터 #2를 1에서 2로 늘립니다.
19 9 JZ 0 6 0 0 2 2 0 9→6 JZ U-점프: 레지스터 #0이(가) 비어 있습니다.
20 6 JZ 1 10 0 0 2 2 0 6→10 JZ 점프!: 레지스터 #1이 비어 있습니다.
21 10 H 0 0 0 0 2 2 0 10→10 H 정지하다

부분 재귀 함수: 재귀를 사용하여 "편의 지침"을 작성합니다.

위의 예에서는 첫 번째 기본 명령 {INC, DEC, JZ }이(가) 3개의 명령(무조건 점프 J, CLR, CPY)을 생성하는 방법을 보여 줍니다.어떤 의미에서 CPY는 CLR과 J에 베이스 세트를 모두 사용했습니다.레지스터 #3이 처음에 콘텐츠를 가지고 있었다면 #2와 #3의 콘텐츠 합계는 #3이 되었을 것이다.따라서 CPY 프로그램이 CLR(1) 및 CLR(3)보다 먼저 움직여야 합니다.

단, ADD는 쉽게 할 수 있었습니다.그리고 실제로 다음은 ADD, MULtiply, EXPonent와 같은 원시 재귀 함수가 어떻게 발생할 수 있는지에 대한 요약입니다(Boolos-Burgess-Jeffrey(2002년) 페이지 45-51 참조).

  • 시작 명령 집합: { DEC, INC, JZ, H }
  • r0에 0이 포함되어 있는 경우 무조건 Jump J(z)를 JZ(r0, z)로 정의합니다.
{ J, DEC, INC, JZ, H }
  • 상기의 관점에서 「CLEAR(r)」를 정의합니다.
{ CLR, J, DEC, INC, JZ, H }
  • 위의 관점에서 r의 내용을j 유지하면서 "CoPY ( rj , rk )"를 정의합니다.
{ CPY, CLR, J, DEC, INC, JZ, H }
위는 Shepherdson-Sturgis(1963년)의 명령어 세트이다.
  • 위의 항목을 사용하여 (아마도 r, 및k r의j 내용을 보존하고 있을 가능성이 있다) "ADD (rj, rk, ri)"를 정의합니다.
{ ADD, CPY, CLR, J, DEC, INC, JZ, H }
  • 위와 같이 "MULtiply ( rj , rki )" (MUL)(아마도 r, r의k 내용을j 보존)를 정의합니다.
{ MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }
  • 상기의 관점에서 「EXPONentialj(rk, r, ri )」(EXP)(아마도 r, r의k 내용을j 보존한다)를 정의합니다.
{ EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

일반적으로 동일한 방법을 사용하여 원하는 부분 또는 전체 원시 재귀 함수를 구축할 수 있습니다.실제로 민스키(1967), 셰퍼드슨-스터기스(1963), 불로스-부르게스-제프리(2002)는 기본 집합(1)에서 5개의 원시 재귀 함수 "연산자"를 형성하는 방법을 시연한다.

하지만 완전한 튜링 동등성은 어떨까요?6번째 연산자(μ 연산자)를 추가하여 완전한 등가성을 얻어야 하며, 전체 및 부분 재귀 함수를 만들 수 있습니다.

  1. 제로 함수(또는 상수 함수)
  2. 후계 기능
  3. 항등함수 함수
  4. 구성 함수
  5. 원시 재귀(유도)
  6. μ 연산자(검색 연산자)

저자들은 이것이 사용 가능한 베이스 세트(1, 2, 또는 3) 내에서 쉽게 수행된다는 것을 보여줍니다(예는 μ 연산자에서 찾을 수 있습니다).그러나, 비록 μ 연산자가 기본 명령 집합에 의해 쉽게 생성되더라도, 임의의 부분 재귀 함수가 기본 모델로 쉽게 생성될 수 있다는 것을 의미하지는 않습니다. 튜링 등가 함수와 부분 재귀 함수는 레지스터의 끝으로 빠르게 이동할 수 있는 무제한 μ 연산자를 의미합니다.er chain ad ininitum은 목표를 찾아 헤매고 있다.문제는 레지스터를 번호/이름으로 상세하게 호출해야 한다는 것입니다.INC(47,528) 및 DEC(39,347)는 유한 상태 기계의 지침 표를 소진합니다.유한 상태 기계가 아무리 "크다"고 해도, 우리는 "더 큰" 레지스터 수를 사용하는 함수를 찾을 수 있습니다.

카운터 머신 모델의 문제

이 문제는 랜덤 액세스머신 기사에 자세히 설명되어 있습니다.문제는 크게 두 가지 클래스와 세 번째 "불편한" 클래스로 나뉩니다.

(1) 레지스터의 무한 용량 대 상태 기계 명령의 무한 용량:기계는 어떻게 유한 상태 기계의 용량보다 더 큰 상수를 생성합니까?

(2) 레지스터의 무제한 수와 상태 기계 명령의 제한 수:머신 액세스는 유한 상태 머신의 도달 범위/기능을 넘는 주소 번호로 어떻게 등록됩니까?

(3) 완전히 축소된 모델은 번거롭다:

Shepherdson과 Sturgis(1963)는 그들의 6개 명령 세트에 대해 사과하지 않는다.그들은 '간단한 프로그래밍'을 바탕으로 결정을 내렸다.경제보다는" (p. 219 각주 1)

Shepherdson과 Sturgis의 지시([r]는 "등록부 r의 내용"을 나타냅니다):

    • 증분( r ); [r] +1 → r
    • 감소( r ); [r] -1 → r
    • CLEAR ( r ) ; 0 → r
    • 복사( r tos rd ); [rs] → rd
    • 명령z I로 무조건 점프
    • 명령z I로 점프 IF [r] =0

Minsky(1967)는 2개의 명령어 세트 { INC(z), JZDEC(r, Iz) }를 {CLR(r), INC(r), JZDEC(rz, I), Jz(I) }로 확장한 후 "Universal Program Machine"을 2개의 레지스터만으로 구축할 수 있다는 것을 증명했습니다(ff 255).

2카운터 머신은 튜링에 상당합니다(경고 있음).

모든 튜링 머신에 대해 2CM의 입출력이 올바르게 인코딩되어 있다는 점에서 이를 시뮬레이트하는 2CM이 있습니다.이것은 민스키의 책 (연산, 1967, 페이지 255-258)에서 입증되었고, 대안 증거는 아래에 세 단계로 스케치되었다.첫째, 튜링 기계는 두 개의 스택을 갖춘 유한 상태 기계(FSM)에 의해 시뮬레이션될 수 있다.다음으로 4개의 카운터에서2개의 스택을 시뮬레이트 할 수 있습니다.마지막으로 4개의 카운터를 2개의 카운터로 시뮬레이트할 수 있습니다.2개의 카운터 머신에서는 명령어{ INC ( r , z ) 、 JZDEC ( rtrue , zfalse ) }세트를 사용합니다.

1단계: 튜링 기계는 두 개의 스택으로 시뮬레이션할 수 있습니다.

튜링 기계는 FSM과 0으로 채워진 무한 테이프로 구성되어 있으며, 이 테이프 위에 1과 0을 쓸 수 있습니다.기계의 읽기/쓰기 헤드는 항상 테이프 상의 하나의 셀을 가리킵니다.이 테이프는 그 시점에서 개념적으로 반으로 자를 수 있습니다.테이프의 각 절반은 스택으로 취급할 수 있습니다.상단은 읽기/쓰기 헤드에서 가장 가까운 셀이며, 하단은 헤드에서 약간 떨어져 있으며, 테이프 상의 모든 0은 아래쪽을 넘어섭니다.따라서 튜링 기계는 FSM과 2개의 스택으로 시뮬레이트할 수 있다.헤드를 왼쪽 또는 오른쪽으로 움직이면 한쪽 스택에서 약간 튀어나와 다른 쪽 스택에 밀어넣는 것과 같습니다.쓰기는 비트를 누르기 전에 비트를 변경하는 것과 같습니다.

스텝 2: 스택은 2개의 카운터에서 시뮬레이트할 수 있습니다.

스택상의 비트가 2진수(스택상의 최상위 비트가 최하위 비트)를 나타낸다고 생각되는 경우, 0과 1을 포함한 스택을 2개의 카운터로 시뮬레이트 할 수 있습니다.0을 스택에 푸시하는 것은 그 수를 2배로 하는 것과 같습니다.1을 누르는 것은 1을 두 배로 더하는 것과 같습니다.팝핑은 2로 나눈 것과 같습니다.나머지는 팝핑된 비트입니다.2개의 카운터가 이 스택을 시뮬레이트할 수 있습니다.이 스택에서는 한쪽 카운터가 스택상의 비트를 나타내는 바이너리 표현을 가진 번호를 보유하고 다른 한쪽 카운터가 스크래치 패드로 사용됩니다.첫 번째 카운터의 숫자를 2배로 하기 위해 FSM은 두 번째 카운터를 0으로 초기화하고 첫 번째 카운터를 1회 감소시킨 후 두 번째 카운터를 2회 증가시킵니다.이것은 첫 번째 카운터가0이 될 때까지 계속됩니다이 시점에서 두 번째 카운터는 두 배의 숫자를 유지합니다.한쪽 카운터를 2회 감소시키고 다른 한쪽 카운터를 1회 증가시켜 제1 카운터가 제로가 될 때까지 반복함으로써 분할한다.나머지는 스텝 수의 패리티가 FSM 상태로 부호화되는 홀수 또는 짝수 스텝 후에 제로에 도달했는지에 따라 판별할 수 있습니다.

스텝 3: 4개의 카운터는 2개의 카운터로 시뮬레이트할 수 있습니다.

이전과 같이 카운터 중 하나를 스크래치 패드로 사용합니다.다른 하나는 소인수 분해가 2357인abcd 정수를 가지고 있습니다.지수 a, b, c 및 d는 (Gödel 번호를 통해)1개의 실제 카운터에 패킹되는4개의 가상 카운터라고 생각할 수 있습니다.실제 카운터가 0으로 설정되어 있는 경우, 1회 증분합니다.이는 모든 가상 카운터를 0으로 설정하는 것과 같습니다.실제 카운터가 2배가 되면 a의 증분에 해당하고, 반으로 줄면 a의 증감에 해당합니다.같은 순서로 3으로 곱하거나 나눌 수 있는데, 이는 b의 증감량과 같다.마찬가지로 c와 d는 증가 또는 감소시킬 수 있습니다.c와 같은 가상 카운터가 0인지 확인하려면 실제 카운터를 5로 나누고 나머지를 확인한 다음 5를 곱한 후 나머지를 다시 추가합니다.그러면 실제 카운터는 변경되지 않습니다.나머지는 c가 0일 경우에만 0이 아닙니다.

그 결과 2개의 카운터를 가진 FSM은 4개의 카운터를 시뮬레이트할 수 있습니다.이 카운터는 튜링 머신을 시뮬레이트하는2개의 스택을 시뮬레이트합니다.따라서 FSM에 2개의 카운터를 더한 값은 적어도 튜링 머신만큼 강력합니다.튜링 머신은 2개의 카운터를 가진 FSM을 쉽게 시뮬레이션 할 수 있기 때문에 2개의 머신은 동등한 전력을 가집니다.

주의: *카운터가 N과 0으로 초기화되면 2CM은 2를 계산할N 수 없습니다.

이 결과는 2개의 카운터 머신에 의해 계산되지 않는 N의 다른 함수 목록과 함께 Schroppel(1972)의2 논문에 기재되어 있습니다.예를2 들어, 한쪽 카운터에 N, 다른 카운터에 0으로 초기화되었을 경우입니다.결과는 놀랍지 않다. 왜냐하면 (Minsky에 의해) 인수 N이 단항으로 인코딩된 초기 테이프가 N을 포함하는 튜링 기계를 시뮬레이션하기 위해 적절히 인코딩될 때에만 (Gödelization에 의해) 2 카운터 머신 모델이 보편적이라는 것이 증명되었기 때문이다. 게다가, 2 카운터 머신의 출력도 비슷하게 인코딩될 것이다.이 현상은 시뮬레이션만으로 보편성이 증명되는 매우 작은 계산기반의 전형이다(예: 많은 튜링 타피트, 가장 작은 것으로 알려진 범용 튜링 기계 등).

증명에는 몇 가지 흥미로운 이론이 선행됩니다.

  • "이론:3카운터 머신은 튜링 머신을 시뮬레이트할 수 있습니다." (p.2, Minsky 1967:170-174)
  • "이론:3CM[3-카운터 머신]은 한 변수의 모든 부분 재귀 함수를 계산할 수 있습니다.그것은 [즉, 논쟁]으로 시작한다.카운터에 N], 그리고 (정지된 경우) 카운터에 [F(N)]의 답을 남깁니다.(p.3)
  • "이론:입력과 출력에 대해 불분명한 부호화가 받아들여진다면 카운터 머신은 2CM [2카운터 머신]에 의해 시뮬레이션될 수 있다[p.3; "불순 부호화"는 시뮬레이션된 카운터가 W, X, Y, Z인 경우: 2357이다WXYZ.
  • "이론:입력과 출력에 대해 불명확한 부호화가 받아들여진다면 모든 카운터 머신은 2CM으로 시뮬레이션할 수 있다." (p.3)
    • 「결론: 2CM의 정지 문제는 해결할 수 없습니다.
    • "결론: 입력이 2로N 코드화되고 출력(머신이answer 정지하는 경우)이 2로 코드화된 경우, 2CM은 하나의 인수의 모든 부분 재귀 함수를 계산할 수 있습니다." (p.3)
  • "이론:[한 카운터가 N으로 초기화되면] 2를 계산하는N 카운터 기계는 없습니다." (p. 11)

"3CM은 모든 부분 재귀 함수를 계산할 수 있다"는 두 번째 정리에 대해 저자는 "어려운 문제:3개의 카운터만 사용하여 2개의 숫자를 곱합니다." (p.2).주요 증거는 2-카운터 기계가 비선형 성장률로 산술 시퀀스를 계산할 수 없다는 개념과 관련된다(p.15). 즉, "함수X 2는 어떤 산술 수열보다 더 빠르게 성장한다"(p.11).

카운트에 의한 계산의 실용적인 예

Friden EC-130 계산기에는 추가 로직이 없습니다.그것의 논리는 매우 연속적이었고, 셈을 해서 계산을 했다.내부적으로 10진수는 기수 1이었습니다.예를 들어, 6은 그 자릿수에 할당된 타임슬롯 내에서 연속되는6개의 펄스로 표현되었습니다.각 타임슬롯은 1자리 숫자를 전송하여 최하위부터 전송했습니다.다음 시간 슬롯의 자릿수에 카운트를 추가하는 플립 플랍 세트를 반송합니다.

차입금도 비슷한 방식으로 차입금을 처리하는 반면, 차입금을 빼는 것은 업카운터에 의해 이루어졌다.

타임 슬롯 방식에서는, 각각 부호 비트를 가지는 13 자리수의 6 개의 레지스터를 정의했습니다.곱셈과 나눗셈은 기본적으로 덧셈과 뺄셈을 반복함으로써 이루어졌다.제곱근 버전인 EC-132는 연속 홀수 정수를 효과적으로 감산했으며, 각 감산에는 연속 두 번의 감산이 필요합니다.첫 번째 뺄셈 후 두 번째 뺄셈 전에 최소값이 1씩 증가했습니다.

「 」를 참조해 주세요.

레퍼런스

  • 조지 불로스, 존 P. Burgess, Richard Jeffrey(2002), 계산성과 논리: 영국 케임브리지 대학 출판부 제4판원래 Boulos-Jeffrey 텍스트는 Burgess에 의해 광범위하게 수정되었습니다: 소개 교과서보다 더 고급입니다."Abacus machine" 모델은 5장 "Abacus Computability"에서 광범위하게 개발되었습니다. 이것은 광범위하게 처리되고 비교되는 세 가지 모델 중 하나입니다. 튜링 머신(아직도 Boolos의 원래 4-태플 형태)과 나머지 두 가지 모델입니다.
  • Arthur Burks, Herman Goldstine, John von Neumann(1946), 전자계산기 논리설계의 예비논의, Gordon Bell과 Allen Newell(1971), 컴퓨터 구조: Readings and Examplems, McGrow-Hill Book Company, News, New York. ISBN0-07-004357-4.
  • 스테판 A 쿡과 로버트 A.Rechow(1972), 시간 제한 랜덤 액세스 머신, Journal of Computer Systems Science 7(1973), 354–375.
  • Martin Davis(1958), McGrow-Hill Book Company, Inc., Computability & Unsolvability & Unsolvability뉴욕.
  • Calvin Elgot과 Abraham Robinson(1964), Random-Access Stored-Program Machines, 프로그래밍 언어에 대한 접근법, 컴퓨터 기계 협회 저널, 제11권, 제4호(1964년 10월), 페이지 365-399.
  • 튜링 머신의 계층과 유사한 카운터 머신의 시간 계층과 공간 계층 이론을 개발합니다Fischer, Patrick C.; Meyer, A. R.; Rosenberg, Arnold L. (1968), "Counter machines and counter languages", Mathematical Systems Theory, 2: 265–283, doi:10.1007/bf01694011, MR 0235932.
  • J. Hartmanis(1971), "랜덤 액세스 저장 프로그램 기계의 계산 복잡도", 수학 시스템 이론 5, 3(1971) 페이지 232–245.
  • Hopcroft, John; Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation (1st ed.). Reading Mass: Addison-Wesley. ISBN 0-201-02988-X. 언어, NP-완전성 등의 기계 해석 문제를 중심으로 한 난해한 책.
  • Stephen Kleene(1952), 네덜란드 암스테르담 노스홀랜드 출판사 메타수학 입문.ISBN 0-7204-2103-9.
  • 도널드 크누스(1968), The Art of Computer Programming, 1973년 제2판, 매사추세츠, 애디슨 웨슬리.462-463페이지에서 "연결된 구조를 다루는 새로운 종류의 추상 기계 또는 '자동화'"를 정의합니다.
  • 요아힘 람베크(1961년 6월 15일 수신), 무한 주판 프로그래밍 방법, 수학 게시판, 제4, 제3권.1961년 9월 295-302쪽.Lambek는 부록 II에서 "프로그램의 공식 정의"를 제안한다.그는 멜작(1961년)과 클린(1952년) 메타수학 입문서를 언급했다.
  • Z. A. Melzak(1961년, 1961년 5월 15일 수신), 계산성과 계산에 대한 비공식 산술적 접근, Canadian Mathematical Bulletin, vol. 4, no. 3.1961년 9월 279-293쪽.Melzak은 어떠한 언급도 하지 않았지만 "Dr. R. Hamming, D. McIlroy 및 V와의 대화의 이점"을 인정한다.벨 연구소의 비소츠 씨와 옥스포드 대학의 H. 왕 박사의 전화입니다.
  • Marvin Minsky (1961). "Recursive Unsolvability of Post's Problem of "Tag" and Other Topics in Theory of Turing Machines". Annals of Mathematics. 74 (3): 437–455. doi:10.2307/1970290. JSTOR 1970290.
  • Marvin Minsky (1967). Computation: Finite and Infinite Machines (1st ed.). Englewood Cliffs, N. J.: Prentice-Hall, Inc. 특히 11장: 디지털 컴퓨터와 유사한 모델 및 14장: 계산가능성을 위한 매우 단순한 기본을 참조하십시오.앞 장에서는 "Program machines"를 정의하고 뒷 장에서는 "Universal Program machines with Two Registers"와 "..."에 대해 설명합니다.등기부" 등
  • John C. Shepherdson과 H. E. Sturgis(1961)는 1961년 12월, JACM(Association of Computing Machine) 10:217-255, 1963년 저널, 재귀 함수의 계산 능력을 받았습니다.매우 귀중한 참고 자료입니다.저자들은 부록 A에서 "4.1에서 사용된 지침의 최소성: 유사한 시스템과의 비교"와 관련하여 다른 4가지를 인용한다.
    • 카펑스트, 하인츠, 아이네 압스트라크테 프로그래밍 프로그램 거슈테 레첸마샤인, Zeitschrift 모피 수학자 Logike und Grundlagen der Mathik: 5(1959), 366-379.
    • Ershov, A.P. 연산자 알고리즘, (러시아) Dok.아카드, 나우크 122(1958), 967-970.영어 번역, Automat.익스프레스 1(1959), 20-23
    • Péter, Rossa Graphschemata und rekursive Funktionen, Fentiica 12(1958년), 373.
    • 에르메스, 한스 다이 유니버설리트 프로그래머 레첸마스키넨수학.-물리학Temperberichte (Göttingen) 4 (1954), 42 ~ 53.
  • A. Schönhage(1980), 스토리지 수정 기계, 산업 및 응용 수학 협회, SIAM J. Compute.제9권 제3호 1980년 8월여기서 Schönhage는 SMM과 "후계자 RAM"(랜덤 액세스 머신)의 동등성을 나타냅니다.
  • Rich Schroppel, 1972년 5월, Massachusetts Institute of Technology, A. I. Laboratory, 인공지능 메모 #257, "두 개의 카운터 기계는 계산할N 수 없습니다"저자는 민스키 1967을 언급하며 프랜스 야오가 1971년 4월 비슷한 방법을 사용해 독립적으로 계산 불가능성을 증명했다고 지적한다.
  • 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에 나와 있습니다.이 처리는 1980년 쇼나게를 명확히 한다.쇼나게 처리는 약간 확대된다.효과적인 이해를 위해서는 두 가지 참고 자료가 모두 필요할 수 있습니다.
  • Hao Wang(1957), 튜링의 컴퓨터 이론의 변종, JACM (컴퓨팅 기계 협회 저널) 4; 63–92.1954년 6월 23일부터 25일까지 협회 회의에서 발표.
  • [1]

외부 링크

  1. ^ "Archived copy" (PDF). stedolan.net. Archived from the original (PDF) on 2021-02-14.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)