Computability

튜링 기계(Turing machine)

먼저 알고리즘을 다룰 언어를 다음과 같이 정의한다.

• 알고리즘이 다룰 대상은 유한한 알파벳 \(A = \{a_1, \dots, a_n\}\) 의 기호들이라고 가정한다. (비기호적 대상일지라도 유한한 기호를 사용하여 계산하는 언어에 의하여 표현될 수 있다. 가령, 이미지는 행렬로 변환되고, 생각은 문장으로 그리고 벡터로 변환된다.)
• 언어 \(A\) 의 기호의 유한열을 \(A\) 의 단어(word)라고 하자. 아무런 기호로도 구성되어 있지 않은 빈 단어를 \(\Lambda\) 라고 하자. 단어 \(P\) 와 \(Q\) 에 대하여 \(PQ\) 를 \(P\) 오른쪽에 \(Q\) 를 쓴 단어라고 하자. 양의 정수 \(k\) 에 대하여 \(P^k\) 를 단어 \(P\) 를 \(k\)번 연속적으로 쓴 것이라고 하자.

알고리즘을 다룰 공간을 다음과 같이 정의한다.

• 인간이 계산하기 위해서는 보통 공책이나 칠판을 사용하므로 알고리즘의 작업공간을 2차원 공간으로 생각할 수 있다. 그러나 이 공간을 단순화시키면 그것들의 본질인 스퀘어로 나뉘어져있는 1차원 선형 테이프을 얻는다.

  테이프는 잠재적으로 무한히 많은 스퀘어를 갖는다. 임의의 시점에서 오직 테이프의 유한한 스퀘어만이 기호를 갖고 있고 나머지 스퀘어는 빈칸으로 남겨진다. (이 1차원 테이프는 알고리즘의 능력을 제한하지 않는다. 2차원 배열에 담긴 정보도 유한열로 인코딩될 수 있다. \(\N\) 의 임의의 튜플과 \(\N\) 사이에 전단사 사상이 존재하기 때문이다.)

이러한 알고리즘의 언어와 공간에서 계산을 수행하는 기계를 모두 튜링 기계라는 개념으로 추상화시키려 한다. 먼저 튜링 기계가 다음과 같은 성질을 갖는다고 정의한다.

• 튜링 기계는 연속적인 시간으로 작동하지 않고 아니라 이산적인 순간마다 작동한다. (모든 연속적으로 작동하는 것처럼 보이는 기계는 이산적인 시간으로 분석되어질 수 있기 때문이다.)
• 튜링 기계가 한 순간에 하나의 스퀘어만을 읽는다고 가정한다. (큰 영역에 대한 관찰은 개별 스퀘어의 연속적인 관찰로 귀결되기 때문이다. 가령, 눈이 사물을 보는 것도 한 시각세포가 하나의 빛의 정보를 받아들여서 종합된 것이다.)

튜링 기계가 특정 스퀘어를 읽었을 때 다음과 같은 리액션을 취한다고 정의한다.

1. 기호를 지우고 새로운 기호를 쓰기.
2. 오른쪽 스퀘어로 이동.
3. 왼쪽 스퀘어로 이동.
4. 멈춤.

튜링 기계는 관찰한 기호에 의존할 뿐만 아니라 기계의 내부 상태에도 의존한다. 기계는 유한한 상태 \(\{q_0, \dots, q_m\}\) 를 갖는다. 기계는 반드시 초기 상태 \(q_0\) 에서 시작한다.

기계의 동작은 다음 셋 중 하나의 쿼드러플 형태로 대응된다. \(q_j\) 는 현재 상태, \(q_r\) 은 다음 상태, \(a_i\) 는 읽은 스퀘어이다.

1. \(q_ja_ia_kq_r\): 기계가 \(a_i\) 를 지우고 \(a_k\) 를 쓴다.
2. \(q_ja_iRq_r\): 기계가 오른쪽 스퀘어로 이동.
3. \(q_ja_iLq_r\): 기계가 왼쪽 스퀘어로 이동.

이제 다음과 같이 튜링 기계의 정확한 정의를 내린다.

• 튜링 기계 \(\mathcal{T}\): 테이프 기호 \(\{a_0, \dots, a_n\}\) 의 알파벳 \(A\) 와 내부 상태 \(\{q_0, \dots, q_m\}\) 를 갖는 튜링 기계 \(\mathcal{T}\) 는 두 쿼드러플이 서로 같은 처음 두 기호를 갖지 않는 세 형태의 쿼드러플 \(q_ja_ia_kq_r\), \(q_ja_iRq_r\), \(q_ja_iLq_r\) 의 유한 집합 \(\mathcal{T}\) 이다.

테이프 서술(tape description)

테이프 서술이란 해당 순간에서의 테이프와 기계의 상태를 설명한다. 테이프 서술은 테이프 기호와 상태 기호로 이루어져있는데, 상태 기호 오른쪽에 있는 테이프 기호가 기계가 그 순간에 스캔한 기호이다.

튜링기계 \(\mathcal{T}\) 가 테이프 서술 \(\alpha\) 에서 \(\beta\) 로 이동한다는 것을 다음 중 하나가 참인 것으로 정의하고, \(\alpha \xtwoheadrightarrow[\mathcal{T}]{}\beta\) 로 표기하자. (\(P\) 와 \(Q\) 는 임의의 비어있어도 되는 \(\mathcal{T}\) 의 알파벳의 단어이고, \(a_0\) 는 빈 칸을 뜻한다.)

1. \(\alpha\) 가 \(Pq_ja_iQ\) 형태이고, \(\beta\) 가 \(Pq_ra_kQ\) 형태이고, \(q_ja_ia_kq_r\) 가 \(\mathcal{T}\) 의 쿼드러플 중 하나이다.
2. \(\alpha\) 가 \(Pa_sq_ja_iQ\) 형태이고, \(\beta\) 가 \(Pq_ra_sa_iQ\) 형태이고, \(q_ja_iLq_r\) 가 \(\mathcal{T}\) 의 쿼드러플 중 하나이다.
3. \(\alpha\) 가 \(q_ja_iQ\) 형태이고, \(\beta\) 가 \(q_ra_0a_iQ\) 형태이고, \(q_ja_iLq_r\) 가 \(\mathcal{T}\) 의 쿼드러플 중 하나이다.
4. \(\alpha\) 가 \(Pq_ja_ia_kQ\) 형태이고, \(\beta\) 가 \(Pa_iq_ra_kQ\) 형태이고, \(q_ja_iRq_r\) 가 \(\mathcal{T}\) 의 쿼드러플 중 하나이다.
5. \(\alpha\) 가 \(Pq_ja_i\) 형태이고, \(\beta\) 가 \(Pa_iq_ra_0\) 형태이고, \(q_ja_iRq_r\) 가 \(\mathcal{T}\) 의 쿼드러플 중 하나이다.

\(\alpha \xtwoheadrightarrow[\mathcal{T}]{}\beta\) 는 튜링 기계가 시간 \(t\) 에서 \(\alpha\) 였고 시간 \(t+1\) 에서 \(\beta\) 라는 것이다.

\(\mathcal{T}\) 가 테이프 서술 \(\alpha\) 에서 멈춘다는 것은 \(\alpha \xtwoheadrightarrow[\mathcal{T}]{}\beta\) 인 \(\beta\) 가 존재하지 않는다는 것이다. 이 상황은 \(\alpha\) 에 \(q_ja_i\) 가 나타났지만 \(q_ja_i\) 가 \(\mathcal{T}\) 의 쿼드러플의 시작으로 나타나지 않을 때 일어난다.

계산(computation), 적용가능(applicable)

튜링기계 \(\mathcal{T}\) 의 계산은 다음을 만족하는 \(k \geq 0\) 에 대한 테이프 서술 유한열 \(\alpha _0,\dots ,\alpha _k\) 이다. 이 계산을 \(\alpha_0\) 에서 시작하여 \(\alpha _k\) 에서 끝난다고 한다.

1. \(\alpha _0\) 는 초기 테이프 서술이다. 즉, \(\alpha_0\) 의 내부 상태가 \(q_0\) 이다.
2. \(0 \leq i < k\) 에 대하여 \(\alpha _i \xtwoheadrightarrow[\mathcal{T}]{}\alpha _{i+1}\)
3. \(\mathcal{T}\) 가 \(\alpha _k\) 에서 멈춘다.

\(\alpha_0\) 에서 시작하는 \(\mathcal{T}\) 의 계산이 존재하면 \(\mathcal{T}\) 가 \(\alpha _0\) 에 적용가능하다고 한다.

알고리즘(algorithm)

튜링기계 \(\mathcal{T}\) 에 의해 수행되는 알고리즘 \(\operatorname{Alg}_{\mathcal{T}}\) 는 다음과 같이 정의된다.

• \(\mathcal{T}\) 의 알파벳 \(A\) 의 임의의 단어 \(P\) 와 \(Q\) 에 대하여 \(\operatorname{Alg}_{\mathcal{T}}(P) = Q\) 는 테이프 서술 \(q_0P\) 에서 시작하여 \(Q = R_1R_2\) 에 대한 테이프설명 \(R_1q_jR_2\) 로 끝나는 \(\mathcal{T}\) 의 계산이 존재한다는 것이다.

튜링 기계 \(\mathcal{T}\) 에 의해 수행되는 알고리즘 \(\operatorname{Alg}_{\mathcal{T}}\) 를 튜링 알고리즘이라고 한다.

부분 함수(partial function)

부분함수는 정의역의 일부분에서 정의되지 않아도 되는 함수의 일반화이다.

튜링계산가능한 함수(Turing-computable)

수론적 함수의 계산을 고려하자. \(a_1\) 를 \(|\) 라고 쓰고 \(a_0\), 즉, 빈칸을 \(B\)(blank)라고 쓰자. 임의의 자연수 \(k\) 의 테이프 표현(tape representation) \(\overline{k}\) 를 단어 \(| ^{k+1}\), 즉, \(|\) 이 \(k+1\) 번 반복되는 것으로 정의한다. 자연수 n-튜플 \((k_1, \dots, k_n)\) 의 테이프 표현 \(\overline{(k_1, \dots, k_n)}\) 은 \(\overline{k_1}B \overline{k_2}B \dots B \overline{k_n}\) 라고 정의한다.

튜링 기계 \(\mathcal{T}\) 가 일변수 부분 함수 \(f _{\mathcal{T},1}\) 를 계산한다는 것은 다음과 같이 정의된다.

• \(f _{\mathcal{T},1}(k) = m\) 은 \(\operatorname{Alg}_{\mathcal{T}}(\overline{k})\) 이 정의되고 비어있어도 되는 \(B\) 로 구성된 단어 \(E_1\), \(E_2\) 에 대하여 \(\operatorname{Alg}_{\mathcal{T}}(k) = E_1 \overline{m}E_2\) 인 것과 동치이다.

이때 함수 \(f _{\mathcal{T},1}\) 을 튜링계산가능하다고 한다. 즉, 일변수 부분함수 \(f\) 가 튜링계산가능한 것은 \(f = f _{\mathcal{T},1}\) 인 튜링 기계 \(\mathcal{T}\) 가 존재한다는 것과 동치이다.

각 \(n>1\) 에 대하여 튜링 기계 \(\mathcal{T}\) 가 n변수 부분함수 \(f _{\mathcal{T},n}\) 을 계산한다는 것도 다음과 같이 정의된다.

• 임의의 자연수 \(k_1, \dots, k_n\) 에 대하여 \(f _{\mathcal{T},n}(k_1, \dots, k_n) = m\) 은 \(\operatorname{Alg}_{\mathcal{T}}\overline{((k_1, \dots, k_n))}\) 이 정의되고 비어있어도 되는 \(B\) 로 구성된 단어 \(E_1\), \(E_2\) 에 대하여 \(\operatorname{Alg}_{\mathcal{T}}((k_1, \dots, k_n)) = E_1 \overline{m}E_2\) 인 것과 동치이다.

이러한 부분함수 \(f _{\mathcal{T},n}\) 을 튜링계산가능하다고 한다. 따라서 n변수 부분함수 \(f\) 가 튜링계산가능한 것은 \(f=f _{\mathcal{T},n}\) 인 튜링 기계가 존재한다는 것과 동치이다.

문제 5.7

함수 \(f\) 가 튜링계산가능하면, \(f\) 는 무한히 많은 다른 튜링 기계에 의하여 계산가능하다.

다이어그램(diagram)

다음과 같이 구성되는 그래프를 다이어그램이라고 한다.

1. 알파벳 \(A = \{a_0, \dots, a_k\}\) 를 갖는 임의의 튜링 기계 \(\mathcal{T}_1,\dots ,\mathcal{T}_r\) 을 잡자.
2. 평면 안의 점들의 유한 집합을 잡자. 이 점을 정점(vertex)이라고 한다.
3. 각 정점에 기계의 이름 \(\mathcal{T}_1,\dots ,\mathcal{T}_r\) 중 하나를 붙이자.
4. 정점을 다른 정점으로 화살로 연결하자. 각 화살은 수 \(0, \dots, k\) 중 하나로 라벨링된다. 이때 같은 정점에서 나온 화살표는 같은 라벨을 가질 수 없다.
5. 원으로 둘러싸인 정점을 초기 정점(initial vertex)라고 한다.

다이어그램으로 정의되는 튜링 기계

모든 다이어그램은 다음과 같은 방식으로 연산이 표현되는 튜링 기계를 결정할 수 있다.

1. 주어진 테이프와 테이프 위의 특정 스퀘어에 대하여 다이어그램의 초기 정점 \(V\) 의 튜링 기계는 특정 스퀘어를 읽음으로써 연산을 시작한다.
2. 이 기계가 멈추고 마지막 계산에서 스캔한 스퀘어의 기호가 \(a_i\) 라면, 라벨이 \(i\) 인 화살표를 찾는다. 만약 이 화살표가 없다면 계산은 멈춘다. 이 화살표가 있다면 이전의 계산에 의하여 생성된 테이프 위에서 해당 기계를 시작한다.
3. 이 절차를 기계가 멈출 때까지 반복한다. 결과 테이프는 다이어그램에 의하여 결정된 기계의 출력이다. 이 기계가 멈추지 않으면 이것은 초기 테이프 서술에 적용 불가능한 것이다.

이러한 튜링 기계에 대한 쿼드러플을 다음과 같이 정의한다.

1. 다이어그램에서 기계 \(\mathcal{T}_i\) 마다 두 기계가 서로 같은 내부 상태를 갖지 않도록 내부 상태를 바꿔서 그것의 쿼드러프를 쓴다. 초기 정점 기계는 수정하지 않아도 된다. \(q_0\) 가 초기 내부 상태가 되도록 유지해야 하기 때문이다. 다른 모든 기계는 초기 상태 \(q_0\) 를 새로운 상태로 수정해야 한다.
2. 기계 \(\mathcal{T}_i\) 가 화살 \(\xrightarrow{u}\) 에 의하여 \(\mathcal{T}_j\) 에 연결되었다고 하자. 그러면, \(\mathcal{T}_i\) 의 모든 새로운 내부 상태 \(q_s\) 에 대하여 \(q_sa_u\) 로 시작하는 쿼드러플이 없다면, \(\mathcal{T}_j\) 의 새로운 내부 상태 \(q_t\) 로 연결되도록 쿼드러플 \(q_sa_ua_uq_t\) 를 추가해준다. 이로써 \(\mathcal{T}_i\) 가 \(q_u\) 를 스캔하고 멈추면 \(\mathcal{T}_j\) 가 시작될 수 있다.

튜링 기계 블록

다이어그램을 구성하기 위한 빌딩 블록으로 알파벳 \(\{a_0, \dots, a_k\}\) 에 대한 다음과 같은 간단한 튜링 기계를 정의한다.

• \(\mathbf{r}\)(right machine): 모든 \(a_i\) 에 대한 쿼드러플 \(q_0a_iRq_1\) 으로 구성된다. 이 기계는 한 칸 오른쪽으로 움직이고 멈춘다.
• \(\mathbf{l}\)(left machine): 모든 \(a_i\) 에 대한 쿼드러플 \(q_0a_iLq_1\) 으로 구성된다. 이 기계는 한 칸 왼쪽으로 움직이고 멈춘다.
• \(\mathbf{a}_j\)(constant machine): 모든 \(a_i\) 에 대한 쿼드러플 \(q_0a_ia_jq_1\) 으로 구성된다. 이 기계는 처음 스캔된 기호를 \(a_j\) 로 바꾸고 멈춘다.

이러한 기초 기계를 기반으로 다음과 같은 기계를 정의한다.

기계	정의	다이어그램
\(\enspace \mathbf{P} \enspace\)	첫 스캔된 스퀘어의 오른쪽으로 첫 빈칸을 찾는다. 알파벳 \(\{a_0, \dots, a_k\}\) 에 대하여 \(\mathbf{P}\) 의 쿼드러플은 모든 \(a_i\) 에 대한 \(q_0a_iRq_1\) 과 모든 \(a_i \neq a_0\) 에 대한 \(q_1a_ia_iq_0\) 이다.
\(\enspace \Lambda \enspace\)	첫 스캔된 스퀘어의 왼쪽으로 첫 빈칸을 찾는다.
\(\enspace \rho \enspace\)	첫 스캔된 스퀘어의 오른쪽으로 첫 빈칸이 아닌 스퀘어를 찾는다.
\(\enspace \lambda \enspace\)	첫 스캔된 스퀘어의 왼쪽으로 첫 빈칸이 아닌 스퀘어를 찾는다.

주요 튜링 기계들

튜링 기계를 쉽게 표기하기 위하여 다음과 같이 정의한다.

• \(\ssim\): 임의의 기호
• \(B \dots B\): 빈칸의 열
• \(B \dots\): 빈칸 우측의 모든 것
• \(\dots B\): 빈칸 좌측의 모든 것
• \(W\): 빈칸이 아닌 기호로 구성된 비어있지 않은 단어
• \(X\): \(n \geq 1\) 에 대한 \(W_1BW_2B \dots W_n\) (빈칸으로 분리된 \(W\) 열)
• 밑줄 표시된 기호는 스캔된 기호이다.

기계	정의	다이어그램
\(\mathcal{R}\)(right-end machine)	\(\underline{\ssim } XBB \implies \ssim X \underline{B}B\)
\(\mathcal{L}\)(left-end machine)	\(BBX \underline{\ssim } \implies B \underline{B}X \ssim\)
\(\mathbf{T}\)(left- translation machine)	\(\underline{\ssim } BWB \implies \ssim W \underline{B}B\)
\(\sigma\)(shift machine)	\(BW_1BW_2 \underline{B}\implies BW_2 \underline{B}\dots B\) (\(W_1\) 을 지우고 \(W_2\) 를 \(W_1\) 의 위치로 옮긴다.)
\(\mathbf{C}\)(clean-up machine)	\(\ssim BBXBW \underline{B}\implies \\ \ssim W \underline{B}\dots B\) (\(X\) 를 지운다.)
\(\mathbf{K}\)(word-copier)	\(BW \underline{B} \dots \implies BWBW \underline{B}\dots\)
\(\mathbf{K} _n\)(n-shift copier)	\(BW_nBW _{n-1}B \dots W_1 \underline{B} \dots \implies \\ BW_nBW _{n-1}B \dots W_1BW_n \underline{B}\dots\)

제한되지 않은 \(\mu\)-연산자(unrestricted \(\mu\)-operator)

\(f\) 가 다음을 만족하면 제한되지 않은 \(\mu\)-연산자에 의하여 \(g\) 로부터 얻어졌다고 한다.

부분 재귀 함수(partial recursive)

초기 함수에서 유한한 수의 치환, 재귀, 제한되지 않은 \(\mu\)-연산자에 의하여 얻어진 함수이다.

문제 5.15

재귀 함수는 부분 재귀이다.

표준 튜링계산가능한(standard turing-computable)

부분 수론적 함수 \(f(x_1, \dots, x_n)\) 가 표준 튜링계산가능하다는 것은 임의의 자연수 \(k_1, \dots, k_n\) 에 대하여 다음을 만족하는 튜링 기계 \(\mathcal{T}\) 가 존재한다는 것이다.

• \(B \overline{k_1}B \overline{k_2} B \dots B \overline{k_n}\) 을 인자띠(argument strip)라고 하자.(일변수 함수에서 인자띠는 \(B \overline{k_1}\) 가 된다.) 이 인자띠는 \(B \overline{(k_1, \dots, k_n)}\) 이다. 이 인자띠를 포함하고 그 오른쪽에는 아무것도 없는 테이프를 잡자. 기계 \(\mathcal{T}\) 는 이 테이프 위에서 시작하고 \(\overline{k_1}\) 의 첫 \(|\) 을 스캔함으로써 시작된다. 그러면 다음이 성립한다.

  1. \(\mathcal{T}\) 가 멈춘다는 것은 \(f(k_1, \dots, k_n)\) 가 정의된 것과 동치이다.

  2. \(\mathcal{T}\) 가 멈추면, 테이프는 \(B \overline{f(k_1, \dots, k_n)}\) 가 뒤따르는 이전 인자띠를 포함한다. 즉, 최종 테이프는 다음과 같다.

     \[ B \overline{k_1}B \overline{k_2} B \dots B \overline{k_n}B \overline{f(k_1, \dots, k_n)} \]

  3. 읽기 헤더는 \(\overline{f(k_1, \dots, k_n)}\) 의 첫 \(|\) 를 스캔하고 있다.

  4. \(\overline{f(k_1, \dots, k_n)}\) 의 오른쪽으로는 빈칸밖에 없다.
  5. 전체 계산동안 읽기 헤더는 인자띠의 왼쪽을 스캔하지 않는다.

\(\mathcal{T}\) 가 위와 같으면 편의상 함수 \(f(x_1, \dots, x_n)\) 를 ST-계산한다(ST-compute)라고 말한다.

정리 5.1

표준 튜링계산가능한 함수는 튜링계산가능하다.

정리 5.2

부분 재귀 함수는 표준 튜링계산가능하다.

따름정리 5.3

부분 재귀 함수는 튜링계산가능하다.

튜링계산가능성의 언어의 산술화

다음과 같이 기호를 산술화한다. 그러므로 모든 기호는 홀수 괴델수를 갖는다.

유한 기호열을 표현식(expression)이라고 하자. 유한 기호열인 표현식 \(u_0, \dots, u_k\) 은 소수 \(p_0, p_1, \dots\)(\(2,3, \dots\)) 와 \(u_i\) 의 괴델수 \(g(u_i)\) 에 대하여 괴델수 \(p _{0}^{g(u_0)}p _{1}^{g(u_1)}\dots p _{k}^{g(u_k)}\) 를 부여받는다.

표현식 \(E_0, \dots, E_m\) 의 유한열에 괴델수 \(p _{0}^{g(E_0)}p _{1}^{g(E_1)}\dots p _{m}^{g(E_m)}\) 을 부여한다.

정리 5.4

다음 수론적 관계와 함수는 원시 재귀이다.

• \(\operatorname{IS}(x)\): \(x\) 는 내부 상태 기호 \(q_u\) 의 괴델수이다.

  \[ (\exists u)_{u<x}(x = 9 + 4u) \]

• \(\operatorname{Sym}(x)\): \(x\) 는 알파벳 기호 \(a_u\) 의 괴델수이다.

  \[ (\exists u)_{u<x}(x = 7 + 4u) \]

• \(\operatorname{Quad}(x)\): \(x\) 는 튜링기계 쿼드러플의 괴델수이다.

  \[ \operatorname{lh}(x) = 4 \land \operatorname{IS}((x)_0) \land \operatorname{Sym}((x)_1) \land \operatorname{IS}((x)_3) \land \\ [\operatorname{Sym}((x)_2) \lor (x)_2 = 3 \lor (x)_2 = 5] \]

• \(\operatorname{TM}(x)\): \(x\) 는 튜링기계(적절한 쿼드러플의 유한열)의 괴델수이다.

  \[ \begin{align}\begin{split} &(\forall u)_{u < \operatorname{lh}(x)}\operatorname{Quad}((x)_u) \land x > 0 \land \\ &(\forall u)_{u < \operatorname{lh}(x)}(\forall v)_{v < \operatorname{lh}(x)}(u \neq v \implies \\ & \qquad [((x)_u)_0 \neq ((x)_v)_0 \lor ((x)_u)_1 \neq ((x)_v)_1])\\ \end{split}\end{align} \tag*{} \]

• \(\operatorname{TD}(x)\): \(x\) 는 테이프 서술의 괴델수이다.

  \[ \begin{align}\begin{split} &x > 1 \land (\forall u)_{u < \operatorname{lh}(x)}[\operatorname{IS}((x)_u) \lor \operatorname{Sym}((x)_u)] \\ & \land (\exists _1u)_{u < \operatorname{lh}(x)}\operatorname{IS}((x)_u) \\ &\land (\forall u)_{u<\operatorname{lh}(x)}(\operatorname{IS}((x)_u) \implies u+1 < \operatorname{lh}(x)) \\ \end{split}\end{align} \tag*{} \]

• \(\operatorname{Cons}(x, y, z)\); \(x\) 와 \(y\) 는 각각 테이프 서술 \(\alpha\) 와 \(\beta\) 의 괴델수이고, \(z\) 는 \(\alpha\) 를 \(\beta\) 로 변환하는 튜링기계 쿼드러플의 괴델수이다.

  \[ \begin{align} & \operatorname{TD}(x) \land \operatorname{TD}(y) \land \operatorname{Quad}(z) \land (\exists w)_{w < \operatorname{lh}(x) \dotdiv 1}[\operatorname{IS}((x)_w)\\ & \land (x)_w = (z)_0 \land (x) _{w+1} = (z)_1 \land \\ & \text{I}\begin{cases} ([\operatorname{Sym}((z)_2) \land (y) _{w+1} = (z)_2 \land (y)_w = (z)_3 \land \operatorname{lh}(x) = \operatorname{lh}(y) &\\ \land (\forall u)_{u< \operatorname{lh}(x)}(u \neq w \land u \neq w + 1 \implies (x)_u = (y)_u)] \lor &\\ \end{cases} \\ & \text{II} \begin{cases} &[(z)_2 = 3 \land (y)_w = (x) _{w+1} \land (y) _{w+1} = (z)_3 \land \\ &(\forall u)_{u < \operatorname{lh}(x)}(u \neq w \land u \neq w + 1 \implies (y)_u = (x)_u ) \land \\ & ([w + 2 < \operatorname{lh}(x) \land \operatorname{lh}(y) = \operatorname{lh}(x)] \lor [w + 2 = \operatorname{lh}(x) \land \\ & \operatorname{lh}(y) = \operatorname{lh}(x) + 1 \land (y) _{w+2} = 7])] \lor \\ \end{cases} \\ & \text{III}\begin{cases} & [(z)_2 = 5 \land \{[w \neq 0 \land (y) _{w \dotdiv 1} = (z)_3 \land (y)_w = (x) _{w \dotdiv 1}\\ & \land \operatorname{lh}(y) = \operatorname{lh}(x) \land (\forall u)_{u < \operatorname{lh}(x)}(u \neq w \dotdiv 1 \land u \neq w \implies \\ & (y)_u = (x)_u)] \lor [w = 0 \land (y)_0 = (z)_3 \land (y)_1 = 7 \land \\ & \operatorname{lh}(y) = \operatorname{lh}(x) + 1 \land (\forall u) _{0 < u < \operatorname{lh}(x)}(y) _{u+1} = (x)_u] \}])] \\ \end{cases} \\ \end{align} \]

  \(\text{I}\) 는 쿼드러플 \(q_ja_ia_kq_r\), \(\text{II}\) 는 쿼드러플 \(q_ja_iRq_r\), \(\text{III}\) 는 쿼드러플 \(q_ja_iLq_r\) 에 대응된다.

• \(\operatorname{NTD}(x)\): \(x\) 는 숫자 테이프 서술의 괴델수이다. 숫자 테이프 서술이란 비어있거나 빈칸으로 구성된 \(E_1\) 과 \(E_2\) 에 대한 \(E_1 \overline{k}E_2\) 의 형태를 갖는 테이프와 임의의 헤드 위치를 갖는 테이프 설명이다.

  \[ \begin{align}\begin{split} &\operatorname{TD}(x) \land (\forall u)_{u < \operatorname{lh}(x)} (\operatorname{Sym}((x)_u) \implies (x)_u = 7 \lor (x)_u = 11) \\ & \land (\forall u)_{u< \operatorname{lh}(x)}(\forall v)_{v < \operatorname{lh}(x)}(\forall w)_{w < \operatorname{lh}(x)}(u < v \land v < w \land (x)_u = 11 \land \\ & (x)_w = 11 \implies (x)_v \neq 7) \land (\exists u) _{u< \operatorname{lh}(x)} ((x)_u = 11) \end{split}\end{align} \tag*{} \]

• \(\operatorname{Stop}(x, z)\): \(z\) 는 튜링 기계 \(\mathcal{T}\) 의 괴델수이고 \(x\) 는 \(\alpha\) 에서 \(\mathcal{T}\) 가 멈추는 테이프 서술 \(\alpha\) 의 괴델수이다.

  \[ \begin{align}\begin{split} \operatorname{TM}(z) \land \operatorname{TD}(x) \land \lnot (\exists u) _{u<\operatorname{lh}(x)} &[\operatorname{IS}((x)_u) \land (\exists v)_{v < \operatorname{lh}(z)}(((z)_v)_0 \\ & = (x)_u \land ((z)_v)_1 = (x) _{u+1})]\\ \end{split}\end{align} \tag*{} \]

• \(\operatorname{Comp}(y, z)\): \(z\) 는 튜링 기계 \(\mathcal{T}\) 의 괴델수이고, \(y\) 는 \(\mathcal{T}\) 의 계산의 괴델수이다.

  \[ \begin{align}\begin{split} &y>1 \land \operatorname{TM}(z) \land (\forall u)_{u < \operatorname{lh}(y)}\operatorname{TD}((y)_u) \land \operatorname{Stop}((y) _{\operatorname{lh}(y) \dotdiv 1}, z) \land \\ & (\forall u)_{u < \operatorname{lh}(y) \dotdiv 1}(\exists w)_{w < \operatorname{lh}(z)}\operatorname{Cons}((y)_u, (y)_{u+1}, (z)_w) \land \\ & (\forall v) _{v < \operatorname{lh}((y)_0)} (\operatorname{IS}(((y)_0)_v) \implies ((y)_0)_v = 9) \\ \end{split}\end{align} \tag*{} \]

• \(\operatorname{Num}(x)\): 단어 \(\overline{x}\), 즉, \(| ^{x+1}\) 의 괴델수.

  \[ \operatorname{Num}(x) = \prod_{u \leq x}^{}p _{u}^{11} \]

• \(\operatorname{TR}(x_1, \dots, x_n)\): n-튜플 \((x_1, \dots, x_n)\) 의 테이프 서술 \(\overline{(x_1, \dots, x_n)}\) 의 괴델수.

  \[ \operatorname{TR}(x_1, \dots, x_n) = \operatorname{Num}(x_1) * 2 ^{7} * \\ \operatorname{Num}(x_2) * 2 ^{7} * \dots * 2 ^{7} * \operatorname{Num}(x_n) \]

• \(U(y)\): \(y\) 가 숫자 테이프 서술의 계산의 괴델수이면 \(U(y)\) 는 최종 테이프에서 표현되는 수이다. 가정이 성립하지 않아도 \(U(y)\) 가 정의는 되지만 그 값은 의미없다.

  \[ U(y) = \left[ \sum_{u < \operatorname{lh}((y) \operatorname{lh}(y) \dotdiv 1)}^{} \overline{\operatorname{sg} }(|((y) _{\operatorname{lh}(y) \dotdiv 1})_u - 11) \right] \dotdiv 1 \]

  최종 테이프에서 \(| ^{w+1}\) 에 의하여 표현되는 수를 \(w\) 라고 하자. \(U(y)\) 의 계산은 최종 테이프에서 나타는 모든 \(|\) 을 센다. 이는 합 \(w+1\) 이 되고 마지막에 \(1\) 을 빼서 \(w\) 를 얻는다.

• \(T_n(z, x_1, \dots, x_n, y)\): \(y\) 는 계산이 테이프 \((x_1, \dots, x_n)\) 에서 \(\overline{x_1}\) 의 첫 \(|\) 를 스캔하는 것으로 시작하여 숫자 테이프 서술로 끝나는 괴델수 \(z\) 의 튜링기계의 계산의 괴델수이다.

  \[ \operatorname{Comp}(y, z) \land (y)_0 = 2 ^{9} * \operatorname{TR}(x_1, \dots, x_n) \land \operatorname{NTD}((y)_{\operatorname{lh}(y) \dotdiv 1}) \]

  \(n=1\) 일 때 \(\operatorname{TR}(x_1, \dots, x_n)\) 를 \(\operatorname{Num}(x_1)\) 으로 바꾼다. (\(T_n(z, x_1, \dots, x_n, y_1)\) 이고 \(T_n(z, x_1, \dots, x_n, y_2)\) 이면 \(y_1 = y_2\) 이다.)

정리 5.5

\(\mathcal{T}\) 가 수론적 함수 \(f(x_1, \dots, x_n)\) 를 계산하는 튜링 기계이고 \(e\) 가 \(\mathcal{T}\) 의 괴델수이면 다음이 성립한다.

따름정리 5.6

튜링계산가능한 함수는 부분 재귀이다.

따름정리 5.7

튜링계산가능한 함수는 부분 재귀 함수과 동일하다.

따름정리 5.8

전 부분 재귀(total partial recursive) 함수는 재귀이다.

따름정리 5.9

임의의 전 수론적(total number-theoretic) 함수 \(f\) 에 대하여 \(f\) 가 재귀인 것은 \(f\) 가 튜링계산가능한 것과 동치이다.

따름정리 5.10

수론적 함수가 튜링계산가능한 것과 표준 튜링계산가능한 것은 동치이다.

따름정리 5.11 클레이니의 표준형 정리(Kleene's Normal Form Theorem)

모든 자연수에 대하여 \(z\) 를 변화시키면, \(U(\mu yT_n(z, x_1, \dots, x_n, y))\) 가 모든 \(n\)변수 부분 재귀 함수를 나열한다.

따름정리 5.12

임의의 재귀 관계 \(R(x_1, \dots, x_n, y)\) 을 잡자. 그러면 모든 자연수 \(x_1, \dots, x_n\) 에 대하여 다음을 만족하는 자연수 \(z_0\) 와 \(v_0\) 가 존재한다.

1. \((\exists y)R(x_1, \dots, x_n, y)\) 는 \((\exists y)T_n(z_0, x_1, \dots, x_n, y)\) 와 동치이다.
2. \((\forall y)R(x_1, \dots, x_n, y)\) 는 \((\forall y)\lnot T_n(v_0, x_1, \dots, x_n, y)\) 와 동치이다.

문제 5.19

\(R(x_1, \dots, x_n, y, z)\) 이 재귀 관계이면 모든 자연수 \(x_1, \dots, x_n\) 에 대하여 다음을 만족하는 자연수 \(z_0\) 과 \(v_0\) 가 존재한다.

1. \((\forall z)(\exists y)R(x_1, \dots, x_n, y, z)\) 는 \((\forall z)(\exists y)T _{n+1}(z_0, x_1, \dots, x_n, z, y)\) 와 동치이다.
2. \((\exists z)(\forall y)R(x_1, \dots, x_n, y, z)\) 는 \((\exists z)(\forall y)\lnot T _{n+1}(v_0, x_1, \dots, x_n, z, y)\) 와 동치이다.

따름정리 5.13

1. \((\exists y)T_n(x_1, x_1, x_2, \dots , x_n, y)\) 는 재귀가 아니다.
2. \((\exists y)T_n(z, x_1, \dots , x_n, y)\) 는 재귀가 아니다.

정지 문제(halting problem)

튜링 기계 \(\mathcal{T}\) 에 대한 정지 문제는 각 테이프 서술 \(\beta\) 에 대하여 \(\mathcal{T}\) 가 \(\beta\) 에 적용가능한지, 즉, \(\beta\) 에서 시작하는 \(\mathcal{T}\) 의 계산이 존재하는지 판정하는 문제이다. 이 정지 문제에 요구되는 알고리즘은 다음과 같은 계산가능한 함수 \(H _{\mathcal{T}}\) 이다.

주어진 테이프 서술 \(\beta\) 에 대하여 \(\mathcal{T}\) 가 \(\beta\) 에 적용가능한지 판정하는 알고리즘이 존재하면 \(\mathcal{T}\) 에 대한 정지문제가 알고리즘적으로 해결가능하다(algorithmically solvable)고 한다.

튜링 알고리즘을 알고리즘의 정확한 대응물로 받아들인다면(확장된 처치의 논제), \(\mathcal{T}\) 에 대한 정지 문제가 알고리즘적으로 해결가능하다는 것은 함수 \(H _{\mathcal{T}}\) 가 튜링계산가능한 것, 또는 따름정리 5.9 에 의하여 그와 동등하게, 재귀라는 것과 동치이다.

함수 \(H _{\mathcal{T}}\) 가 재귀이면 \(\mathcal{T}\) 에 대한 정지 문제가 재귀적으로 해결가능하다(recursively solvable)고 한다. \(H_{\mathcal{T}}\) 가 재귀가 아니면, \(\mathcal{T}\) 에 대한 정지문제가 재귀적으로 해결불가능(recursively unsolvable)하다고 한다.

정리 5.14

재귀적으로 해결불가능한 정지 문제를 갖는 튜링 기계가 존재한다.

다음과 같이 정의한다.

함수 \(\phi _{z}^{n}\) 의 \(z\) 를 인덱스(index)라고 한다.

정리 5.15 Iteration Theorem(s-m-n Theorem)

임의의 양의 정수 \(m\) 과 \(n\) 에 대하여 다음을 만족하는 원시 재귀 함수 \(s _{n}^{m}(z, y_1, \dots, y_m)\) 이 존재한다.

따름정리 5.16

임의의 부분 재귀 함수 \(f(x_1, \dots, x_n, y_1, \dots, y_m)\) 에 대하여 다음이 성립하는 재귀 함수 \(g(y_1, \dots, y_m)\) 가 존재한다.

보편 튜링 기계(universal turing machine)

부분 재귀 함수 \(U(\mu yT_1(z, x, y))\) 가 괴델수 \(e\) 의 튜링 기계 \(\mathcal{V}\) 에 의하여 계산된다고 하자. 정리 5.5 에 의하여 \(U(\mu yT_1(z, x, y)) = U(\mu yT_2(e,z,x,y))\) 이 성립한다. 다음이 성립하므로 \(\mathcal{V}\) 는 보편적이다.

1. \(\mathcal{V}\) 는 모든 일변수 부분 재귀 함수 \(f(x)\) 를 계산할 수 있다.

   \(z\) 가 \(f\) 를 계산하는 튜링기계의 괴델수이면 \(\mathcal{V}\) 는 테이프 \(\overline{(z,x)}\) 위에서 시작하여 \(U(\mu yT_1(z, x, y)) = f(x)\) 를 계산할 수 있다.

2. \(\mathcal{V}\) 는 임의의 부분 재귀 함수 \(h(x_1, \dots, x_n)\) 를 계산할 수 있다.

   \(h\) 를 계산하는 튜링 기계의 괴델수를 \(v_0\) 라고 하고, \(f(x) = h((x)_0, (x)_1,\dots ,(x) _{n-1})\) 라고 하자. 따름정리 5.16 을 부분 재귀 함수 \(U(\mu y T_n(v, (x)_0, (x)_1, \dots ,(x) _{n-1}, y))\) 에 적용하면 \(U(\mu yT_n(v, (x)_0, (x)_1, \dots , (x)_{n-1}, y)) = \phi _{g(v)}^{1}(x)\) 을 만족하는 재귀 함수 \(g(v)\) 를 얻는다. 그러므로 \(f(x) = \phi _{g(v)}^{1}(x)\) 이다. 그러면 \(h(x_1, \dots, x_n)\) 는 \(\mathcal{V}\) 를 테이프 \(\overline{(g(v_0), p _{0}^{x_1}\dots p _{n-1}^{x_n})}\) 에 적용함으로써 계산된다.

산술 계층(Kleene–Mostowski hierarchy, arithmetical hierarchy)

재귀 관계 \(R(x_1, \dots, x_n, y_1, \dots, y_m)\) 에 대한 다음과 같은 wff 배열을 생각하자.

\(\Sigma _{0}^{n} = \Pi _{0}^{n}\) 를 모든 \(n\)항 재귀 관계 집합으로 정의한다.

\(k>0\) 에 대하여 \(\Sigma _{k}^{n}\) 을 프리넥스 형태의 \((\exists y_1)(\forall y_2)\dots (Q y_k)R(x_1, \dots, x_n, y_1, \dots, y_k)\) 로 표현가능한 모든 \(n\)항 관계의 집합으로 정의한다. \((Qy_k)\) 는 \(k\) 가 홀수이거나 짝수일 때 \((\exists y_k)\) 또는 \((\forall y_k)\) 이다.

\(\Pi _{k}^{n}\) 를 프리넥스 형태의 \((\forall y_1)(\exists y_2)\dots (Qy_k)R(x_1, \dots, x_n, y_1, \dots, y_k)\) 로 표현가능한 모든 \(n\)항 관계의 집합으로 정의한다.

이제 위 배열을 다음과 같이 쓸 수 있다.

이 관계들의 계층의 배열을 산술 계층이라고 한다.

정리 5.17

1. 산술 계층의 어떠한 형태로든 표현가능한 모든 관계는 그것보다 낮은 행의 형태로 표현가능하다. 즉, 모든 \(j > k\) 에 대하여 다음이 성립한다.

   \[ \Sigma _{k}^{n} \subseteq \Sigma _{j}^{n} \cap \Pi _{j}^{n} \qquad \Pi_{k}^{n} \subseteq \Sigma_{j}^{n} \cap \Pi_{j}^{n} \]

2. \(\Sigma_{0}^{n}\) 을 제외하고 같은 행에서 다른 형태로 표현불가능한 관계가 존재한다. 즉, \(k>0\) 에 대하여 다음이 성립한다.

   \[ \Sigma_{k}^{n} - \Pi_{k}^{n} \neq \varnothing \qquad \Pi_{k}^{n} - \Sigma_{k}^{n} \neq \varnothing \]

3. 모든 산술적 관계는 이들 형태 중 최소한 하나로 표현가능하다.

4. (Post) 임의의 관계 \(Q(x_1, \dots, x_n)\) 에 대하여 다음은 동치이다.

   • \(Q\) 가 재귀이다.
   • \(Q\) 와 \(\lnot Q\) 가 재귀인 \(R\) 에 대한 형태 \((\exists y_1)R(x_1, \dots, x_n, y_1)\) 로 표현가능하다.

   즉, \(\Sigma_{1}^{n} \cap \Pi_{1}^{n} = \Sigma_{0}^{n}\) 이다.

5. \(Q_1 \in \Sigma_{k}^{n}\) 이고 \(Q_2 \in \Sigma_{k}^{n}\) 이면 \(Q_1 \lor Q_2\) 과 \(Q_1 \land Q_2\) 이 \(\Sigma_{k}^{n}\) 에 속한다.

   \(Q_1 \in \Pi_{k}^{n}\) 이고 \(Q_2 \in \Pi_{k}^{n}\) 이면 \(Q_1 \lor Q_2\) 과 \(Q_1 \land Q_2\) 이 \(\Pi_{k}^{n}\) 에 속한다.

6. 4) 와 대조되게 \(k>0\) 에 대하여 다음이 성립한다.

   \[ \left( \Sigma_{k+1}^{n} \cap \Pi_{k+1}^{n} \right) - \left( \Sigma_{k}^{n} \cup \Pi_{k}^{n} \right) \neq \varnothing \]

정리 5.18 재귀 정리(Recursion Theorem)

\(n>1\) 이고 \(f(x_1, \dots, x_n)\) 가 부분 재귀 함수이면 다음을 만족하는 자연수 \(e\) 가 존재한다.

따름정리 5.19 고정점 정리(Fixed-Point Theorem)

\(h(x)\) 가 재귀이면 \(\phi _{e}^{1} = \phi _{h(e)}^{1}\) 를 만족하는 \(e\) 가 존재한다.

따름정리 5.20 라이스의 정리(Rice's Theorem)(Rice, 1953)

최소한 하나의, 그러나 전부는 아닌, 일변수 부분 재귀 함수로 구성된 집합 \(\mathcal{F}\) 에 대하여 집합 \(A = \{u : \phi _{u}^{1} \in \mathcal{F}\}\) 는 재귀가 아니다.

재귀적으로 열거가능한(recursively enumerable)

자연수 집합 \(A\) 가 재귀적으로 열거가능하다는 것은 \(A = \varnothing\) 이거나 재귀 함수의 치역인 것과 동치이다.

정리 5.21

1. 집합 \(B\) 가 r.e. 인 것은 \(x \in B\) 가 재귀인 \(R\) 에 대한 형태 \((\exists y)R(x, y)\) 로 표현가능하다는 것과 동치이다. (\(R\) 이 원시 재귀여도 된다.)
2. \(B\) 가 r.e. 인 것은 \(B = \varnothing\) 이거나 부분 재귀 함수의 치역인 것과 동치이다. (공함수가 부분 재귀이고 공집합을 치역으로 가지므로 \(B =\varnothing\) 라는 조건을 생략해도 된다.)
3. \(B\) 가 r.e. 인 것과 \(B\) 가 부분 재귀 함수의 정의역인 것은 동치이다.
4. \(B\) 가 재귀인 것은 \(B\) 와 여집합 \(\overline{B}\) 가 r.e. 인 것은 동치이다. (자연수 집합 \(\omega\) 에 대하여 \(\overline{B} = \omega -B\) 이다.)
5. 집합 \(K = \{x : (\exists y) T_1(x,x,y) \}\) 은 r.e. 이지만 재귀가 아니다.

해결불가능한 문제(unsolvable)

문제를 해결할 효과적인 절차가 존재하지 않으면 문제가 해결불가능하다고 한다.