계산가능성

계산가능성은 어떤 문제를 컴퓨터로 풀 수 있는지를 가르는 성질입니다. 푼다는 말은 모든 입력에 대해 언젠가 멈추고 맞는 답을 내는 절차가 있다는 뜻입니다. 이런 절차가 아예 없는 문제도 있다는 것이 증명되어 있습니다. 얼마나 빨리 푸는지는 따지지 않고 풀 수 있는지만 봅니다.

상세

요리책의 레시피는 누가 따라 해도 같은 순서로 같은 요리가 나오는 지시서입니다. 계산가능성은 어떤 일에 이런 레시피를 쓸 수 있는지를 묻습니다.

이 절은 「컴퓨터로 풀 수 있다」는 말이 무엇을 뜻하는지, 그리고 왜 못 푸는 문제가 반드시 있는지를 다룹니다. 계산을 흉내 내는 기계 하나와 짧은 파이썬 함수 하나를 가지고 봅니다.

푼다는 말의 뜻

이 개념에서 문제는 입력을 받아 답을 내야 하는 물음입니다. 「이 목록을 오름차순으로 늘어놓아라」나 「이 수는 소수인가」가 문제입니다. 가능한 입력마다 맞는 답이 하나씩 정해져 있습니다.

알고리즘은 이런 문제를 푸는 절차입니다. 지시의 개수가 유한합니다. 생각할 필요 없이 기계적으로 따라 할 수 있습니다. 그리고 어떤 입력을 넣어도 유한한 단계 뒤에 멈추고 답을 냅니다.

어떤 문제에 이런 알고리즘이 하나라도 있으면 그 문제는 계산 가능합니다. 하나도 없으면 계산 불가능합니다. 정렬도, 소수 판정도, 두 수의 최대공약수 구하기도 계산 가능합니다.

계산의 기준이 되는 튜링 기계

「알고리즘이 없다」를 보이려면 알고리즘이 무엇인지부터 빈틈없이 정해야 합니다. 「기계적으로 따라 할 수 있는 절차」라는 말만으로는 무엇이 들고 무엇이 빠지는지 가를 수 없습니다. 그래서 계산을 흉내 내는 단순한 기계를 세우고, 그 기계가 할 수 있는 일을 계산이라고 정합니다.

가장 널리 쓰는 기계가 튜링 기계입니다. 앨런 튜링이 내놓아서 이 이름이 붙었습니다. 부품은 셋뿐입니다.

1. 테이프 — 칸이 한쪽으로 끝없이 이어진 띠입니다. 칸마다 글자 하나가 들어갑니다. 입력이 여기 적혀 있고 답도 여기 남습니다
2. 헤드 — 테이프의 한 칸을 가리킵니다. 그 칸의 글자를 읽습니다. 다른 글자로 고쳐 쓸 수 있습니다. 그다음 왼쪽이나 오른쪽으로 한 칸 옮깁니다
3. 상태표 — 기계는 늘 정해진 몇 가지 상태 가운데 하나에 있습니다. 상태는 지금 어느 단계인지를 기억하는 표시입니다. 상태표는 지금 상태와 방금 읽은 글자를 보고 다음에 할 일을 정하는 표입니다. 이 표가 곧 프로그램입니다

기계는 아래 그림의 한 바퀴를 되풀이합니다. 상태 가운데 하나는 멈춤 상태입니다. 상태표가 기계를 멈춤 상태로 보내면 그때 테이프에 남은 글자가 답입니다.

flowchart TD
    A["헤드가 지금 칸의 글자를 읽는다"] --> B["상태표에서 지금 상태와 읽은 글자의 줄을 찾는다"]
    B --> C["글자를 쓰고 헤드를 한 칸 옮기고 상태를 바꾼다"]
    C --> D{"멈춤 상태인가"}
    D -->|아니다| A
    D -->|그렇다| E["테이프에 남은 글자가 답이다"]

이렇게 단순한 기계로도 우리가 쓰는 컴퓨터의 계산을 전부 흉내 낼 수 있습니다. 느릴 뿐 못 하는 계산은 없습니다. 테이프가 끝없이 길다는 점만 컴퓨터와 다릅니다.

언어와 무관한 경계

튜링 기계 말고도 계산을 정의하려는 모형은 여럿 나왔습니다. 함수를 만들고 적용하는 규칙만으로 계산을 적는 람다 계산법이 그 하나입니다. 이 모형들은 겉모양이 전혀 다릅니다. 그런데 풀 수 있는 문제의 집합은 모두 같다는 것이 증명되었습니다.

그래서 「기계적으로 따라 할 수 있는 절차로 풀리는 문제」와 「튜링 기계로 풀리는 문제」를 같은 것으로 받아들입니다. 이 생각을 처치-튜링 논제라고 부릅니다. 「기계적으로 따라 할 수 있다」는 직관은 수학으로 적을 수 없어서 정리가 아니라 논제입니다. 이를 뒤집는 반례는 아직 나오지 않았습니다.

어떤 언어가 튜링 기계의 계산을 전부 흉내 낼 수 있으면 그 언어를 튜링 완전하다고 합니다. 조건 분기와 끝을 정하지 않는 반복, 필요한 만큼 쓸 수 있는 메모리가 있으면 튜링 완전해집니다.

파이썬·자바·C 같은 범용 언어는 모두 튜링 완전합니다. 실제 컴퓨터의 메모리는 유한하지만 이것과 어긋나지 않습니다. 튜링 완전은 언어의 규칙을 따지는 말이라, 메모리가 모자라면 더 붙일 수 있다고 보고 셉니다.

처치-튜링 논제와 튜링 완전성을 합치면 계산가능성은 언어를 가리지 않는 성질이 됩니다. 범용 언어는 튜링 기계만큼 풀고, 논제에 따르면 어떤 절차도 튜링 기계보다 더 풀지 못합니다. 그래서 파이썬으로 못 푸는 문제는 자바로도, 앞으로 나올 어떤 언어로도 못 풉니다. 계산 가능한지는 언어가 아니라 문제가 정합니다.

못 푸는 문제가 반드시 있는 까닭

못 푸는 문제가 있다는 것은 개수를 세어 보면 드러납니다. 먼저 프로그램 쪽을 셉니다.

프로그램은 길이가 유한한 글자열입니다. 짧은 것부터, 길이가 같으면 사전 순으로 늘어놓으면 모든 프로그램이 1번, 2번, 3번처럼 번호를 받습니다. 이렇게 번호를 매겨 한 줄로 세울 수 있는 것을 셀 수 있다고 합니다.

문제 쪽은 다릅니다. 여기서는 「예」나 「아니요」로 답하는 문제만 봅니다. 이런 문제 하나는 입력 1, 2, 3 … 마다 답을 적은 끝없는 목록으로 바꿔 볼 수 있습니다. 소수 판정이라면 입력 1은 아니요, 2는 예, 3은 예, 4는 아니요 … 로 이어지는 목록입니다.

그런데 이런 목록은 어떻게 번호를 매겨도 빠지는 것이 생깁니다. 이것을 보이는 방법이 대각선 논법입니다.

아래 표의 굵은 칸처럼 n번 목록의 n번째 답만 골라 모두 뒤집어 새 목록을 만듭니다.

새 목록은 1번 목록과 입력 1에서 다르고, 2번 목록과 입력 2에서 다릅니다. 어느 번호의 목록과도 적어도 한 칸이 다르니 번호를 받지 못한 목록이 됩니다. 그래서 문제는 셀 수 없습니다.

프로그램은 셀 수 있고 문제는 셀 수 없습니다. 프로그램 하나가 문제 하나씩 맡아도 짝을 못 찾는 문제가 남습니다. 남는 쪽이 오히려 훨씬 많습니다.

이름이 붙은 계산 불가능 문제

개수를 세는 증명은 못 푸는 문제가 있다는 것만 알려 줍니다. 어떤 문제가 그런지는 따로 찾아야 합니다. 가장 유명한 것이 정지 문제입니다.

정지 문제는 「이 프로그램에 이 입력을 넣으면 언젠가 끝나나」를 묻습니다. 모든 프로그램에 대해 늘 맞게 답하는 알고리즘은 없습니다.

까닭은 그런 판정기가 있다고 놓고 모순을 끌어내 보면 드러납니다. 판정기에 물어서, 끝난다고 하면 영원히 돌고 안 끝난다고 하면 바로 끝나는 프로그램을 짭니다. 이 프로그램에 자기 자신을 입력으로 넣으면 판정기가 어느 쪽으로 답해도 틀립니다. 그러니 그런 판정기는 처음부터 있을 수 없습니다.

정지 문제를 발판으로 다른 물음도 못 푼다는 것을 보일 수 있습니다. 어떤 물음을 풀 수 있다면 그것으로 정지 문제도 풀 수 있다는 것을 보이면 됩니다. 이렇게 한 물음을 다른 물음으로 바꾸는 일을 환원이라고 부릅니다.

「이 함수가 어떤 입력에서 오류를 낼 수 있나」·「두 함수가 모든 입력에서 같은 값을 내나」도 이렇게 못 푸는 물음이 됩니다. 둘 다 프로그램이 내는 결과를 묻는 물음입니다.

이런 물음을 한 문장으로 묶은 것이 라이스 정리입니다. 프로그램이 내는 결과에 관한 성질이 어떤 프로그램에는 맞고 어떤 프로그램에는 안 맞으면, 그 성질을 판정하는 알고리즘은 없습니다. 모든 프로그램에 맞거나 어느 프로그램에도 안 맞는 성질만 이 정리에서 빠집니다.

답이 반쪽만 나오는 문제

계산 불가능한 문제에도 정도가 있습니다. 정지 문제는 「끝난다」는 쪽 답만큼은 언젠가 낼 수 있습니다. 그냥 돌려 보면 되기 때문입니다.

아래 함수는 받은 프로그램 p 를 입력 x 로 돌려 봅니다. 끝나면 True 를 돌려줍니다.

def halts_yes(p, x):
    p(x)          # p 가 끝나야
    return True   # 이 줄에 닿는다

def forever(x):
    while True:
        pass

halts_yes(len, "abc")   # True
halts_yes(forever, 0)   # 돌아오지 않는다

len 은 바로 끝나니 True 가 돌아옵니다. forever 는 끝나지 않으니 halts_yes 도 영영 돌아오지 않습니다. 「예」인 입력에는 언젠가 답하지만 「아니요」인 입력에는 답을 못 줄 수 있습니다.

이처럼 「예」인 입력에는 반드시 답하는 알고리즘이 있는 문제를 인식 가능하다고 합니다. 「아니요」인 입력에서는 답을 안 줘도 됩니다. 정지 문제는 halts_yes 가 있으니 인식 가능합니다.

「예」와 「아니요」 모두 반드시 답하는 알고리즘이 있으면 결정 가능합니다. 예·아니요로 답하는 문제에서는 결정 가능이 곧 앞에서 말한 계산 가능입니다. 정지 문제는 인식 가능하지만 결정 가능하지는 않은 문제의 대표입니다.

halts_yes 처럼 「예」에만 답하는 함수를 반쪽 판정기라고 하겠습니다. 정지 문제를 뒤집은 「이 프로그램은 영원히 도나」에는 반쪽 판정기조차 없습니다. 있다고 놓으면 끝나는 프로그램에는 halts_yes 가 답하고, 영원히 도는 프로그램에는 새 판정기가 답합니다.

둘을 차례로 돌리면 앞의 것을 기다리다 영영 안 돌아올 수 있습니다. 그래서 한 걸음씩 번갈아 돌립니다. 입력마다 둘 중 하나는 반드시 답하니 늘 답이 나옵니다. 그러면 정지 문제가 결정 가능해져 앞의 결론과 어긋나므로, 영원히 도는지 묻는 물음은 인식조차 안 됩니다.

세 묶음은 아래 그림처럼 안쪽이 바깥쪽에 들어가는 관계입니다. 결정 가능하면 인식 가능하지만 거꾸로는 아닙니다.

flowchart TD
    subgraph all["예·아니요로 답하는 모든 문제"]
        subgraph rec["인식 가능"]
            subgraph dec["결정 가능"]
                A["소수 판정"]
            end
            B["정지 문제"]
        end
        C["영원히 도는지 묻는 문제"]
    end

계산가능성과 복잡도

계산가능성은 풀리는가만 묻습니다. 풀린다면 얼마나 빨리 풀리는가는 계산 복잡도 이론이 묻습니다. 두 물음은 아래 표처럼 갈립니다.

외판원 순회는 모든 도시를 한 번씩 도는 가장 짧은 길을 찾는 문제입니다. 모든 길을 다 견줘 보면 답이 나오니 계산 가능합니다. 다만 도시가 늘면 견줄 길이 빠르게 불어나 기다릴 수 없게 됩니다.

복잡도는 계산 가능한 문제 안에서만 따집니다. 걸리는 시간과 메모리로 문제를 묶은 복잡도 클래스도 흔히 쓰는 것은 전부 결정 가능한 문제의 묶음입니다.

개발에서 만나는 경계

계산가능성의 경계는 개발 도구가 할 수 있는 일의 상한을 정합니다. 경계를 모르면 처음부터 만들 수 없는 도구에 시간을 씁니다.

정적 분석 도구는 코드를 돌리지 않고 읽어서 버그를 찾습니다. 라이스 정리 때문에 이런 도구는 모든 코드에서 늘 맞게 답할 수 없습니다. 그래서 판정이 안 서는 코드를 만나면 일단 경고하거나 조용히 넘어갑니다.

일단 경고하는 쪽은 문제없는 코드에도 경고를 냅니다. 이런 잘못된 경고가 오탐입니다. 조용히 넘어가는 쪽은 진짜 버그를 지나칩니다. 이것을 미탐이라고 부릅니다.

작업이 끝날지 미리 알 수 없으니 실무는 기다리는 시간에 상한을 겁니다. 요청마다 거는 타임아웃이 그 예입니다. 끝날지를 판정한 것이 아니라 끝까지 기다리지 않기로 정한 것입니다.

일부러 튜링 완전하지 않게 만든 언어도 있습니다. 반복 횟수를 실행 전에 정하게 하면 그 언어로 쓴 것은 모두 끝납니다. 이런 언어는 표현력을 내주는 대신 반드시 끝난다는 보장을 얻습니다.

관련 항목

계산가능성이 속하는 상위 분류

계산 이론 · 이론 컴퓨터 과학 · 수리 논리학 · 알고리즘

계산을 정의하는 모형

튜링 기계 · 범용 튜링 기계 · 람다 계산법 · 재귀 함수 · 유한 오토마타 · 처치-튜링 논제 · 튜링 완전성

계산가능성으로 가르는 문제의 등급

결정 문제 · 결정 가능성 · 결정 불가능성 · 인식 가능 · 재귀 열거 가능 집합

계산할 수 없음을 보인 정리와 문제

정지 문제 · 라이스 정리 · 우편 대응 문제 · 힐베르트의 결정 문제 · 괴델의 불완전성 정리

불가능성을 증명하는 논법

대각선 논법 · 귀류법 · 환원 · 자기 참조

계산가능성과 맞세워지는 효율의 척도

계산 복잡도 이론 · 복잡도 클래스 · 시간 복잡도 · 공간 복잡도 · P 대 NP 문제 · 외판원 순회

이 경계에 부딪히는 개발 도구

정적 분석 · 린터 · 타입 검사 · 타임아웃 · 종료 증명