튜링 기계

3. 역사

앨런 튜링은 1936년 논문 "계산가능수와 결정문제에 대한 응용에 관하여"에서 튜링 기계를 처음 제시했다.^[25] 튜링은 이 기계를 통해 계산 가능성, 결정 가능성, 정지 문제 등 중요한 개념을 정의하고 증명했다.

다비트 힐베르트가 1900년에 제안한 힐베르트의 문제들 중 열 번째 문제는, 디오판토스 방정식의 정수해를 유한한 연산을 통해 얻어낼 수 있는지 묻는 문제였다. 1928년 힐베르트는 이 문제를 다음 세 가지 질문으로 더 엄밀하게 만들었다.

# 수학은 완전한가?

# 수학은 모순이 없는가?

# 수학은 결정 가능한가?

처음 두 질문은 1930년 쿠르트 괴델에 의해 해결되었으나, 세 번째 문제인 결정 문제는 1930년대 중반까지 해결되지 않았다.

1935년 봄, 케임브리지 대학교 킹스 칼리지의 앨런 튜링은 결정 문제에 대한 괴델의 연구에 대해 알게 되었고, 이 문제에 도전하게 되었다. 튜링은 일생 동안 기계에 대한 흥미를 가지고 있었으며, 박사후과정 동안 불 논리 곱셈 기계를 만들기도 했다.

1937년, 프린스턴에서 박사 학위 연구를 하는 동안 튜링은 전기-기계식 릴레이를 이용해 디지털(Boolean-logic) 곱셈 기계를 만들었다.^[7] 튜링의 발명은 단순한 호기심과 실험 정신에서 시작되었지만, 같은 시기 독일(콘라트 추제)과 미국(하워드 에이컨, 조지 스티비츠)에서도 비슷한 연구가 진행되고 있었으며, 그 결과물은 제2차 세계 대전 동안 연합국과 추축국의 군사 활동에 사용되었다.

앨런조 처치는 튜링의 논문(1936)을 발표하면서 "튜링 기계"라는 용어를 만들었다.^[10] 같은 시기 에밀 포스트도 독립적으로 유사한 계산 모델을 제시했다.^[26]

1950년대 중반 하오 왕과 마빈 민스키는 튜링 기계를 좀 더 간단한 형태로 바꾸었다. 동시에 유럽의 연구자들은 최신식의 전자 컴퓨터를 현재의 튜링 기계인 '컴퓨터와 같은 이론적 오브젝트'로 환원시켜 생각했다. 1950년대 후반에서 1960년대 초반에 멜자크와 레벡(1961), 민스키(1961), 셰퍼슨과 스터기스(1961) 등의 유럽 연구자들은 일련의 연구들을 통해 튜링 기계를 좀 더 친숙하고 컴퓨터와 같은 '계산기 기계'로 만들었다. 이후 1970년대 초반에는 엘곳과 로빈슨(1964), 하트마니스(1971), 쿡과 렉하우(1973) 등은 이 연구를 진척시켜 '레지스터 기계'와 RAM의 모델로 발전시켰다.

3. 1. 처치-튜링 명제

• 테이프에 있는 임의의 기계가 "순환적"(예: 멈추거나 계산 작업을 계속하지 못하는 경우)인지 결정할 수 있는 기계가 존재하는가?
• 테이프에 있는 임의의 기계가 주어진 기호를 인쇄하는지 여부를 결정할 수 있는 기계가 존재하는가?^[11][12]

4. 다양한 튜링 기계 모델

튜링 기계는 다양한 변형 모델이 존재한다. 반 엠데 보아스(1990)에 따르면, 튜링 기계의 형식적인 7-튜플 설명은 기계 작동 방식과 계산 과정에 대한 부분적인 정보만 제공한다.^[1]

예를 들어, 실제 튜링 기계를 만들 때는 다음과 같은 다양한 결정이 필요하다.

• 기호의 실제 모양과 무한히 읽고 쓰는 방법
• 테이프 헤드를 테이프 전체로 이동시키는 대신, 테이프가 헤드 아래에서 앞뒤로 움직이도록 하는 방법
• 테이프를 유한하게 만들고 필요에 따라 공백으로 자동 확장하는 방법 (수학적 정의에 가장 가깝다)

• (정의 1): '''(q_i, S_j, S_k/E/N, L/R/N, q_m)'''
• '''(''' 현재 상태 '''q_i''' ''',''' 스캔된 기호 '''S_j''' ''',''' 인쇄 기호 '''S_k'''/지우기 '''E'''/없음 '''N''' ''',''' 테이프를 한 칸 왼쪽으로 이동 '''L'''/오른쪽으로 이동 '''R'''/없음 '''N''' ''',''' 새로운 상태 '''q_m''' ''')'''

• (정의 2): '''(q_i, S_j, q_m, S_k/E/N, L/R/N)'''
• '''(''' 현재 상태 '''q_i''' ''',''' 스캔된 기호 '''S_j''' ''',''' 새로운 상태 '''q_m''' ''',''' 인쇄 기호 '''S_k'''/지우기 '''E'''/없음 '''N''' ''',''' 테이프를 한 칸 왼쪽으로 이동 '''L'''/오른쪽으로 이동 '''R'''/없음 '''N''' ''')'''

튜링의 원래 모델은 처음 세 줄(N1, N2, N3)만 허용했다. 그는 0번째 기호 S₀ = "지우기" 또는 "공백" 등을 지정하여 "스캔된 사각형"을 지울 수 있도록 허용했지만, 인쇄하지 않는 것은 허용하지 않았다. 1936–1937년 튜링의 원본 논문 이후, 기계 모델은 아홉 가지 가능한 유형의 5-튜플을 모두 허용했다.^[1]

아래는 튜링이 허용했던 5-튜플의 유형을 정리한 표이다.

위의 아홉 개의 5-튜플로 모든 튜링 표(명령 목록)를 구성할 수 있다. 기술적인 이유로 인쇄하지 않는 또는 "N" 명령어(4, 5, 6)는 일반적으로 생략할 수 있다.^[1]

덜 자주 4-튜플의 사용이 발견되는데, 이는 튜링 명령어의 추가적인 원자화를 나타낸다.^[1]

아래는 3 상태 비지 비버("P" = "1" 인쇄/쓰기) 표이다.

위 표는 "상태 전이" 다이어그램으로 표현될 수 있다. 일반적으로 큰 표는 표로 남겨두는 것이 좋지만, 특정 개념은 그림으로 볼 때 더 쉽게 이해할 수 있다.^[1]

이러한 다이어그램은 시간과 공간을 통한 계산의 과정("궤적")이 아닌, 시간상에서 고정된 표의 스냅샷을 나타낸다는 점에 주의해야 한다. 비지 비버 기계는 항상 동일한 상태 궤적을 따르지만, 가변 입력 "매개변수"로 제공될 수 있는 "복사" 기계의 경우에는 그렇지 않다.^[1]

"계산 진행" 다이어그램은 3 상태 비지 비버의 "상태"(명령)가 시작부터 끝까지 계산을 진행하는 모습을 보여준다. 기계를 중지하고 "상태 레지스터"와 전체 테이프를 비우면 이러한 "구성"을 사용하여 진행 중인 계산을 어디에서나 다시 시작할 수 있다.^[1]

4. 1. 튜링 기계와 동치인 모델들

• 다중 테이프 튜링 기계
• 다중 트랙 튜링 기계
• 입력과 출력이 있는 튜링 기계
• 비결정론적 튜링 기계

• 단일 스택 푸시다운 오토마타(PDA): 스택의 후입선출(LIFO) 제약을 완화하여 더 유연하고 간결하게 만든 모델이다.
• 2개의 스택을 가진 PDA: 한 스택은 헤드의 왼쪽 테이프를, 다른 스택은 오른쪽 테이프를 모델링하여 표준 LIFO 의미를 갖는다.
• 읽기 전용 우측 이동 튜링 기계: 결정적 유한 오토마타(DFA)와 동등하며, NFA를 DFA로 변환 알고리즘을 사용하면 비결정적 유한 오토마타(NFA)와도 동등하다.
• 레지스터 기계: 실용적이고 교육적인 목적으로, 일반적인 어셈블리 언어 프로그래밍 언어로 사용될 수 있다.

5. 범용 튜링 기계

다른 모든 튜링 기계를 시뮬레이션할 수 있는 튜링 기계를 보편 튜링 기계(UTM, 또는 단순히 보편 기계)라고 한다. 튜링은 ''결정 불가능성''에서 다음과 같이 적었다.

이 발견은 현재 당연하게 여겨지지만, 1936년 당시에는 놀라운 것으로 여겨졌다. 튜링이 "보편 기계"—"'''U'''"로 간략하게 표현한 계산 모델은 저장 프로그램 방식 컴퓨터의 개념을 이끌어낸 근본적인 이론적 돌파구로 여겨진다.

계산 복잡도 이론 측면에서 다중 테이프 보편 튜링 기계는 시뮬레이션하는 기계에 비해 로그 인자만큼만 느리면 된다. 이 결과는 1966년 F. C. 헤니와 R. E. 스턴스에 의해 얻어졌다.

규칙을 적절히 구성함으로써 "어떤 튜링 머신이든 이를 모방할 수 있는 튜링 머신(만능 튜링 머신)"이 가능하다. 만능 튜링 머신은 주어진 다른 튜링 머신을 기술한 기호열과 해당 튜링 머신에 대한 입력 기호열을 읽어 들여 이에 따라 작동한다. (에뮬레이터(컴퓨터)의 원리)

6. 튜링 기계와 실제 컴퓨터

튜링 기계는 실제 컴퓨터의 작동 방식을 추상화한 모델이다. 실제 컴퓨터는 유한한 메모리를 갖지만, 튜링 기계는 무한한 테이프를 가정하여 더 많은 데이터를 처리할 수 있다는 차이점이 있다. 튜링 기계는 알고리즘의 계산 복잡도를 분석하는 데 유용하게 사용된다.

튜링(1936)은 계산 과정에서 기계의 'm-배열'과 기계의 '진행 상태'를 명확히 구분했다. 튜링이 '상태식'이라고 표현한 것은 현재의 지시와 테이프 상의 모든 기호를 포함한다.^[17]

1936년 당시에는 튜링이 '범용 기계'라고 부른 이 계산 모델이 프로그램 내장식 컴퓨터의 기초적인 이론적 해결책을 제시했다는 평가를 받았다. 민스키(1967)는 튜링의 논문이 현대 컴퓨터와 관련된 일부 프로그래밍 기술의 발견을 서술하고 있다고 평가했다.^[18]

계산 복잡도 측면에서 보면 다중테이프 튜링 기계는 이 기계가 시뮬레이트하는 기계에 비해 로그 인수만큼 느려야 한다. 이 결과는 1966년에 F.C. 헨리와 R.E. 스턴에 의해 얻어졌다.

흔히 튜링 기계는 다른 오토마타와 다르게 실제 기계만큼 강력하고 실제 프로그램이 할 수 있는 연산을 모두 실행할 수 있다고 알려져 있다. 그러나 실제 기계는 유한한 개수의 배열만을 가질 수 있기 때문에 선형 구속 오토마타에 그친다는 점을 간과해서는 안 된다. 튜링 기계는 연산을 위한 무한한 저장 공간을 가진 기계이며, 컴퓨터가 아닌 연산 자체를 모델링한 것이다.

튜링 기계는 실제 컴퓨터가 연산할 수 있는 모든 것을 계산할 수 있고, 그 한계는 실제 컴퓨터에도 적용된다. 실제 컴퓨터와 튜링 기계의 차이는 처리할 수 있는 데이터의 양인데, 튜링 기계는 무한한 양의 데이터를 처리할 수 있는 반면 실제 컴퓨터는 유한한 양의 데이터만 처리할 수 있다. 그러나 유한한 시간 내에서 튜링 기계도 실제 기계처럼 유한한 양의 데이터만 조작 가능하다.

튜링 기계는 실제 컴퓨터를 모델링하는 데 유용하지만, 몇 가지 한계점도 존재한다. 운영 체제나 워드 프로세서처럼 시간에 따라 무한한 입력을 받아야 하는 경우에는 튜링 기계로 모델링하기 어렵다. 또한, 현대의 저장 프로그램 컴퓨터는 램덤 액세스 저장 프로그램 기계(RASP)의 일종으로, 튜링 기계와는 다른 메모리 구조를 가지고 있어, 튜링 기계로 모델링할 때 일부 알고리즘에 대해 잘못된 시간 복잡도 하한을 줄 수 있다.

계산의 산술 모형은 튜링 모형과 다음 두 가지 면에서 다르다.^[20]

• 산술 모형에서는 모든 실수에 단일 메모리 셀이 필요하지만, 튜링 모형에서는 실수의 저장 크기가 이를 나타내는 데 필요한 비트 수에 따라 달라진다.
• 산술 모형에서는 실수에 대한 모든 기본적인 산술 연산(덧셈, 뺄셈, 곱셈 및 나눗셈)을 단일 단계로 수행할 수 있지만, 튜링 모형에서는 각 산술 연산의 실행 시간이 피연산자의 길이에 따라 달라진다.

6. 1. 한계

7. 튜링 기계와 관련된 문제

앨런 튜링은 1936년에 "a-머신"(자동 기계)을 발명했으며,^[7] 튜링의 박사 과정 지도 교수인 앨런조 처치가 나중에 "튜링 기계"라는 용어를 만들었다.^[10] 튜링은 이 모델을 사용하여 일반적인 계산의 속성, 특히 ''결정 문제(Entscheidungsproblem)''의 계산 불가능성을 증명했다.^[13]

튜링은 임의의 계산을 수행할 수 있는 매우 단순한 장치의 수학적 설명을 제공했고, "이 기계가 0을 인쇄하는가?"라는 질문은 "결정 불가능"하다고 증명했다.

실제 계산기의 기본적인 동작은 튜링 기계의 원리를 따른다. "계산기로 원리상 풀 수 있는 문제"는 "튜링 기계로 풀 수 있는 문제"와 같다고 여겨지며, 알고리즘은 튜링 기계 상의 절차와 동일시될 수 있다(처치-튜링 명제).

수학의 형식 체계는 모두 튜링 기계의 동작으로 환원될 수 있으며, 이 기계로 결정할 수 없는 명제도 존재한다. 예를 들어, 주어진 튜링 기계가 정지하는지 여부를 튜링 기계로 결정하는 것은 불가능하다(정지 문제). 이는 괴델의 불완전성 정리의 또 다른 표현으로 간주될 수 있다.

7. 1. 정지 문제

• 테이프에 있는 임의의 기계가 "순환적"인지(예: 멈추거나 계산 작업을 계속하지 못하는 경우)를 결정할 수 있는 기계가 존재하는가?^[11][12]

7. 2. 결정 문제 (Entscheidungsproblem)

8. 현대적 응용

튜링 기계는 계산 이론, 복잡도 이론, 알고리즘 연구 등에서 여전히 중요한 역할을 하며, 컴퓨터 과학, 인공지능, 인지 과학 등 다양한 분야에 영향을 미쳤다.^[1] 앨런 튜링은 1937년 프린스턴에서 박사후 과정을 밟는 동안 전기-기계식 릴레이를 이용해 디지털(Boolean-logic) 곱셈 기계를 만들었다.^[2] 튜링의 발명은 단순한 호기심과 실험에서 시작되었지만, 독일과 미국에서도 비슷한 연구가 진행되었고, 그 결과물은 제2차 세계 대전 동안 연합국과 추축국의 군사 활동에 사용되었다.^[3]

1950년대 중반, 하오 왕과 마빈 민스키는 튜링 기계를 더 간단한 형태로 변형시켰다.^[4] 같은 시기 유럽의 연구자들은 최신 전자 컴퓨터를 튜링 기계와 같은 '컴퓨터와 같은 이론적 오브젝트'로 환원시켜 생각했다.^[5] 1950년대 후반에서 1960년대 초반, 멜자크와 레벡(1961), 민스키(1961), 셰퍼슨과 스터기스(1961) 등은 튜링 기계를 더 친숙하고 컴퓨터와 같은 '셈 기계(counter machine)'로 발전시켰다.^[6] 이후 1970년대 초반, 엘곳과 로빈슨(1964), 할트마니스(1971), 쿡과 렉하우(1973) 등은 이 연구를 더욱 발전시켜 '기록 기계(register machine)'와 RAM 모델의 기반을 마련했다.^[7]

오늘날 셈 기계, 기록 기계, RAM은 튜링 기계에 근간을 두고 있으며,^[8] 많은 연구자들이 계산 이론을 연구하는 데 튜링 기계를 활용한다.^[9] 특히 계산 복잡도 이론에서는 튜링 기계가 필수적으로 사용된다.^[10]

8. 1. 한국에서의 튜링 기계 연구

참조

_[1] 문서 Minsky 1967:107 "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols," also Stone 1972:8 where the word "machine" is in quotation marks.
_[2] 문서 Stone 1972:8 states "This "machine" is an abstract mathematical model", also cf. Sipser 2006:137ff that describes the "Turing machine model". Rogers 1987 (1967):13 refers to "Turing's characterization", Boolos Burgess and Jeffrey 2002:25 refers to a "specific kind of idealized machine".
_[3] 문서 Sipser 2006:137 "A Turing machine can do everything that a real computer can do".
_[4] 문서 Cf. Sipser 2002:137. Also, Rogers 1987 (1967):13 describes "a paper tape of infinite length in both directions". Minsky 1967:118 states "The tape is regarded as infinite in both directions". Boolos Burgess and Jeffrey 2002:25 include the possibility of "there is someone stationed at each end to add extra blank squares as needed".
_[5] 문서 Cf. Rogers 1987 (1967):13. Other authors use the word "square" e.g. Boolos Burgess Jeffrey 2002:35, Minsky 1967:117, Penrose 1989:37.
_[6] 문서 Boolos Burgess Jeffry 2002:25 illustrate the machine as moving along the tape. Penrose 1989:36-37 describes himself as "uncomfortable" with an infinite tape observing that it "might be hard to shift!"; he "prefer[s] to think of the tape as representing some external environment through which our finite device can move" and after observing that the " 'movement' is a convenient way of picturing things" and then suggests that "the device receives all its input from this environment. Some variations of the Turing machine model also allow the head to stay in the same position instead of moving or halting.
_[7] 서적 Alan Turing: The Enigma Princeton University Press
_[8] 문서 The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by [[M. H. A. Newman]] in his lectures: "Was there a definite method, or as Newman put it, a "mechanical process" which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its ''Proceedings'' (cf. Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf. Hodges 1983:129).
_[9] 문서 See footnote in Davis 2000:151.
_[10] 서적 The Collected Works of Alonzo Church https://mitpress.mit[...] MIT Press 2019-04-23
_[11] 문서 Turing 1936 in ''The Undecidable'' 1965:132-134; Turing's definition of "circular" is found on page 119.
_[12] 논문 On Computable Numbers, with an Application to the ''Entscheidungsproblem''
_[13] 문서 Turing 1936 in ''The Undecidable'' 1965:145
_[14] 문서 Sipser 2006:137 observes that "A Turing machine can do everything that a real computer can do. Nevertheless, even a Turing machine cannot solve certain problems. In a very real sense, these problems are beyond the theoretical limits of computation."
_[15] 문서 See the definition of "[[wikt:innings|innings]]" on [[Wiktionary]]
_[16] 간행물 Intelligent Machinery http://www.alanturin[...] 1948-07
_[17] 문서 Occasionally called an ''action table'' or ''[[transition system|transition function]]''.
_[18] 문서 Usually quintuples [5-tuples]: q_ia_j→q_i1a_j1d_k, but sometimes quadruples [4-tuples].
_[19] 문서 p.149; in particular, Hopcroft and Ullman assume that $\backslash delta$ is undefined on all states from $F$
_[20] 서적 Geometric algorithms and combinatorial optimization https://books.google[...] Springer-Verlag, Berlin
_[21] 문서 L. Torres Quevedo. ''Ensayos sobre Automática – Su definicion. Extension teórica de sus aplicaciones,'' Revista de la Academia de Ciencias Exacta, Revista 12, pp. 391–418, 1914.
_[22] 문서 Torres Quevedo. L. (1915). [https://diccan.com/dicoport/Torres.htm "Essais sur l'Automatique - Sa définition. Etendue théorique de ses applications"], ''Revue Génerale des Sciences Pures et Appliquées'', vol. 2, pp. 601–611.
_[23] 문서 The narrower question posed in [[Hilbert's tenth problem]], about [[Diophantine equation]]s, remains unresolved until 1970, when the relationship between [[recursively enumerable set]]s and [[Diophantine set]]s is finally laid bare.
_[24] 웹사이트 チューリングマシン 2022-02-02
_[25] 논문 On Computable Numbers, with an Application to the Entscheidungsproblem http://doi.wiley.com[...] 1937
_[26] 논문 Finite combinatory processes—formulation https://doi.org/10.2[...] Cambridge University Press
_[27] 문서 一般的には両方向にいくらでもシークできるものとするが、理論的には片方には端があっても良いのでそのように制限することもある。
_[28] 문서 あるいは単に停止する場合は、停止する前に、答えがどちらであるかを、テープ上の記号列として書き残してから停止する。
_[29] 문서 "1935년 중반, [[막스 뉴만]]은 그의 강의에서 \"과연 수학적 표현에 적용되어 그 표현이 증명될 수 있는지를 알려주는 명확한 방법이(뉴만은 이를 기계적 과정이라고 표현하였다.) 존재하는가?\"(호지스 1983:93) 라는 질문을 던졌다. 이 강의를 들고 튜링은 그 가상의 장치를 생각해내었다고 한다.(더 자세한 사실은 역사부분을 참조하시오) 그는 이 논문을 런던 수학회지에 1936년 5월 31일에 ''제출하였으나''(참고: 호지스 1983:112), 정작 이 논문이 ''출판된'' 것은 1937년 초였고, 그 해 2월이 다 돼서야 발췌 인쇄가 가능해졌다.(참고: 호지스 1983:129)"