카운터 머신

카운터 머신(counter machine) 또는 카운터 오토마톤(counter automaton)은 형식논리학 및 이론 컴퓨터 과학에서 계산 모델링에 사용되는 추상 기계이다. 이는 네 가지 유형의 레지스터 머신 중 가장 기본적인 형태이다. 카운터 머신은 하나 이상의 무한 레지스터 세트로 구성되며, 각 레지스터는 단일 비음 정수를 담을 수 있고, 기계가 따를 (대개 순차적인) 산술 및 제어 명령어 목록을 포함한다. 카운터 머신은 일반적으로 상호 배제 원칙과 관련된 병렬 알고리즘 설계 과정에서 사용된다. 이러한 방식으로 사용될 때, 카운터 머신은 메모리 접근과 관련된 계산 시스템의 이산 시간 단계를 모델링하는 데 사용된다. 각 계산 단계에 대한 메모리 접근과 관련하여 계산을 모델링함으로써, 두 개(또는 그 이상)의 스레드가 동일한 메모리 주소에 동시에 쓰기 작업을 수행하는 인터록을 피하기 위한 방식으로 병렬 알고리즘을 설계할 수 있다.

세 개의 카운터를 가진 카운터 머신은 단일 변수의 모든 원시 재귀 함수를 계산할 수 있다. 두 개의 카운터를 가진 카운터 머신은 튜링 완전하며, 적절하게 인코딩된 튜링 기계를 시뮬레이션할 수 있다. 단일 카운터만 가진 카운터 머신은 정규 언어의 적절한 상위 집합과 결정적 문맥 자유 언어의 부분 집합을 인식할 수 있다.^[1]

기본 기능

주어진 카운터 머신 모델의 명령어 세트는 매우 작다. 단 한두 개에서부터 서너 개의 명령어만 사용한다. 대부분의 모델은 몇 가지 산술 연산과 적어도 하나의 조건부 연산(조건이 참이면 점프)을 포함한다. 세 가지 기본 모델은 각각 다음 컬렉션에서 세 가지 명령어를 사용한다. (약어는 임의적이다.)

• CLR (r): 레지스터 r을 CLear 한다. (r을 0으로 설정한다.)
• INC (r): 레지스터 r의 내용을 INCrement 한다.
• DEC (r): 레지스터 r의 내용을 DECrement 한다.
• CPY (r_j, r_k): 레지스터 r_j의 내용을 레지스터 r_k로 CoPY하며 r_j의 내용은 그대로 둔다.
• JZ (r, z): 레지스터 r이 Zero를 포함하면 THEN instruction z로 Jump 하고 ELSE 순서대로 계속한다.
• JE (r_j, r_k, z): 레지스터 r_j의 내용이 레지스터 r_k의 내용과 Equals하면 THEN instruction z로 Jump 하고 ELSE 순서대로 계속한다.

또한, 기계는 일반적으로 HALT 명령어를 가지고 있으며, 이 명령어는 기계를 정지시킨다(일반적으로 결과가 계산된 후).

위에서 언급된 명령어를 사용하여 여러 저자들이 특정 카운터 머신에 대해 논의했다:

• 집합 1: { INC (r), DEC (r), JZ (r, z) }, (마빈 민스키 (1961, 1967), 람벡 (1961))
• 집합 2: { CLR (r), INC (r), JE (r_j, r_k, z) }, (예르쇼프 (1958), 페터 (1958) 셰퍼드슨–스터지스 (1964)에 의해 해석됨; 마빈 민스키 (1967); 쇤하게 (1980))
• 집합 3: { INC (r), CPY (r_j, r_k), JE (r_j, r_k, z) }, (엘고트–로빈슨 (1964), 마빈 민스키 (1967))

세 가지 카운터 머신 기본 모델은 한 모델의 명령어를 다른 모델의 명령어에서 파생할 수 있으므로 동일한 계산 능력을 갖는다. 이들 모두는 튜링 기계의 계산 능력과 동등하다. 단항 처리 방식 때문에 카운터 머신은 일반적으로 비교 가능한 튜링 기계보다 지수적으로 느리다.

대안적인 이름, 대안적인 모델

 이 부분의 본문은 카운터 머신 모델입니다.

카운터 머신 모델은 그 특이성에 따라 다양한 이름으로 불릴 수 있다. 다음에서 "JZDEC ( r )" 명령어는 레지스터 r이 비어있는지 확인하는 복합 명령어이다. 만약 비어있으면 명령어 I_z로 점프하고, 그렇지 않으면 r의 내용을 DECrement 한다.

• 민스키 머신, 마빈 민스키 (1961)가 모델을 형식화했기 때문이다. 주판 머신, 람벡 (1961)이 멜작 (1961) 모델을 단순화하여 붙인 이름이자 불루스-버게스-제프리 (1974)가 부르는 이름이다. 람벡 머신, 불루스-버게스-제프리 (1974)가 주판 머신에 부여한 대안 이름이다. 일반적으로 명령어 세트 (1)을 사용하지만, 명령어 실행이 기본-순차적이지 않으므로 INC 다음의 다음 명령어와 JZDEC의 대안을 지정하기 위해 추가 매개변수 'z'가 나타난다.

  { INC ( r, z ), JZDEC ( r, z_true, z_false) }

• 프로그램 머신, 프로그램 컴퓨터, 마빈 민스키 (1967)가 이 모델에 부여한 이름으로, 컴퓨터처럼 조건부 점프가 성공하지 않으면 명령어가 순차적으로 진행되기 때문이다. (일반적으로) 명령어 세트 (1)을 사용하지만, 셰퍼드슨-스터지스 모델과 유사하게 확장될 수 있다. JZDEC는 종종 분리된다.

  { INC ( r ), DEC ( r ), JZ ( r, z_true )}

• 후속자 머신, '후속자 연산'을 사용하고 페아노 공리계와 매우 유사하기 때문이다. 후속자 RAM 모델의 기반으로 사용된다. 쇤하게가 그의 RAM0 및 RAM1 모델의 기반으로 사용한 명령어 세트 (2)를 사용하며, 이는 그의 포인터 머신 SMM 모델로 이어진다. 반 엠데 보아스 (1990)에서도 간략하게 논의된다.

  { CLR ( r ), INC ( r ), JE ( r_j, r_k, z ) }

• 엘고트-로빈슨 모델, 그들의 RASP 모델 (1964)을 정의하는 데 사용되었다. 이 모델은 시작 시 하나의 빈 레지스터를 필요로 한다 (예: [r0] =0). (그들은 "인덱스" 레지스터로 사용할 추가 레지스터를 사용하여 간접 주소 지정을 통해 동일한 모델을 확장했다.)

  { INC (r), CPY ( r_s, r_d ), JE ( r_j, r_k, z ) }

• 셰퍼드슨-스터지스 머신, 이 저자들이 그들의 모델을 쉽게 접근할 수 있는 설명으로 공식적으로 명시했기 때문이다 (1963). 추가적인 편의 명령어 (JNZ는 JZ 대신 사용되는 "0이 아니면 점프"임)로 확장된 명령어 세트 (1)을 사용한다.

  { INC ( r ), DEC ( r ), CLR ( r ), CPY ( r_j, r_k ), JNZ ( r, z ), J ( z ) }

• 다른 카운터 머신: 마빈 민스키 (1967)는 이 문서의 서론 단락에 설명된 사용 가능한 명령어의 상위 집합에서 세 가지 기본 모델 (프로그램/민스키/람벡-주판, 후속자, 엘고트-로빈슨)을 구축하는 방법을 보여준다. 멜작 (1961) 모델은 '증가' 및 '감소' 대신 '더하기' 및 '빼기'를 포함하므로 위의 모델들과 상당히 다르다. 마빈 민스키 (1961, 1967)의 단일 레지스터가 튜링 동등성에 충분하다는 증명은 계산을 나타내는 레지스터에서 괴델 수를 인코딩하고 디코딩하기 위해 { k를 MULtiply, k를 DIVide } 두 가지 명령어를 필요로 한다. 마빈 민스키는 두 개 이상의 레지스터를 사용할 수 있다면 더 간단한 INC, DEC 등이 충분하다는 것을 보여준다 (그러나 튜링 동등성을 증명하기 위해서는 여전히 괴델 수가 필요하다; 엘고트-로빈슨 1964에서도 증명됨).

공식 정의

카운터 머신은 다음으로 구성된다:

1. 레이블이 지정된 무한 정수 값 레지스터: 유한한 (또는 일부 모델에서는 무한한) 레지스터 r₀ ... r_n 세트. 각 레지스터는 하나의 비음 정수(0, 1, 2, ... 즉, 무한)를 담을 수 있다. 레지스터는 자체적으로 산술 연산을 수행한다. "누산기"와 같은 하나 이상의 특수 레지스터가 있을 수도 있고 없을 수도 있다 (이에 대한 자세한 내용은 랜덤 접근 기계 참조).
2. 현재 실행할 명령어를 저장/식별하는 상태 레지스터. 이 레지스터는 유한하며 위의 레지스터와는 별개이다. 따라서 카운터 머신 모델은 하버드 아키텍처의 한 예시이다.
3. 레이블이 지정된 순차적 명령어 목록: 명령어 I₀ ... I_m의 유한 목록. 프로그램 저장소(유한 상태 기계의 명령어)는 레지스터와 동일한 물리적 "공간"에 있지 않다. 일반적으로, 하지만 항상 그런 것은 아니며, 컴퓨터 프로그램처럼 명령어는 순차적으로 나열된다. 점프가 성공하지 않는 한, 기본 순서는 숫자 순서로 계속된다. 목록의 각 명령어는 (매우) 작은 세트에서 가져오지만, 이 세트에는 간접 주소 지정이 포함되지 않는다. 역사적으로 대부분의 모델은 다음 세트에서 명령어를 가져왔다:

{ 증가(r), 감소(r), 지우기(r); 복사(r_j,r_k), r=0이면 조건부 점프, r_j=r_k이면 조건부 점프, 무조건 점프, HALT }

일부 모델은 위에서 언급된 일부 명령어를 매개변수 없는 명령어로 더 세분화하거나, "조건부 점프-0이면 JZ ( r, z )"와 같이 "감소"와 결합하여 단일 명령어로 만들기도 한다. 명령어를 세분화하거나 편의 명령어를 포함하더라도 개념적 능력에는 변화가 없으며, 한 변형의 어떤 프로그램이든 다른 변형으로 간단하게 번역될 수 있다.

대체 명령어 세트는 보충 자료인 레지스터 머신 모델에서 논의된다.

예시: 레지스터 #2에서 #3으로 카운트 COPY

이 예시는 세 가지 더 유용한 명령어인 클리어, 무조건 점프, 복사를 만드는 방법을 보여준다.

• CLR ( j ): 레지스터 r_j의 내용을 0으로 지운다.
• J ( z ): 무조건 명령어 I_z로 점프한다.
• CPY ( s, d ): 소스 레지스터 r_s의 내용을 대상 레지스터 r_d로 복사한다. (단일 명령어 집합 컴퓨터#전송 트리거 아키텍처 참조)

이후 r_s는 원래 카운트를 유지한다 (소스 레지스터를 비우는, 즉 0으로 지우는 MOVE와는 다르다).

여기서 정의된 기본 세트 (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 THEN Iz → IC ELSE [IC] +1 → IC	레지스터 j의 내용이 0이면 명령어 z, 아니면 다음 명령어
HALT

초기 조건

초기에 레지스터 #2는 "2"를 포함한다. 레지스터 #0, #1, #3은 비어 있다("0"을 포함). 레지스터 #0은 무조건 점프에 사용되기 때문에 계산 내내 변경되지 않는다. 레지스터 #1은 임시 저장 공간이다. 프로그램은 명령어 1부터 시작한다.

최종 조건

프로그램은 레지스터 #2의 내용이 원래 카운트와 같고 레지스터 #3의 내용이 레지스터 #2의 원래 내용과 같아지면 HALT한다. 즉,

[2] = [3].

프로그램 고급 설명

프로그램 COPY ( #2, #3)는 두 부분으로 구성된다. 첫 번째 부분에서 프로그램은 소스 레지스터 #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	2	3	4	5	6	7	8	9	10	← 명령어 번호 (주소)
														JZ	DEC	INC	INC	JZ	JZ	DEC	INC	JZ	H	← 명령어
														2	2	3	1	0	1	1	2	0		← 레지스터 번호
														6				1	10			6		← 점프할 명령어 번호
단계		IC	명령어 #	레지스터 #	J-주소		reg0	reg1	reg2	reg3	reg4		IC
시작							0	0	2	0	0		1												[#2]를 #1과 #3으로 이동:
1		1	JZ	2	6		0	0	2	0	0		1→2		JZ									Jump 실패: 레지스터 #2에 2가 들어있음
2		2	DEC	2	0		0	0	2→1	0	0		2→3			DEC									레지스터 #2를 2에서 1로 감소
3		3	INC	3	0		0	0	1	0→1	0		3→4				INC								레지스터 #3를 0에서 1로 증가
4		4	INC	1	0		0	0→1	1	1	0		4→5					INC								레지스터 #1을 0에서 1로 증가
5		5	JZ	0	1		0	1	1	1	0		5→1						JZ						무조건 점프: 레지스터 #0이 비어 있음
6		1	JZ	2	6		0	1	1	1	0		1→2		JZ									Jump 실패: 레지스터 #2에 1이 들어있음
7		2	DEC	2	0		0	1	1→0	1	0		2→3			DEC								레지스터 #2를 1에서 0으로 감소
8		3	INC	3	0		0	1	0	1→2	0		3→4				INC								레지스터 #3를 1에서 2로 증가
9		4	INC	1	0		0	1→2	0	2	0		4→5					INC								레지스터 #1을 1에서 2로 증가
10		5	JZ	0	1		0	2	0	2	0		5→1						JZ						무조건 점프: 레지스터 #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					Jump 실패: 레지스터 #1에 2가 들어있음
13		7	DEC	1	0		0	2→1	0	2	0		7→8								DEC				레지스터 #1을 2에서 1로 감소
14		8	INC	2	0		0	1	0→1	2	0		8→9									INC			레지스터 #2를 0에서 1로 증가
15		9	JZ	0	6		0	1	1	2	0		9→6										JZ		무조건 점프: 레지스터 #0이 비어 있음
16		6	JZ	1	10		0	1	1	2	0		6→7							JZ					Jump 실패: 레지스터 #1에 1이 들어있음
17		7	DEC	1	0		0	1→0	1	2	0		7→8								DEC				레지스터 #1을 1에서 0으로 감소
18		8	INC	2	0		0	0	1→2	2	0		8→9									INC			레지스터 #2를 1에서 2로 증가
19		9	JZ	0	6		0	0	2	2	0		9→6										JZ		무조건 점프: 레지스터 #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	HALT

부분 재귀 함수: 재귀를 이용한 "편의 명령어" 구축

위의 예시는 기본적인 명령어 세트 { INC, DEC, JZ }가 어떻게 세 가지 더 유용한 명령어—무조건 점프 J, CLR, CPY—를 만들 수 있는지 보여준다. 어떤 의미에서 CPY는 CLR과 J, 그리고 기본 세트를 모두 사용했다. 만약 레지스터 #3에 초기에 내용이 있었다면, #2와 #3의 내용의 합이 #3에 저장되었을 것이다. 따라서 CPY 프로그램은 이동 전에 CLR(1)과 CLR(3)을 선행했어야 완전히 정확하다.

하지만 ADD는 쉽게 가능했음을 알 수 있다. 사실 다음은 ADD, MULtiply, EXPonent와 같은 원시 재귀 함수가 어떻게 생겨날 수 있는지에 대한 요약이다.^[2]

• 시작 명령어 세트: { DEC, INC, JZ, H }
• r0가 0을 포함할 때 JZ ( r0, z )를 사용하여 무조건 "점프 J (z)"를 정의한다.

{ J, DEC, INC, JZ, H }

• 위의 것을 이용하여 "CLeaR ( r )"을 정의한다.

{ CLR, J, DEC, INC, JZ, H }

• r_j의 내용을 유지하면서 위의 것을 이용하여 "CoPY ( r_j, r_k )"를 정의한다.

{ CPY, CLR, J, DEC, INC, JZ, H }

위는 셰퍼드슨–스터지스 (1963)의 명령어 세트이다.

• 위의 것을 이용하여 "ADD ( r_j, r_k, r_i )"를 정의한다 (아마 r_j와 r_k의 내용을 보존하면서):

{ ADD, CPY, CLR, J, DEC, INC, JZ, H }

• 위의 것을 이용하여 "MULtiply ( r_j, r_k, r_i )" (MUL)를 정의한다 (아마 r_j와 r_k의 내용을 보존하면서):

{ MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

• 위의 것을 이용하여 "EXPonential ( r_j, r_k, r_i )" (EXP)를 정의한다 (아마 r_j와 r_k의 내용을 보존하면서):

{ EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

일반적으로, 우리는 같은 방법을 사용하여 원하는 모든 부분 또는 전체 원시 재귀 함수를 구축할 수 있다. 실제로, 마빈 민스키 (1967), 셰퍼드슨-스터지스 (1963), 불루스-버게스-제프리 (1974)는 기본 세트 (1)로부터 다섯 가지 원시 재귀 함수 "연산자" (아래 1-5)를 형성하는 방법을 시연한다.

그러나 완전한 튜링 동등성은 어떨까? 우리는 전체 및 부분 재귀 함수를 생성할 수 있는 완전한 동등성을 얻기 위해 여섯 번째 연산자인 μ 연산자를 추가해야 한다.

1. 영 함수 (또는 상수 함수)
2. 후속 함수
3. 항등 함수
4. 합성 함수
5. 원시 재귀 (귀납)
6. μ 연산자 (무한 탐색 연산자)

저자들은 이것이 사용 가능한 기본 집합 (1, 2 또는 3) 중 어느 하나에서든 쉽게 수행됨을 보여준다 (예시는 μ 연산자에서 찾을 수 있다). 이는 카운터 머신 설계의 유한한 명령어 집합 및 프로그램 크기에도 불구하고 모든 뮤 재귀 함수가 카운터 머신으로 구현될 수 있음을 의미한다.^[3] 그러나 필요한 구성은 랜덤 접근 기계와 같은 더 복잡한 레지스터 머신에서 정의하기 비교적 쉬운 함수에 대해서도 직관적이지 않을 수 있다. 이는 μ 연산자가 무한정 반복될 수 있지만, 주어진 카운터 머신은 명령어 목록의 유한한 크기로 인해 무한정 많은 개별 레지스터를 주소 지정할 수 없기 때문이다.

예를 들어, 위에서 언급된 원시 재귀 연산자 계층은 지수 연산을 넘어 커누스 윗화살표 표기법의 더 고차원적인 화살표 연산으로 확장될 수 있다. 어떤 고정된 ${\displaystyle k}$에 대해 함수 ${\displaystyle Q(x,y)=x\uparrow ^{k}y}$는 원시 재귀적이며, 간단한 방법으로 카운터 머신으로 구현될 수 있다. 그러나 함수 ${\displaystyle R(n,x,y)=x\uparrow ^{n}y}$는 원시 재귀적이지 않다. ${\displaystyle n}$의 더 작은 값에 대해 재귀적으로 함수를 적용할 수 있도록 콜 스택을 구현하여 위의 후속자, 덧셈, 곱셈 및 지수 연산 명령어와 유사한 구성을 사용하여 위쪽 화살표 연산자 ${\displaystyle R}$를 구현하려는 유혹을 느낄 수 있다. 이 아이디어는 많은 프로그래밍 언어에서 실제로 함수를 구현하는 방법과 유사하다. 그러나 카운터 머신은 계산에 무한정 많은 레지스터를 사용할 수 없으며, 이는 임의로 커질 수 있는 콜 스택을 구현하는 데 필요할 것이다. 위쪽 화살표 연산은 뮤 재귀적이므로 여전히 카운터 머신으로 구현될 수 있지만, 이 함수는 괴델 수를 사용하는 것과 같이 유한한 수의 레지스터 안에 무한한 양의 정보를 인코딩하여 구현될 것이다.

카운터 머신 모델의 문제점

문제점은 랜덤 접근 기계 문서에서 자세히 논의된다. 문제는 두 가지 주요 범주와 세 번째 "불편함" 범주로 나뉜다:

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

(2) 레지스터의 무한한 개수 대 상태 기계 명령어의 유한한 개수: 기계는 유한 상태 기계의 도달/능력을 넘어선 주소 번호를 가진 레지스터에 어떻게 접근할까?

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

셰퍼드슨과 스터지스 (1963)는 그들의 6개 명령어 세트에 대해 사과하지 않는다. 그들은 "경제성보다는 프로그래밍의 용이성"에 기반하여 선택을 했다 (p. 219 각주 1).

셰퍼드슨과 스터지스의 명령어들 ( [r]은 "레지스터 r의 내용"을 나타낸다):

• • INCREMENT ( r ) ; [r] +1 → r
  • DECREMENT ( r ) ; [r] -1 → r
  • CLEAR ( r ) ; 0 → r
  • COPY ( r_s to r_d ) ; [r_s] → r_d
  • JUMP-UNCONDITIONAL to instruction I_z
  • JUMP IF [r] =0 to instruction I_z

마빈 민스키 (1967)는 그의 2개 명령어 세트 { INC (z), JZDEC (r, I_z) }를 { CLR (r), INC (r), JZDEC (r, I_z), J (I_z) }로 확장한 후, "범용 프로그램 머신"이 단 두 개의 레지스터로 구축될 수 있음을 증명했다 (p. 255ff).

두 카운터 머신은 튜링 동등하다 (주의사항 포함)

모든 튜링 기계에 대해, 2CM의 입력과 출력이 적절하게 인코딩된다면, 그 튜링 기계를 시뮬레이션하는 2CM이 존재한다. 이는 마빈 민스키의 책 (Computation, 1967, p. 255-258)에 증명되어 있으며, 다른 증명은 아래 세 단계로 개략적으로 설명되어 있다. 첫째, 튜링 기계는 두 개의 스택이 장착된 유한 상태 기계(FSM)에 의해 시뮬레이션될 수 있다. 둘째, 두 개의 스택은 네 개의 카운터에 의해 시뮬레이션될 수 있다. 마지막으로, 네 개의 카운터는 두 개의 카운터에 의해 시뮬레이션될 수 있다. 두 카운터 머신은 명령어 집합 { INC ( r, z ), JZDEC ( r, z_true, z_false) }를 사용한다.

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

튜링 기계는 FSM과 무한 테이프로 구성되며, 이 테이프는 초기에는 0으로 채워져 있고 기계는 그 위에 1과 0을 쓸 수 있다. 언제든지 기계의 읽기/쓰기 헤드는 테이프의 한 셀을 가리킨다. 이 테이프는 그 지점에서 개념적으로 절반으로 나눌 수 있다. 테이프의 각 절반은 스택으로 처리될 수 있으며, 상단은 읽기/쓰기 헤드에 가장 가까운 셀이고, 하단은 헤드에서 어느 정도 떨어져 있으며, 하단 너머의 테이프에는 모두 0이 있다. 따라서 튜링 기계는 FSM과 두 개의 스택으로 시뮬레이션될 수 있다. 헤드를 왼쪽이나 오른쪽으로 이동하는 것은 한 스택에서 비트를 팝하고 다른 스택으로 푸시하는 것과 동등하다. 쓰기는 푸시하기 전에 비트를 변경하는 것과 동등하다.

2단계: 스택은 두 개의 카운터로 시뮬레이션될 수 있다.

0과 1을 포함하는 스택은 스택의 비트가 이진법을 나타내는 것으로 생각될 때 (스택의 가장 위쪽 비트가 최하위 비트임) 두 개의 카운터로 시뮬레이션될 수 있다. 스택에 0을 푸시하는 것은 숫자를 두 배로 늘리는 것과 동등하다. 1을 푸시하는 것은 두 배로 늘리고 1을 더하는 것과 동등하다. 팝하는 것은 2로 나누는 것과 동등하며, 이 경우 나머지가 팝된 비트이다. 두 개의 카운터는 이 스택을 시뮬레이션할 수 있으며, 이 스택에서 한 카운터는 스택의 비트를 나타내는 이진 표현을 가진 숫자를 보유하고 다른 카운터는 임시 저장 공간으로 사용된다. 첫 번째 카운터의 숫자를 두 배로 늘리려면 FSM은 두 번째 카운터를 0으로 초기화한 다음, 첫 번째 카운터를 한 번 감소시키고 두 번째 카운터를 두 번 증가시키는 작업을 반복할 수 있다. 이 작업은 첫 번째 카운터가 0에 도달할 때까지 계속된다. 그 시점에서 두 번째 카운터는 두 배로 늘어난 숫자를 보유하게 된다. 절반으로 줄이는 작업은 한 카운터를 두 번 감소시키고 다른 카운터를 한 번 증가시킨 다음, 첫 번째 카운터가 0에 도달할 때까지 반복하여 수행된다. 나머지는 짝수 또는 홀수 단계 후에 0에 도달했는지 여부에 따라 결정될 수 있으며, 단계 수의 패리티는 FSM의 상태에 인코딩된다.

3단계: 네 개의 카운터는 두 개의 카운터로 시뮬레이션될 수 있다.

이전과 마찬가지로, 카운터 중 하나는 임시 저장 공간으로 사용된다. 다른 하나는 소수 인수분해가 2^a3^b5^c7^d인 정수를 포함한다. 지수 a, b, c, d는 단일 실제 카운터에 ( 괴델 수 매기기를 통해) 압축되는 네 개의 가상 카운터로 생각될 수 있다. 실제 카운터가 0으로 설정된 다음 한 번 증가하면 모든 가상 카운터를 0으로 설정하는 것과 동등하다. 실제 카운터가 두 배가 되면 a를 증가시키는 것과 동등하며, 절반이 되면 a를 감소시키는 것과 동등하다. 유사한 절차를 통해 3으로 곱하거나 나눌 수 있으며, 이는 b를 증가시키거나 감소시키는 것과 동등하다. 마찬가지로, c와 d도 증가시키거나 감소시킬 수 있다. c와 같은 가상 카운터가 0과 같은지 확인하려면 실제 카운터를 5로 나누고, 나머지가 무엇인지 확인한 다음, 5를 곱하고 나머지를 다시 더하면 된다. 이렇게 하면 실제 카운터는 변경되지 않는다. 나머지는 c가 0일 때만 0이 아니었을 것이다.

결과적으로, 두 개의 카운터를 가진 FSM은 네 개의 카운터를 시뮬레이션할 수 있으며, 이들은 다시 두 개의 스택을 시뮬레이션하고, 이들은 다시 튜링 기계를 시뮬레이션한다. 따라서 FSM에 두 개의 카운터가 있으면 튜링 기계만큼 강력하다. 튜링 기계는 두 개의 카운터를 가진 FSM을 쉽게 시뮬레이션할 수 있으므로 두 기계는 동등한 능력을 갖는다.

주의사항: 카운터가 N과 0으로 초기화된 경우, 2CM은 2^N을 계산할 수 없다

이 결과는 슈뢰펠(1972)의 논문에 N², sqrt(N), log₂(N) 등과 같이 두 카운터 머신이 계산할 수 없는 다른 N 함수 목록과 함께 나타난다 — 한 카운터에 N이, 다른 카운터에 0이 초기화된 경우이다. 이 결과는 놀랍지 않은데, 두 카운터 머신 모델은 입력 N이 튜링 기계를 시뮬레이션하기 위해 적절하게 인코딩(괴델화)된 경우에만 보편적이라는 것이 (민스키에 의해) 증명되었기 때문이다. 여기서 튜링 기계의 초기 테이프는 단항으로 인코딩된 N을 포함하며, 두 카운터 머신의 출력도 유사하게 인코딩된다. 이러한 현상은 보편성이 시뮬레이션을 통해서만 증명되는 매우 작은 계산 기반(예: 많은 튜링 곤궁, 알려진 가장 작은 범용 튜링 기계 등)에서 흔히 나타난다.

이 증명에 앞서 몇 가지 흥미로운 정리가 제시된다.

• "정리: 세 카운터 머신은 튜링 기계를 시뮬레이션할 수 있다" (p. 2, 마빈 민스키 1967:170-174도 참조)
• "정리: 3CM [세 카운터 머신]은 한 변수의 모든 부분 재귀 함수를 계산할 수 있다. 인자 [즉, N]로 시작하여 (정지하면) 카운터에 답 [즉, F(N)]을 남긴다." (p. 3)
• "정리: 카운터 머신은 2CM [두 카운터 머신]에 의해 시뮬레이션될 수 있다. 단, 입력과 출력에 모호한 코딩이 허용된다는 조건 하에." [p. 3; "모호한 코딩"은 2^W3^X5^Y7^Z이며, 여기서 시뮬레이션된 카운터는 W, X, Y, Z이다.]
• "정리: 모든 카운터 머신은 2CM에 의해 시뮬레이션될 수 있다. 단, 입력과 출력에 모호한 코딩이 허용된다는 조건 하에." (p. 3)
  • "귀결: 2CM의 정지 문제는 해결 불가능하다.
  • "귀결: 2CM은 한 인자의 모든 부분 재귀 함수를 계산할 수 있다. 단, 입력이 2^N으로 코딩되고 출력(기계가 정지하면)이 2^answer로 코딩된다는 조건 하에." (p. 3)
• "정리: 2^N을 계산하는 두 카운터 머신은 없다 [한 카운터가 N으로 초기화된 경우]." (p. 11)

"3CM은 어떤 부분 재귀 함수도 계산할 수 있다"는 두 번째 정리와 관련하여, 저자는 독자에게 "어려운 문제: 세 개의 카운터만을 사용하여 두 숫자를 곱하라" (p. 2)고 도전한다. 주요 증명은 두 카운터 머신이 비선형 성장률을 가진 산술 수열을 계산할 수 없다는 개념을 포함한다 (p. 15), 즉 "함수 2^X는 어떤 산술 진행보다 더 빠르게 성장한다." (p. 11).

계산의 실제 예시: 계산에 의한 계산

프리든 EC-130 계산기는 본질적으로 덧셈 로직이 없었다. 그 로직은 고도로 직렬적이었고, 계산을 통해 산술을 수행했다. 내부적으로 십진수 자릿수는 10진수였다. 예를 들어, 6은 해당 자릿수에 할당된 시간 슬롯 내에서 6개의 연속 펄스로 표현되었다. 각 시간 슬롯은 하나의 자릿수를 운반했고, 최하위 자릿수부터 먼저 처리되었다. 올림수는 플립플롭을 설정하여 다음 시간 슬롯의 자릿수에 하나의 카운트를 추가하게 했다.

덧셈은 상승 카운터로, 뺄셈은 하강 카운터로 수행되었으며, 빌림수를 처리하는 비슷한 방식이 있었다.

시간 슬롯 방식은 각각 부호 비트를 가진 13개의 십진수 자릿수 레지스터 6개를 정의했다. 곱셈과 나눗셈은 기본적으로 반복적인 덧셈과 뺄셈으로 수행되었다. 제곱근 버전인 EC-132는 연속된 홀수를 효과적으로 뺐고, 각 감소는 두 번의 연속적인 뺄셈을 필요로 했다. 첫 번째 뺄셈 후, 두 번째 뺄셈 전에 피감수는 1만큼 증가되었다.

같이 보기

• 포인터 머신
• 포스트-튜링 머신
• 랜덤 접근 기계
• 레지스터 머신
• 왕 B-머신
• 벡터 덧셈 시스템