튜링 기계 해설
전자 컴퓨터가 존재하기 전인 1936년, 24세의 수학자 앨런 튜링은 계산이 기계적이라는 것이 무슨 뜻인지 물었습니다. 그의 답은 이보다 더 적은 일을 하기 어려울 만큼 단순한 상상 속 기계였습니다. 고정된 규칙표에 따라 테이프 위에서 한 번에 한 칸씩 기호를 읽고 쓰는 기계입니다. 이 기계는 결국 계산 자체를 정의하게 되었고, 어떤 질문은 그 어떤 컴퓨터로도 결코 답할 수 없음을 보여 주었습니다.
튜링의 질문
1928년 다비트 힐베르트는 수학의 모든 명제에 대해 그것이 증명 가능한지를 판정하는 기계적 절차가 있는지 물었습니다. 이것이 결정 문제(Entscheidungsproblem)입니다. 이에 답하려면 누군가가 기계적 절차가 정확히 무엇인지 말해야 했습니다. 1936년 논문 「계산 가능한 수에 대하여」(On Computable Numbers)에서 튜링은 연필과 종이로 일하는 계산원을 상상하고, 그 일을 가장 작은 단계로 쪼갰습니다. 기호 하나를 보고, 그것을 바꾸고, 이웃한 기호로 옮겨 가고, 자신이 무엇을 하고 있었는지 조금 기억하는 것입니다. 그 결과가 튜링 기계입니다.
기계
튜링 기계에는 칸으로 나뉜 테이프가 있는데, 양방향으로 끝없이 이어지며 각 칸에는 기호가 하나씩, 대개는 빈칸이 들어 있습니다. 헤드는 한 칸 위에 있고, 기계는 유한한 상태 중 하나에 있습니다. 규칙표는 각 상태와 헤드가 읽을 수 있는 각 기호에 대해 쓸 기호, 움직일 방향, 다음 상태를 정해 줍니다. 기계는 한 단계에 규칙 하나를 적용합니다. 정지 상태에 들어가면 멈추고, 테이프에 남은 것이 그 답이 됩니다.
규칙표로서의 프로그램
규칙표 하나하나가 프로그램입니다. 이진수에 1을 더하려면 기계는 수의 오른쪽 끝까지 간 다음, 왼쪽으로 움직이며 1을 0으로 바꾸다가 0이나 빈칸을 만나면 그것을 1로 바꿉니다. 단어가 회문인지 확인하려면 첫 기호를 지우고 상태에 기억해 둔 채 반대쪽 끝까지 달려가 마지막 기호가 일치하는지 확인하고, 이를 반복합니다. 곱셈이나 정렬을 하는 프로그램처럼 긴 프로그램도 같은 몇 가지 종류의 규칙으로 만들어집니다.
만능 기계
튜링의 가장 중요한 아이디어는 규칙표 자체를 테이프에 쓸 수 있다는 것이었습니다. 만능 튜링 기계는 다른 아무 기계의 설명과 그 입력을 읽은 다음, 그 기계를 한 단계씩 흉내 냅니다. 따라서 고정된 기계 하나로 모든 프로그램을 실행할 수 있습니다. 이것은 소프트웨어가 메모리 속 데이터일 뿐인 모든 프로그램 내장식 컴퓨터의 바탕에 있는 원리입니다. 만능 튜링 기계를 흉내 낼 수 있는 시스템을 튜링 완전하다고 하며, 모든 프로그래밍 언어, 콘웨이의 생명 게임, 세포 자동자 규칙 110이 여기에 속합니다.
처치-튜링 논제
같은 해 알론조 처치는 람다 대수로 계산을 기술했는데, 두 정의가 정확히 같은 함수들을 계산한다는 사실이 밝혀졌습니다. 레지스터 기계에서 현대 프로세서에 이르기까지 이후의 모든 모델도 마찬가지였습니다. 처치-튜링 논제는 단계적 절차로 계산할 수 있는 것은 무엇이든 튜링 기계로 계산할 수 있다고 말합니다. '단계적 절차'는 비형식적인 개념이므로 이 논제는 증명할 수 없지만, 반례는 지금까지 한 번도 발견되지 않았습니다.
정지 문제
튜링은 이어서 어떤 질문에는 기계적인 답이 없음을 보였습니다. 모든 프로그램과 입력에 대해 그 프로그램이 결국 멈추는지를 판정할 수 있는 기계가 있다고 가정해 봅시다. 이 판정기에게 자기 자신에 대해 묻고 그 반대로 행동하는 새 프로그램을 만듭니다. 멈춘다는 답을 들으면 영원히 반복하고, 반복한다는 답을 들으면 멈추는 것입니다. 어느 답이든 틀리게 되므로 그런 판정기는 존재할 수 없습니다. 정지 문제는 결정 불가능하며, 그와 함께 결정 문제도 결정 불가능합니다. 어떤 알고리즘도 모든 수학적 질문을 해결할 수는 없습니다.
바쁜 비버
1962년 티보르 라도는 정지 문제를 하나의 게임으로 바꾸었습니다. 상태가 n개이고 기호 0과 1을 쓰며 빈 테이프에서 시작하면 멈추는 모든 기계 중에서, 1을 가장 많이 쓰는 기계는 무엇이며 그런 기계는 최대 몇 단계를 실행할 수 있을까요? 이 수들, 즉 바쁜 비버 값은 어떤 계산 가능한 함수보다도 빠르게 커집니다. 그것을 계산하는 방법이 있다면 정지 문제를 풀 수 있게 되기 때문입니다. 알려진 값은 2상태, 3상태, 4상태에서 각각 6, 21, 107단계입니다. 5상태에서는 하이너 마르크센(Heiner Marxen)과 위르겐 분트로크(Jürgen Buntrock)의 챔피언이 47,176,870단계를 실행하며, 이 값은 2024년 온라인 공동 작업 bbchallenge가 컴퓨터로 검증한 증명을 통해 확정되었습니다. 6상태에서는 일반적인 표기법으로는 적을 수 없을 만큼 많은 단계를 실행하는 기계들이 알려져 있습니다.
직접 탐험하기
튜링 기계 시뮬레이터를 열어 준비된 프로그램 여덟 개를 실행하거나 직접 프로그램을 작성해 보세요. 헤드를 한 단계씩 따라가며 어떤 규칙이 실행되는지 보고, 멈추지 않는 카운터를 지켜보고, 회문을 검사하고, 바쁜 비버를 실행해 보세요. 4상태 챔피언의 107단계는 다이어그램에 다 들어가고, 5상태 챔피언의 4700만 단계는 가장 빠른 속도에서 몇 초면 끝납니다.
자주 묻는 질문
튜링 기계가 실제로 만들어진 적이 있나요?
테이프가 끝없이 이어지므로 튜링이 기술한 그대로 만들어진 적은 없습니다. 하지만 이 아이디어가 나온 뒤 곧 실제 프로그램 내장식 컴퓨터들이 등장했고, 튜링 자신도 제2차 세계 대전 후 그 설계를 도왔습니다. 그 뒤로 애호가들이 나무, 레고, 심지어 생명 게임으로도 작동하는 모형을 만들었습니다. 모두 테이프가 유한하지만, 끝나는 계산이라면 어떤 것이든 그것으로 충분합니다.
3상태의 단계 수 14와 21은 무엇이 다른가요?
바쁜 비버 질문은 두 가지입니다. 1을 가장 많이 쓰는 것과 단계를 가장 많이 실행하는 것입니다. 3상태의 경우 시뮬레이터에 있는 기계는 14단계에 최대치인 1 여섯 개를 쓰고, 다른 3상태 기계는 최대치인 21단계를 실행하지만 1을 다섯 개만 남깁니다. 2상태, 4상태, 5상태에서는 한 기계가 두 부문 모두에서 이깁니다.
튜링 완전하다는 것은 강력하다는 뜻인가요?
충분한 시간과 메모리가 주어지면 계산 가능한 것은 무엇이든 계산할 수 있다는 뜻이며, 속도에 대해서는 아무것도 말해 주지 않습니다. 튜링 기계는 간단한 산수에도 많은 단계가 필요하고, 카드 게임, 스프레드시트 수식, 마인크래프트 레드스톤처럼 거의 우연히 튜링 완전해진 시스템도 있습니다.
컴퓨터로 프로그램을 그냥 실행해서 멈추는지 보면 안 되나요?
실행해 보면 프로그램이 멈출 경우 멈춘다는 것은 알 수 있습니다. 하지만 아직 멈추지 않았다면, 영원히 멈추지 않을지 아니면 시간이 더 필요할 뿐인지 알 수 없습니다. 튜링의 증명은 모든 프로그램에 통하는 더 영리한 방법도 없다는 것을 보여 줍니다. 다만 많은 개별 프로그램에 대해서는 이 질문에 답할 수 있습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
튜링 기계 시뮬레이터 열기