컴퓨터과학이 여는 세계 2강

sith-call.dev·2022년 2월 19일

컴퓨터과학이 여는 세계

목록 보기

2/4

튜링 기계

튜링 기계 : 튜링이 자신의 논문에서 수리명제 자동판결 문제가 풀릴 수 없음을 증명하기 위해 구상한 기계

튜링은 몇 가지 추론 규칙을 기계적인 방식으로 조합하여 이 세상 모든 참인 수리 명제를 만들어낼 수 있다는 수리 명제 자동 판결 문제는 풀 수 없는 것임을 증명한다. 이는 괴델이 이미 한번 증명한 것이지만, 자신만의 방식으로 재증명한 것이다.

튜링의 증명을 따라가기 위해선 먼저 수리 명제 자동 판결 문제가 무엇인지부터 제대로 알고 가야 한다.

수리 명제 자동 판결 문제 : 이 세상 모든 참인 명제를 기계적인 방식으로 자동적으로 찾아낼 수 있는지 여부를 따지는 문제

이때 주목할 지점은 바로 “기계적 방식”이다. 튜링은 이 기계적 방식이란 무엇인지 정의내린다. 그리고 자신의 정의가 꽤나 보편적임을 다양한 계산을 시켜봄으로써 보여준다.

그리고 이 기계적인 방식을 정의하기 위해 고안한 가상의 기계가 존재하는데, 이것이 이후에 컴퓨터라고 불리는 것의 초안이 된다.

즉 다시 말하자면, 먼저 자신이 고안한 가상의 기계가 충분히 기계적인 방식의 정의가 될 만큼 보편적인 성능을 가짐을 보여준다.

그리고 이 기계가 기계적인 방식으로서 유효함을 보여줬기에, 기계의 한계가 곧 기계적 방식의 한계가 된다.

그렇기 때문에 튜링이 고안한 가상의 기계가 이 세상 모든 참인 수리 명제를 만들어낼 수 있다면, 수리 명제 자동 판결 문제는 풀리게 될 것이고, 그렇지 않다면 해당 문제는 절대로 풀리지 않는 것임을 나타낼 수 있는 것이다.

이렇게까지 논리의 흐름을 끌고간 뒤에, 튜링은 논문에서 해당 기계가 풀어낼 수 없는 문제를 제시하여 증명을 완료한다.

Universal Machine(a Turing Machine)

튜링 머신을 만든다는 것

튜링 머신의 구성은 다음과 같다.

무한한 테이프
유한한 기호들
유한한 규칙들
읽기, 쓰기 동작과 상태를 가진 기계

💡 여기서 궁금한 점은 튜링 기계의 구성이 현재 컴퓨터의 어떤 부분과 대응이 되는 걸까? 즉, 튜링 기계가 어떻게 발전해서 현재의 컴퓨터의 모습이 되었는 지가 궁금하다.

그런데 튜링머신에서 사용하는 언어를 프로그래밍할 때 사용하지는 않는다. 왜냐하면 너무 Low Level의 언어이기 때문이다.

“3. Examples of computing machines”

수를 복사하는 튜링 머신을 구현하기 위해서는 마커라는 부품이 추가된다.

그런데 이 마커 또한 튜링 머신의 정의대로 구현할 수 있다.

즉, 마커라는 부품은 튜링 머신의 규칙표로부터 추상화된 부품인 것이다.

그래서 수업에서 이제는 마커를 자유자재로 쓸 예정이다.

또한 마커의 종류도 2 가지나 된다.

기호가 원래는 한 칸만을 차지했는데, 이것을 두 칸을 차지하게 하면 한 칸은 기호, 한 칸은 마커를 두면 이를 통해 마커라는 부품을 튜링 머신의 정의대로 구현할 수 있다. 만약에 마커의 개수가 늘어나게 되면, 단지 기호의 칸의 개수를 더 추가해주면 된다.

수업에서는 다음의 튜링 기계가 나왔다.

0,1을 반복하는 튜링 기계
주어진 수를 복사하는 튜링 기계 - 중요

이 기계같은 경우에는 마커라는 특수한 부품이 추가된다.

그러나 마커 또한 튜링 머신의 정의 안에서 구현 가능한 부품이다.

단순하게 기호가 차지하는 기본칸의 개수를 마커의 수만큼 늘려주고, 그 추가된 칸에 마커를 위치시키면 된다. 그러면 그 추가된 기호가 추상화되어서 마커라는 부품으로 표현가능하게 된다.

https://youtu.be/3XiiN7HfN9M?list=PL0Nf1KJu6Ui7yoc9RQ2TiiYL9Z0MKoggH&t=319

위와 같은 규칙표(링크에서 확인 가능)가 카피를 하는 튜링 기계의 것이다.

여기서 규칙표를 설계하는 과정을 살펴보면, A,B,C의 상태마다 역할이 존재함을 알 수 있다.

A : 복사 준비

B : 복사

C : 복사 종료

그래서 위의 역할을 염두하고 순차적으로 주어진 상황에 맞춰 규칙표를 만들어가면 매우 쉽게 규칙표를 만들어낼 수 있다.

마커를 1개 사용한다.
1을 더해주는 튜링 기계

카피하는 튜링 기계를 이용한다.

이때 준비하는 단계에서 먼저 1을 추가해준 뒤에 주어진 수를 복사하면, 1을 더해주는 튜링 기계를 만들 수 있다.

마커를 1개 사용한다.
두 수를 더해주는 튜링 기계

카피만 할 수 있다면, 더하는 것도 구현할 수 있다.

이는 단순하게 1진수로 표현된 수를 2번 복사하면 구현할 수 있다.

마커를 1개 사용한다.
두 수를 곱해주는 튜링 기계

이 또한 복사만 할 줄 알면 구현할 수 있다.

단순하게 주어진 수만큼 다른 수를 여러 번 복사해주면 되는 것이다.

그런데 이것을 좀 더 편하게 구현하기 위해서 마커를 2개 사용한다.

처치-튜링 명제(처치의 가정)

간단히 요약하면, 어떤 함수는 튜링 기계가 계산할 수 있으면, 그리고 그 때만 알고리즘으로 계산 가능하다는 명제이다. [위치백과, 처치-튜링 명제]

튜링 기계는 모든 범용 프로그래밍 언어로 번역될 수 있으므로, 이것은 어떤 컴퓨터에게든 충분한 시간과 메모리가 주어진다면 존재하는 모든 알고리즘의 결과를 출력할 수 있다는 명제와 동치이다. [위치백과, 처치-튜링 명제]

처치의 가정은 튜링 머신보다 더 처리력이 우수한 컴퓨터 구조는 있을 수 없다고 말하고 있다. 이는 달리 표현하면 알고리즘에 의해 풀리는 문제들은 그것을 푸기 위해 채택하는 컴퓨터 체계와는 무관하다는 의미이다. 개념적으로는 어떠한 문제가 현대의 고성능 슈퍼컴퓨터에 의해 풀릴 경우, 이는 개인용 컴퓨터에 의해서도 풀릴 수 있으며, 또한 튜링 머신에서도 풀릴 수 있다는 의미가 된다. from[운영체제와 정보기술의 원리,p.23]

현재의 디지털 컴퓨터는 튜링 머신의 성능에서 벗어나지 못한다. 지금까지 나온 모든 소프트웨어는 튜링 머신에서도 구현 가능하다. from[컴퓨터과학이 여는 세계 2.3]

처치-튜링 논제 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

“4. Abbreviated tables”

“skeleton tables”: 반복해서 사용할 라이브러리/서브루틴 룰들

아까 사용했던 마커와 같은 것들을 말한다.

“5. Enumeration of computable sequence”

튜링기계마다 자연수 하나로 표현가능.

(강의자료 Part1 22쪽)

즉, 위와 같이 튜링 기계의 규칙표(언급된 강의자료에서 확인)가 있다고 해보자. 이때, 이 규칙들을 전부 일렬로 나열할 수 있고, 각각의 규칙은 X와 같은 Delemeter로 구분시킬 수 있다. 그리하여 결국은 어떤 규칙표더라도 하나의 줄로 표현할 수 있게 된다. 근데 모든 문자들을 n진수(n은 모든 기호의 개수)로 표현하게 되면 튜링 기계의 규칙표를 하나의 자연수와 대응시킬 수 있게 된다.

그러면 규칙표뿐만 아니라, 상태, 테이프까지 각각 하나의 자연수로 대응시킬 수 있다.

그래서 튜링 기계는 자연수 3개로 대응된다. 이때 3개의 자연수를 하나의 자연수로 Unique하게 대응시킬 수 있다.

$N_1,N_2,N_3$ 이 규칙표, 테이프, 상태를 자연수에 대응시킨 것이라면,

그 해당 튜링 기계는 $2^{N_!} \times 3^{N_2} \times5^{N_3}$ 와 같은 수로 대응시킬 수 있다.

그래서 중요한 점은 다음과 같다.

결국에 하나의 튜링 머신은 하나의 자연수이다. 그래서 하나의 튜링 머신을 다른 임의의 튜링 머신에 수로서 입력할 수 있다.
튜링 머신은 하나의 자연수로 일대일대응시킬 수 있음을 보였다. 이는 모든 튜링 머신의 수와 자연수의 개수는 서로 같다고 밝힌 것과 같다.

그러나 이때 무한에도 급이 존재한다. 즉, 자연수의 개수와 실수의 개수가 다르다. 그렇기에 튜링 머신의 개수가 자연수의 개수로 제한되어 있음을 밝힌 것이다. 이 사실이 매우 중요하다. 왜냐하면 이것이 튜링 머신의 급소이기 때문이다! 이 성질을 이용해서 튜링은 괴델의 불완전성 원리를 증명한다.

소프트웨어는 튜링 머신과 일대일 대응 관계이다. 그리고 튜링 머신은 자연수와 일대일 대응 관계이다. 그래서 이 세상의 소프트웨어의 개수는 자연수의 개수를 초과할 수 없다. 이러한 한계 때문에 튜링 기계로는 이 세상의 모든 참인 명제를 밝혀내지 못한다.

괴델 수 대응

하나의 튜링 머신을 하나의 자연수로 맵핑시킬 때 사용하는 개념이다.

괴델의 불완전성 정리 (jinseob2kim.github.io)

초한기수

무한 사이에도 급이 존재한다. 그러나 무한과 관련한 내용은 직관에서 벗어나는 경우가 많다. 그래서 철저하게 논리에 입각한 연역논증의 흐름을 따라가야 한다. 아무리 비직관적인 결과가 나온다고 해도 철저히 연역적인 추론을 했으므로 이해할 수 있게 된다.

초한기수 - 나무위키 (namu.wiki)

“6. The universal computing machine”, “7. Detailed description of the universal machine”

자연수로서 임의의 튜링 기계를 입력하면 입력 받은 튜링 기계는 그 튜링 기계를 모방할 수 있다. 그런데 이런 일을 하는 것이 바로 컴퓨터이다. 즉, 어떤 소프트웨어를 내 컴퓨터에 입력하면 컴퓨터가 그것을 실행하는 행위 자체가 튜링 머신에 튜링 머신을 입력하여 입력 받은 튜링 머신이 그 튜링 머신을 따라하는 것과 동일한 것이다.