계산 가능성: 튜링 기계와 결정 불가능한 문제
테이프 한 줄과 상태 몇 개뿐인 튜링 기계를 직접 만들어 2진수에 1을 더하고, 문맥 자유 문법으로는 못 하던 a, b, c 개수 맞추기를 해내는 모습을 확인해요. 튜링 기계로 계산할 수 있는 것이 곧 알고리즘으로 계산할 수 있는 것이라는 처치-튜링 논제와 프로그램을 데이터로 받는 범용 튜링 기계를 다루고, 어떤 판별기를 가져와도 그것을 속이는 프로그램을 만들어 정지 문제를 풀 수 없음을 보여요. 끝나는지 아무도 모르는 콜라츠 반복, 라이스 정리가 말하는 정적 분석 도구의 한계까지 짚어요.
유한 오토마타에 스택을 더하니 괄호를 셀 수 있었어요. 하지만 문맥 자유 문법도 a, b, c를 똑같이 n개씩 쓴 문자열은 다루지 못했어요. 1936년 앨런 튜링은 더 근본적인 질문을 던졌어요. "기계적으로 계산한다는 건 정확히 무엇인가?" 그의 답인 튜링 기계는 지난 강의에서 본 계층의 꼭대기에 있고, 지금 우리가 쓰는 모든 컴퓨터의 이론적인 모형이에요. 이번 강의에서는 튜링 기계를 직접 만들고, 이 기계로도, 즉 어떤 컴퓨터로도 절대 풀 수 없는 문제가 있다는 사실을 증명해요.
튜링 기계: 테이프 한 줄과 상태 몇 개
튜링 기계는 사람이 종이와 연필로 계산하는 모습을 가장 단순하게 줄인 거예요.
- 양쪽으로 끝없이 이어진 테이프가 칸으로 나뉘어 있고, 칸마다 기호가 하나씩 적혀 있어요. 빈칸도 기호 하나(여기서는
_)로 쳐요. - 헤드가 한 칸을 가리키며 그 칸의 기호를 읽어요.
- 기계는 상태 하나를 기억해요.
- 규칙표는 (지금 상태, 읽은 기호)마다 무엇을 쓰고, 왼쪽과 오른쪽 중 어디로 움직이고, 어떤 상태가 될지를 정해요.
유한 오토마타와 다른 점은 테이프에 쓸 수 있고, 되돌아갈 수 있고, 테이프가 끝이 없다는 거예요. 이것만으로 충분히 강해요. 2진수에 1을 더하는 기계부터 만들어 볼게요.
def run_tm(rules, tape, state="start", blank="_", max_steps=100_000):
cells = dict(enumerate(tape)) # 끝없는 테이프: 칸 번호 → 기호
head, steps = 0, 0
while state not in ("accept", "reject", "halt"):
symbol = cells.get(head, blank)
if (state, symbol) not in rules: # 정해진 규칙이 없으면 거절하고 멈춰요
state = "reject"
break
write, move, state = rules[(state, symbol)] # 쓰고, 움직이고, 상태를 바꿔요
cells[head] = write
head += {"R": 1, "L": -1, "S": 0}[move]
steps += 1
if steps >= max_steps:
return "멈추지 않음", None, steps
used = [i for i, s in cells.items() if s != blank]
result = "".join(cells[i] for i in range(min(used), max(used) + 1)) if used else ""
return state, result, steps
INCREMENT = { # 2진수에 1 더하기
("start", "0"): ("0", "R", "start"), # 오른쪽 끝까지 가요
("start", "1"): ("1", "R", "start"),
("start", "_"): ("_", "L", "carry"),
("carry", "1"): ("0", "L", "carry"), # 1은 0으로 바꾸고 올림을 왼쪽으로
("carry", "0"): ("1", "S", "halt"), # 0을 만나면 1로 바꾸고 끝
("carry", "_"): ("1", "S", "halt"), # 맨 왼쪽까지 올림이 가면 새 자리
}
for bits in ["1011", "111"]:
state, result, steps = run_tm(INCREMENT, bits)
print(f"{bits} + 1 = {result} ({steps}걸음)")
print("0부터 1,023까지 모두 맞나요?",
all(run_tm(INCREMENT, bin(n)[2:])[1] == bin(n + 1)[2:] for n in range(1024)))
1011 + 1 = 1100 (8걸음)
111 + 1 = 1000 (8걸음)
0부터 1,023까지 모두 맞나요? True
오른쪽 끝까지 간 다음, 1을 0으로 바꾸며 올림을 왼쪽으로 옮기다가 0이나 빈칸을 만나면 1을 쓰고 멈춰요. 우리가 손으로 하는 덧셈과 똑같아요. 디지털 논리 강의에서 회로로 만든 덧셈을 이번에는 규칙표 여섯 줄로 만들었어요.
문법보다 강한 기계
지난 강의에서 문맥 자유 문법으로는 a, b, c를 똑같이 n개씩 쓴 문자열을 만들 수 없었어요. 튜링 기계는 이걸 판별해요. a, b, c를 하나씩 지워 표시하고 처음 자리로 되돌아오기를 반복하다가, 다 지웠을 때 남은 것이 없으면 받아들여요.
from itertools import product
ABC = { # a, b, c가 똑같이 n개씩인가
("start", "a"): ("X", "R", "find_b"), # a 하나를 X로 지우고
("start", "Y"): ("Y", "R", "check"), # a를 다 지웠으면 남은 게 없는지 확인
("start", "_"): ("_", "S", "accept"),
("find_b", "a"): ("a", "R", "find_b"),
("find_b", "Y"): ("Y", "R", "find_b"),
("find_b", "b"): ("Y", "R", "find_c"), # b 하나를 Y로 지우고
("find_c", "b"): ("b", "R", "find_c"),
("find_c", "Z"): ("Z", "R", "find_c"),
("find_c", "c"): ("Z", "L", "back"), # c 하나를 Z로 지운 뒤
("back", "a"): ("a", "L", "back"), # 마지막으로 지운 X까지 되돌아가요
("back", "b"): ("b", "L", "back"),
("back", "Y"): ("Y", "L", "back"),
("back", "Z"): ("Z", "L", "back"),
("back", "X"): ("X", "R", "start"),
("check", "Y"): ("Y", "R", "check"),
("check", "Z"): ("Z", "R", "check_z"),
("check_z", "Z"): ("Z", "R", "check_z"),
("check_z", "_"): ("_", "S", "accept"),
}
for word in ["aabbcc", "aabbc", "abcabc", "aaabbbccc"]:
state, _, steps = run_tm(ABC, word)
print(f"{word}: {'받아들임' if state == 'accept' else '거절'} ({steps}걸음)")
words = ["".join(p) for n in range(8) for p in product("abc", repeat=n)]
expected = lambda w: w == "a" * (len(w) // 3) + "b" * (len(w) // 3) + "c" * (len(w) // 3)
print(f"길이 7 이하 문자열 {len(words):,}개에서 모두 맞나요?",
all((run_tm(ABC, w)[0] == "accept") == expected(w) for w in words))
aabbcc: 받아들임 (23걸음)
aabbc: 거절 (13걸음)
abcabc: 거절 (7걸음)
aaabbbccc: 받아들임 (46걸음)
길이 7 이하 문자열 3,280개에서 모두 맞나요? True
길이 7 이하의 모든 문자열 3,280개에서 하나도 틀리지 않았어요. 스택은 맨 위만 볼 수 있고 꺼내면 사라지지만, 테이프는 앞뒤로 오가며 몇 번이고 다시 읽고 고쳐 쓸 수 있어요. 이 차이가 힘의 차이예요.
처치-튜링 논제와 튜링 완전
튜링 기계는 너무 단순해 보이지만, 지금까지 알려진 어떤 계산 방법도 튜링 기계보다 더 많은 것을 계산하지 못했어요. 같은 시기에 알론조 처치가 전혀 다른 방식(람다 대수)으로 정의한 계산도 튜링 기계와 정확히 같은 힘을 가진다는 게 밝혀졌고요. 그래서 "알고리즘으로 계산할 수 있는 것은 정확히 튜링 기계로 계산할 수 있는 것"이라고 받아들이는데, 이걸 처치-튜링 논제라고 해요. "알고리즘"이라는 직관적인 말을 수학적으로 정의하는 주장이라, 증명하는 정리가 아니라 논제예요.
튜링 기계가 할 수 있는 모든 계산을 해낼 수 있는 체계를 튜링 완전하다고 해요. 파이썬, 자바스크립트, C 같은 프로그래밍 언어는 메모리가 끝없다고 치면 모두 튜링 완전해요. 엑셀 수식도 LAMBDA 함수가 생긴 뒤로 튜링 완전해졌고, 몇 가지 단순한 규칙으로 점이 생기고 사라지는 콘웨이의 생명 게임도 튜링 완전하다는 게 증명됐어요. 계산 능력은 생각보다 쉽게 꼭대기에 닿아요. 언어마다 다른 건 무엇을 계산할 수 있느냐가 아니라 얼마나 편하고 빠르게 쓰느냐예요.
범용 튜링 기계: 프로그램도 데이터
앞의 run_tm 함수는 규칙표를 데이터로 받아서 어떤 튜링 기계든 흉내 내요. 튜링은 이런 기계, 즉 다른 기계의 규칙표를 테이프에서 읽어 그대로 흉내 내는 범용 튜링 기계도 튜링 기계 하나로 만들 수 있음을 보였어요. 일마다 기계를 새로 만들 필요 없이, 기계 하나에 프로그램만 바꿔 넣으면 된다는 생각이에요. 프로그램을 데이터처럼 메모리에 담아 실행하는 지금의 컴퓨터 구조도 같은 생각 위에 서 있어요. 파이썬 인터프리터도 여러분이 쓴 코드를 데이터로 읽어서 실행하는 범용 기계예요.
정지 문제: 만들 수 없는 프로그램
이렇게 강한 기계에게도 풀 수 없는 문제가 있어요. 가장 유명한 것이 정지 문제예요. 어떤 프로그램과 입력이 주어졌을 때, 그 프로그램이 언젠가 멈추는지 영원히 도는지 판별하는 프로그램을 만들 수 있을까요?
이런 판별기 halts(program, arg)가 있다고 가정해 볼게요. 어떤 프로그램이든 정확히 "끝난다" 또는 "안 끝난다"로 답해 주는 함수예요. 그러면 이 판별기로 이런 프로그램을 만들 수 있어요.
def paradox(program):
if halts(program, program): # "program에 자기 자신을 넣으면 끝난다"는 답이면
영원히 돈다
else: # "안 끝난다"는 답이면
바로 끝낸다
이제 paradox(paradox), 즉 paradox에 자기 자신을 넣는 경우를 생각해 봐요.
halts가 "끝난다"고 답하면paradox는 영원히 돌아요. 판별기가 틀렸어요.halts가 "안 끝난다"고 답하면paradox는 바로 끝나요. 역시 판별기가 틀렸어요.
어느 쪽이든 판별기는 틀려요. 그러니 모든 프로그램에 대해 맞게 답하는 판별기는 존재할 수 없어요. 1936년 튜링이 보인 증명이에요. 판별기를 실제로 가져와서, 그 판별기를 속이는 프로그램을 만들어 확인해 볼게요. 영원히 도는 걸 끝까지 기다릴 수는 없으니 1만 걸음까지만 돌려 봐요.
def run(program, arg, budget=10_000): # 프로그램을 최대 budget걸음까지 돌려 봐요
for n, _ in enumerate(program(arg), 1):
if n >= budget:
return f"{budget:,}걸음이 넘도록 끝나지 않아요"
return "끝났어요"
def make_paradox(halts): # 어떤 판별기든 받아서, 그 판별기를 속이는 프로그램을 만들어요
def paradox(program):
if halts(program, program): # "끝난다"는 답을 들으면
while True:
yield # 영원히 돌고
return # "안 끝난다"는 답을 들으면 바로 끝내요
return paradox
candidates = {
"늘 '끝난다'고 답하는 판별기": lambda program, arg: True,
"늘 '안 끝난다'고 답하는 판별기": lambda program, arg: False,
}
for name, halts in candidates.items():
paradox = make_paradox(halts)
said = "끝난다" if halts(paradox, paradox) else "안 끝난다"
print(f"{name}: '{said}'고 예측 → 실제로는 {run(paradox, paradox)}")
늘 '끝난다'고 답하는 판별기: '끝난다'고 예측 → 실제로는 10,000걸음이 넘도록 끝나지 않아요
늘 '안 끝난다'고 답하는 판별기: '안 끝난다'고 예측 → 실제로는 끝났어요
1만 걸음이 넘도록 끝나지 않았다고 영원히 돈다는 증명이 되는 건 아니지만, 이 경우는 while True 안에 갇힌 게 분명해요. 핵심은 make_paradox가 어떤 판별기를 받든 그 판별기가 틀리는 프로그램을 만들어 낸다는 점이에요. 소스 코드를 분석하는 판별기든, 몇 걸음 돌려 보고 판단하는 판별기든 마찬가지예요. 판별기가 무슨 답을 하든 paradox는 그 답을 듣고 반대로 움직여요.
이 논법은 칸토어가 "실수는 자연수보다 많다"를 보일 때 쓴 대각선 논법과 뿌리가 같아요. 모든 프로그램을 한 줄로 늘어놓을 수 있다고 해도, 각 프로그램에 자기 자신을 넣은 결과를 뒤집어 만든 프로그램은 그 목록의 어느 줄과도 달라요. 같은 생각에서 더 놀라운 사실도 나와요. 프로그램은 유한한 글자의 나열이라 자연수처럼 하나, 둘 셀 수 있지만, 자연수를 받아 0이나 1을 돌려주는 함수는 그보다 훨씬 많아서 셀 수조차 없어요. 그러니 대부분의 함수는 어떤 프로그램으로도 계산할 수 없어요.
끝나는지 아무도 모르는 짧은 코드
정지 문제가 추상적으로 느껴진다면 이 코드를 보세요. 짝수면 반으로 나누고, 홀수면 3배 하고 1을 더하기를 1이 될 때까지 반복해요.
def collatz_steps(n): # 짝수면 반으로, 홀수면 3배 하고 1을 더해요. 1이 되면 끝
steps = 0
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
steps += 1
return steps
print(f"27은 {collatz_steps(27)}단계 만에 1이 돼요")
worst = max(range(1, 100_000), key=collatz_steps)
print(f"10만 아래에서 가장 오래 걸리는 수: {worst:,} ({collatz_steps(worst)}단계)")
27은 111단계 만에 1이 돼요
10만 아래에서 가장 오래 걸리는 수: 77,031 (350단계)
27처럼 작은 수도 111단계를 오르내리고, 10만 아래에서는 77,031이 350단계로 가장 오래 걸려요. 컴퓨터로 확인한 아주 큰 범위의 수까지 모두 결국 1이 됐지만, 모든 자연수에서 이 반복이 끝나는지는 아직 아무도 증명하지 못했어요. 이걸 콜라츠 추측이라고 해요. 만약 정지 문제의 판별기가 있다면, "1이 되지 않는 수가 나올 때까지 1부터 차례로 시험하는 프로그램이 멈추는가"를 물어서 이 추측을 단번에 풀 수 있을 거예요. 수학의 수많은 미해결 문제가 이런 식으로 "어떤 프로그램이 멈추는가"로 바뀌어요.
비슷한 예가 바쁜 비버 문제예요. 상태가 n개인 튜링 기계 중 빈 테이프에서 시작해 결국 멈추는 것들 가운데, 가장 오래 도는 것은 몇 걸음 만에 멈출까요? 상태 5개짜리의 답(47,176,870걸음)은 2024년에야 여러 사람의 공동 작업과 컴퓨터로 검증한 증명으로 확정됐고, 상태 6개짜리는 아직 아무도 몰라요.
결정 불가능성이 실무에 주는 뜻
정지 문제는 시작일 뿐이에요. 라이스 정리에 따르면 "이 프로그램이 0을 출력할 때가 있는가", "이 함수는 늘 같은 답을 내는가", "이 프로그램은 악성인가"처럼 프로그램이 실제로 하는 일에 대한 의미 있는 질문은 모두 일반적으로 판별할 수 없어요. 그런 판별기가 있다면 그걸로 정지 문제를 풀 수 있게 만들 수 있거든요. 그래서 실무의 도구는 모두 근사예요.
- 린터와 타입 검사기는 문제를 놓치거나, 멀쩡한 코드를 의심하거나 둘 중 하나를 감수해요. 모든 버그를 정확히 찾아내는 도구는 원리적으로 만들 수 없어요.
- 백신은 알려진 패턴과 의심스러운 행동으로 악성 코드를 추측할 뿐, 모든 악성 코드를 판별할 수는 없어요.
- 컴파일러는 끝나지 않는 반복문을 모두 찾아 주지 못해요.
- 그래서 서버는 타임아웃을 둬요. 끝날지 미리 알 수 없으니 정해진 시간이 지나면 끊는 거예요. 서버 트랙과 네트워크 트랙에서 연결과 읽기에 타임아웃을 둔 것도 같은 지혜예요.
"결정할 수 없다"는 건 "어떤 경우에도 알 수 없다"가 아니라 "모든 경우에 맞게 답하는 하나의 방법은 없다"는 뜻이에요. 특정 프로그램이 멈추는지는 증명할 수 있는 경우가 많고, 실제 도구들은 그 넓은 영역에서 아주 쓸모 있어요.
실습
INCREMENT를 고쳐서 2진수에서 1을 빼는 튜링 기계를 만들어 보세요. 0에서 빼면 어떻게 할지도 정해 보세요.- 테이프에 적힌 0과 1을 그대로 한 번 더 이어 쓰는 튜링 기계(예를 들어 101을 101101로)를 설계해 보세요. 어떤 표시 기호가 필요할까요?
make_paradox에 "1,000걸음 돌려 보고 끝나면 True, 아니면 False"라고 답하는 판별기를 넣으면 무슨 일이 생길지 예상하고 확인해 보세요.- 콜라츠 반복에서 100만 아래 수 중, 도중에 가장 크게 올라가는 수와 그 최댓값을 찾아보세요.
- "이 함수가 어떤 입력에서든 결국 hello를 출력하는가"를 판별하는 프로그램이 있다면, 그걸로 정지 문제를 어떻게 풀 수 있을지 설명해 보세요.
자주 하는 오해
- 튜링 기계는 옛날 기계다. 실제로 만들어 쓰려는 기계가 아니라, "계산이란 무엇인가"를 정의하는 수학적 모형이에요.
- 더 좋은 컴퓨터나 언어가 나오면 정지 문제도 풀린다. 처치-튜링 논제에 따르면 어떤 컴퓨터도 튜링 기계보다 더 많은 것을 계산하지 못해요. 속도가 아니라 원리의 문제예요.
- 결정 불가능하면 아무것도 알 수 없다. 모든 경우에 맞게 답하는 하나의 방법이 없을 뿐, 개별 프로그램이나 좁은 범위에서는 판별할 수 있는 경우가 많아요.
- 오래 돌려 보면 멈추는지 알 수 있다. 1만 걸음, 100만 걸음을 돌려도 바로 다음 걸음에 멈출 수 있어요. 기다림으로는 "안 멈춘다"를 확인할 수 없어요.
- 완벽한 버그 탐지기는 기술이 부족해서 없다. 라이스 정리에 따라 원리적으로 만들 수 없어요.
점검 문제
- 튜링 기계를 이루는 요소는 무엇이고, 유한 오토마타와 무엇이 다른가요?
- 튜링 기계가 a, b, c를 똑같이 n개씩 쓴 문자열을 판별할 수 있는 이유는?
- 처치-튜링 논제란 무엇이고, 왜 정리가 아니라 논제인가요?
- 범용 튜링 기계의 생각은 지금의 컴퓨터와 어떻게 이어지나요?
- 정지 문제의 판별기가 존재할 수 없다는 증명을 설명해 보세요.
- 콜라츠 반복은 정지 문제와 어떻게 연결되나요?
- 라이스 정리는 무엇을 말하고, 정적 분석 도구에 어떤 뜻을 가지나요?
- 끝날지 알 수 없는 작업을 다루는 실무의 방법은?
정답
- 끝없는 테이프, 한 칸을 읽고 쓰는 헤드, 상태, 그리고 (상태, 읽은 기호)마다 쓸 기호와 움직일 방향과 다음 상태를 정한 규칙표예요. 유한 오토마타와 달리 테이프에 쓸 수 있고, 앞뒤로 움직일 수 있고, 테이프가 끝이 없어요.
- a, b, c를 하나씩 지워 표시하고 되돌아오기를 반복하면서, 테이프를 몇 번이고 다시 읽고 고쳐 쓸 수 있기 때문이에요. 스택처럼 한 번 꺼내면 사라지지 않아요.
- 알고리즘으로 계산할 수 있는 것은 정확히 튜링 기계로 계산할 수 있는 것이라는 주장이에요. "알고리즘"이라는 직관적인 개념을 수학적으로 정의하는 것이라 증명할 대상이 아니고, 지금까지의 모든 증거가 뒷받침하는 논제예요.
- 다른 기계의 규칙표를 데이터로 읽어 흉내 내는 기계 하나만 있으면 된다는 생각이, 프로그램을 데이터처럼 메모리에 담아 실행하는 지금의 컴퓨터와 인터프리터로 이어져요.
- 판별기가 있다고 가정하고, 그 판별기에게 "자기 자신을 넣으면 끝나는가"를 물어 반대로 움직이는 프로그램을 만들어요. 그 프로그램에 자기 자신을 넣으면, 판별기가 "끝난다"고 하면 영원히 돌고 "안 끝난다"고 하면 끝나서 어느 쪽이든 판별기가 틀려요. 그러니 그런 판별기는 존재할 수 없어요.
- "1이 되지 않는 수가 나올 때까지 차례로 시험하는 프로그램"이 멈추는지 알면 콜라츠 추측이 풀려요. 정지 문제의 판별기가 있다면 이런 미해결 문제를 단번에 풀 수 있다는 뜻이에요.
- 프로그램이 실제로 하는 일에 대한 의미 있는 성질은 모두 일반적으로 판별할 수 없다는 정리예요. 그래서 린터, 타입 검사기, 백신 같은 도구는 문제를 놓치거나 멀쩡한 것을 의심하는 근사일 수밖에 없어요.
- 미리 판별하려 하지 않고 타임아웃을 둬서, 정해진 시간이 지나면 끊고 실패로 다뤄요.
다음 강의
이번 강의는 "계산할 수 있는가"를 따졌어요. 하지만 계산할 수 있어도 우주의 나이만큼 걸린다면 소용이 없죠. 다음 강의에서는 "얼마나 빨리 계산할 수 있는가"로 질문을 옮겨, 빠르게 풀 수 있는 문제(P)와 답을 빠르게 확인할 수 있는 문제(NP), 그리고 컴퓨터 과학 최대의 미해결 문제인 P와 NP의 관계를 다뤄요.