처치-튜링 논제, 보편 튜링머신, 계산가능성, 물리적 계산 가능성

1. 개요

계산 이론에서 자주 함께 등장하는 개념들이 있다.
처치-튜링 논제, 보편 튜링머신, 계산가능성, 물리적 계산 가능성이다.

이 네 개념은 서로 연결되어 있지만 같은 뜻은 아니다.
가장 큰 차이는 다음과 같다.

계산가능성은 무엇이 원리적으로 계산될 수 있는가에 대한 개념이다.
보편 튜링머신은 하나의 기계가 다른 모든 튜링 기계를 모사할 수 있음을 보여주는 모델이다.
처치-튜링 논제는 직관적인 알고리즘 개념과 튜링 기계의 형식적 개념이 사실상 같은 범위를 가진다는 주장이다.
물리적 계산 가능성은 실제 세계의 물리적 장치가 무엇을 계산할 수 있는가라는 문제다.

2. 계산가능성

계산가능성은 어떤 문제나 함수가 유한한 절차에 의해 계산될 수 있는지를 다룬다.

예를 들어,

두 수의 덧셈
정수의 소인수분해
주어진 수가 소수인지 판정하기

같은 문제는 계산 가능한 문제들이다.

반면 계산 이론은 모든 문제가 계산 가능한 것은 아니라는 사실도 보여준다.
대표적으로 정지 문제(Halting Problem) 는 일반적인 알고리즘으로 풀 수 없다.
즉, 계산가능성은 단순히 “어려운가 쉬운가”의 문제가 아니라,
아예 계산 절차 자체가 존재하는가의 문제다.

3. 보편 튜링머신

보편 튜링머신은 다른 모든 튜링 기계를 입력으로 받아 그 동작을 모사할 수 있는 튜링 기계다.

이 개념의 의미는 매우 크다.

개별 문제마다 별도의 기계를 만드는 대신,
하나의 일반 목적 기계가 프로그램과 입력을 받아 다양한 계산을 수행할 수 있다는 뜻이기 때문이다.

현대 컴퓨터의 핵심 아이디어도 여기에 가깝다.

하드웨어는 하나의 범용 장치이고
프로그램만 바꾸면 전혀 다른 계산을 수행할 수 있다

즉, 보편 튜링머신은 프로그램 내장형 범용 계산기계의 이론적 원형이다.

4. 처치-튜링 논제

처치-튜링 논제는 보통 다음과 같이 말한다.

직관적인 의미에서 효과적으로 계산 가능한 모든 것은 튜링 기계로 계산 가능하다.

여기서 중요한 점은 이것이 정리가 아니라 논제라는 것이다.

왜냐하면 한쪽은 엄밀하게 정의된 수학적 개념이다.

튜링 기계로 계산 가능함

반면 다른 한쪽은 원래 비형식적 개념이다.

효과적으로 계산 가능한 절차
알고리즘적으로 계산 가능하다고 직관적으로 받아들여지는 것

즉, 처치-튜링 논제는
비형식적 계산 개념을 형식적 모델과 연결하는 철학적·수학적 주장이다.

이 논제가 강하게 받아들여지는 이유는,
튜링 기계뿐 아니라 람다 계산, 재귀 함수 등 여러 서로 다른 형식 체계가
모두 같은 계산 가능성의 범위를 가리켰기 때문이다.

5. 물리적 계산 가능성

물리적 계산 가능성은 질문의 방향이 다르다.

여기서는
“실제 세계의 물리적 장치가 무엇을 계산할 수 있는가?”
를 묻는다.

이때 중요한 것은 현실의 제약이다.

에너지
시간
잡음
양자역학적 효과
상대론적 한계
구현 가능한 물리 과정

즉, 계산가능성이 수학적 모델의 문제라면,
물리적 계산 가능성은 자연법칙 아래에서 실현 가능한 계산의 문제다.

이와 관련해 더 강한 형태의 주장이 물리적 처치-튜링 논제다.

현실적으로 실현 가능한 모든 계산 과정은 튜링 기계로 모사 가능하다.

이 주장은 원래의 처치-튜링 논제보다 더 강하다.
왜냐하면 여기서는 인간의 기호 조작 절차를 넘어서
자연 전체가 허용하는 계산 과정까지 포함하기 때문이다.

6. 네 개념의 관계

이 네 개념은 다음처럼 구분하면 깔끔하다.

계산가능성

무엇이 원리적으로 계산 가능한가를 묻는 이론적 개념

보편 튜링머신

계산 가능한 절차들을 하나의 범용 기계가 모사할 수 있음을 보여주는 모델