튜링 기계(Turing machine)
칸이 끝없이 이어진 테이프, 한 칸을 읽고 쓰는 헤드, 유한한 상태표만으로 '기계적인 계산'을 정의한 가상의 기계. 보편 튜링 기계(universal Turing machine)는 다른 모든 튜링 기계를 흉내 낸다.
1936년 앨런 튜링은 '기계적으로 계산한다'는 말을 정확히 정의하려고, 종이와 연필로 계산하는 사람을 극단까지 단순하게 만들었습니다. 칸이 한 줄로 끝없이 이어진 테이프, 한 번에 한 칸만 읽고 쓰는 헤드, 그리고 유한한 개수의 상태가 전부입니다. 기계의 프로그램은 표 하나입니다. 표의 한 칸은 "(지금 상태 q, 읽은 기호 s) → (쓸 기호 s′, 움직일 방향 d, 다음 상태 q′)"라는 규칙이고, 기계는 정지 상태에 닿을 때까지 이 규칙을 되풀이합니다. 방향 d는 왼쪽(L)이나 오른쪽(R)입니다. 아래 그림의 기계들은 편의상 제자리(–)도 쓰는데, 이것을 허용해도 계산할 수 있는 것은 달라지지 않습니다. 이렇게 초라한 기계가, 지금까지 알려진 어떤 컴퓨터가 하는 계산이든 (시간과 테이프만 넉넉하면) 모두 해냅니다. 이것이 계산의 정의로 받아들여지는 까닭은 처치–튜링 논제(Church–Turing thesis)에서 다룹니다.
기계를
이진수에 1 더하기는 오른쪽 끝까지 간 다음, 1을 0으로 바꾸며 받아올림을 왼쪽으로 넘기다가 0이나 빈칸을 만나면 1을 쓰고 멈춥니다. 이진법(binary)의 받아올림 그대로입니다. 회문 검사는 abba처럼 앞에서 읽으나 뒤에서 읽으나 같은 문자열(회문)인지 가립니다. 맨 앞 글자를 지우고 그 글자를 상태로 기억한 채(a→, b→) 오른쪽 끝으로 가서 마지막 글자와 비교합니다. 헤드가 테이프를 계속 오가므로 길이 n인 입력에 대략 n²에 비례하는 걸음이 듭니다. 알고리즘(algorithm)의 빠르기를 이런 걸음 수로 재는 것이 P 대 NP 문제(P versus NP problem)의 출발점입니다.
바쁜 비버(busy beaver)는 기호 0과 1만 쓰는 n상태 기계 가운데, 빈 테이프에서 출발해 언젠가 멈추면서 1을 가장 많이 남기는 기계입니다. 상태가 셋이면 최대 6개이고, 위의 기계가 그런 기계입니다(14걸음 만에 멈춥니다). 남기는 1의 개수 대신 멈출 때까지 걸리는 걸음 수의 최댓값을 물어도 됩니다. 이런 최댓값들은 n이 커질수록 어떤 계산 가능한 함수(function)보다도 결국 빨리 자랍니다(헝가리 태생의 미국 수학자 티보르 라도, 1962). 여기서 계산 가능한 함수란 n을 입력받아 그 값을 적고 멈추는 튜링 기계가 있는 함수를 말합니다. 핵심은 계산 가능한 함수로는 이 최댓값을 위에서 막을 수조차 없다는 데 있습니다. 만약 모든 n에서 걸음 수의 최댓값 이상인 수를 계산해 내는 기계가 있다면, n상태 기계를 빈 테이프에서 그 걸음만큼 돌려 보고 그때까지 멈추지 않으면 영원히 돈다고 판정할 수 있게 됩니다. 멈추는 기계와 영원히 도는 기계를 이렇게 가려내는 일은 정지 문제(halting problem) 때문에 불가능합니다. 다섯 상태의 경우 가장 오래 달리는 기계가 47,176,870걸음 만에 멈춘다는 사실은 2024년에야 온라인 공동 연구 모임(bbchallenge)의 작업과 컴퓨터 증명 검증으로 확정되었습니다.
튜링의 가장 큰 발견은 보편 튜링 기계입니다. 상태표도 기호열로 적어 테이프에 올릴 수 있으니, 다른 기계의 표와 입력을 테이프에서 읽어 그 기계가 할 일을 한 걸음씩 흉내 내는 기계 하나를 만들 수 있습니다. 프로그램을 데이터처럼 메모리에 넣어 두는 오늘날 컴퓨터의 발상, 흔히 폰 노이만의 이름으로 불리는 내장 프로그램 방식(stored-program concept)과 같은 생각이 이 기계에 이미 들어 있습니다. 또 기계는 모두 유한한 기호열로 적히니 기계 전체는 가산개뿐이고, 자릿수를 계산해 낼 수 있는 실수(real number)도 가산개뿐입니다. 그런데 실수는 셀 수 없이 많으므로(대각선 논법(diagonal argument)) 나머지 셀 수 없이 많은 실수는 어떤 기계로도 자릿수를 계산해 낼 수 없습니다. 튜링의 1936년 논문 제목이 바로 「계산 가능한 수(computable number)에 대하여」였습니다.
이어지는 곳. 튜링 기계에서 힘을 덜어 내면 더 약한 기계들이 나옵니다. 테이프에 쓰지 못하고 한 방향으로 읽기만 하는 기계가 유한 오토마톤(finite automaton)입니다. 쓸 수 있는 칸을 입력이 차지한 칸으로 제한한 기계(선형 유계 오토마톤, linear bounded automaton)는 문맥 의존 언어(context-sensitive language)를 인식하는데, 예를 들어 aⁿbⁿcⁿ처럼 a, b, c 세 덩어리의 길이가 모두 같은 문자열들을 알아봅니다. 기계의 힘에 따라 나뉘는 이 층들이 촘스키 위계(Chomsky hierarchy)입니다. 같은 1936년 알론조 처치는 전혀 다른 람다 계산(lambda calculus)으로 같은 개념에 이르렀고, 둘이 같다는 사실이 처치–튜링 논제의 근거가 되었습니다. 튜링은 이 논문에서 힐베르트의 결정 문제(decision problem)가 풀릴 수 없음도 보였습니다. 결정 문제는 1차 논리(first-order logic)로 적은 문장이 주어지면, 그 문장이 논리 법칙만으로 증명되는지를 기계적으로 가리는 방법을 찾으라는 문제입니다. 처치도 몇 달 앞서 따로 같은 결론에 이르렀습니다. 괴델이 '증명할 수 없는 참'이 있음을 보였다면 튜링은 '기계적으로 판정할 수 없는 문제'가 있음을 보인 것이라, 괴델의 불완전성 정리(Gödel's incompleteness theorems)와 짝을 이루는 결과입니다. 튜링 기계는 '알고리즘'이라는 말에 정확한 뜻을 준 모형 가운데 가장 설득력 있는 것으로 꼽힙니다. 보편 기계(universal machine) 하나를 정해 두고, 그 기계에 넣어 어떤 문자열을 출력하게 하는 가장 짧은 프로그램의 길이가 그 문자열의 콜모고로프 복잡도(Kolmogorov complexity)입니다.
이 개념이 나오는 긴 글
이 개념 위에 세워진 것
이 개념을 언급하는 페이지
- 함수
… 알론조 처치가 만든 람다 계산은 함수를 만드는 일과 함수에 값을 넣는 일, 이 두 가지만으로튜링 기계가 할 수 있는 모든 계산을 적을 수 있음을 보여 줍니다. 여기에 모든 변수와 함수에 종류(타입, 예: …
- 가산 집합
… 셀 수 없이 많으니, 어떤 문법이나 프로그램으로도 적을 수 없는 언어가 반드시 있습니다(촘스키 위계,튜링 기계).
- 진법
… 그 수가 3의 배수인지 알 수 있습니다. 상태가 셋뿐인 유한 오토마톤입니다. 2진수에 1을 더하는 일은튜링 기계의 첫 번째 예제로 자주 쓰입니다. 매번 바뀌는 끝자리와 드물게 바뀌는 앞자리를 함께 읽어 수를 정한다는 …
- 그래프
… 단순한 규칙 가운데 '규칙 110'이라 불리는 것 하나가 (끝없이 긴 줄에 알맞은 처음 무늬를 깔아 두면)튜링 기계가 할 수 있는 모든 계산을 흉내 낼 수 있습니다. 미국의 수학자 매슈 쿡이 증명해 2004년에 …
- 불 대수
… 없습니다. 출력을 입력으로 되먹여 상태를 기억하게 하면 유한 오토마톤이 되고, 끝없는 테이프를 붙이면튜링 기계가 됩니다. 함수만으로 계산을 적는 람다 계산에서는 참과 거짓조차 '둘 중 하나를 고르는 함수'로 …
- 괴델의 불완전성 정리
… 들어 'A'와 'A이면 B'에서 'B'를 얻는 규칙)이 분명하게 정해져 있어서, 주어진 증명이 맞는지를기계가 검사할 수 있는 체계입니다. 대표적인 예가 0, '다음 수', 덧셈, 곱셈에 관한 몇 가지 공리와 …
- 정지 문제
… 오늘날의 '멈추는가' 형태와 이름은 1950년대에 자리 잡았지만, 논증은 같습니다. 여기서 프로그램은튜링 기계든 파이썬 같은 범용 프로그래밍 언어든 상관없습니다. 메모리에 한계가 없다고 치면 둘은 서로를 흉내 낼 수 …
- 람다 계산
… 자유 문법⟧으로 적힙니다. 이어지는 곳. 1936–37년 튜링은 람다로 정의할 수 있는 함수와튜링 기계로 계산할 수 있는 함수가 정확히 같음을 보였고, 이것이 처치–튜링 논제의 기둥이 되었습니다. 계산을 …
- 처치–튜링 논제
… '조건을 만족하는 가장 작은 수 찾기'만으로 만들어지는 자연수 함수입니다. 여기에 튜링의튜링 기계, 그리고 미국의 에밀 포스트가 따로 구상한 비슷한 기계가 더해졌습니다. 출발점은 제각각이었는데, 곧 …
- P 대 NP 문제
… 뜻입니다. 이런 성장 속도를 상수배를 무시하고 O(n^2) 처럼 적는 것이 점근 표기법입니다. 걸음은튜링 기계의 걸음으로 재지만, 어떤 합리적인 계산 모형을 써도 결론은 같습니다. 빠르게 풀 수 있으면 확인도 빠르니 …
- 유한 오토마톤
… 아니면 거부합니다. 되돌아가 다시 읽을 수도, 어디에 적어 둘 수도 없다는 점에서 테이프에 쓰고 오가는튜링 기계보다 훨씬 약합니다. 그림으로는 상태가 꼭짓점이고 전이가 기호를 단 화살표인 방향 그래프입니다. …
- 촘스키 위계
… 됩니다. 입력이 적힌 칸만큼의 테이프를 읽고 쓸 수 있게 하면 선형 유계 오토마톤, 테이프에 끝이 없으면튜링 기계가 됩니다. 여기서 기계들은 갈림길에서 여러 길을 동시에 시도할 수 있는(비결정적) 기계로 봅니다. 유한 …
- 문맥 자유 문법
… 바꿀 수 있다'는 규칙입니다(γ는 빈 문자열이 아니어야 합니다). 규칙에 어떤 제한도 두지 않으면 문법은튜링 기계와 같은 힘을 가집니다.
- 알고리즘
… 일입니다. 영국의 튜링은 기호가 적힌 긴 테이프를 한 칸씩 읽고 쓰며 움직이는 가상의 기계, 곧튜링 기계로 절차를 정의했습니다. 미국의 논리학자 처치는 함수를 만들고 적용하는 규칙만으로 계산을 적는 ⟦람다 …
- 콜모고로프 복잡도
… 차이틴은 각자 이 차이를 수로 만들었습니다. 문자열 x의 콜모고로프 복잡도 K(x) 는 고정된 보편튜링 기계U에서 x를 출력하고 멈추는 가장 짧은 프로그램의 길이입니다. 보편 튜링 기계는 다른 어떤 튜링 기계든 …
- 맥스웰의 악마와 란다우어 원리
… 되돌릴 수 있는 계산만 쓰면 원리적으로는 지우기 없이 계산할 수 있다는 것도 베넷이 1973년에튜링 기계로 보였습니다. 이어지는 곳. 미시 상태들의 확률분포 하나에 대해 정의한 열역학의 엔트로피(깁스 …
- 수학 기초론 논쟁
… 기계적으로 판정하는 방법이 있는가(결정 문제)에 '없다'고 답하면서, 계산이란 무엇인지를 정의했습니다(튜링 기계, 람다 계산, 처치–튜링 논제). 같은 해 독일의 게르하르트 겐첸은 유한한 방법보다 조금 강한 …
- 기술 집합론
… 개념을 실수 너머로 넓힌 것이 위상수학입니다. 논리의 '어떤'과 '모든'이 집합의 층이 되는 모습은튜링 기계와 정지 문제에서 계산 가능성의 층을 세는 방식과도 닮았으며, 둘 다 자기 참조와 대각선과 ⟦무한을 …
- 기계 학습
… 원리는 가장 좋은 것 고르기에서 이어집니다. 기계가 무엇을 계산할 수 있는지라는 더 오래된 질문은튜링 기계에서 시작합니다. 2022년 이후 큰 언어 모델에서 일어난 일은 언어 모델의 발전사에 날짜순으로 …
- 인공지능
… 무엇을 계산할 수 있는가. 기계가 원리적으로 무엇을 계산할 수 있고 없는지라는 더 밑바닥의 질문은튜링 기계, 정지 문제, 처치–튜링 논제에 있습니다. 이 위키의 AI 페이지들. 표에서 배우는 고전적인 …
- 타입 이론
… 그 대가로 모든 계산을 표현하지는 못합니다. 자연수 같은 자료에 끝나지 않을 수도 있는 되부름까지 넣으면튜링 기계만큼 강해지지만, 끝남의 보장과 논리로서의 무모순성을 함께 잃습니다. 항에 타입을 적는 방식은 둘입니다. …
- 단순 타입 람다 계산
… 타입이 없는 람다 계산에서는 이런 귀납을 걸 곳이 없습니다. 대가도 분명합니다. 모든 계산이 끝나는 언어는튜링 기계만큼 강할 수 없습니다. 이유는 정지 문제와 같은 대각선 논법입니다. 프로그램이 모두 끝나고, …
- 직관주의 논리
… 커리–하워드 대응의 표와 한 줄씩 같습니다. 그러면 배중률에 프로그램이 없는 까닭이 보입니다. 모든튜링 기계M에 대해 'M은 멈춘다 또는 M은 멈추지 않는다'의 증명이 있다면, 그 증명은 M을 받아 어느 쪽인지를 …