정지 문제

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사적 배경
3. 정지 문제의 정의와 증명
4. 정지 문제의 응용 및 확장
참조

1. 개요

정지 문제는 주어진 프로그램과 입력에 대해 해당 프로그램이 유한 시간 내에 멈출지, 아니면 무한히 실행될지를 판별하는 문제이다. 1900년 다비트 힐베르트가 제시한 문제와 1930년대 알론조 처치, 앨런 튜링 등의 연구를 통해 결정 불가능성이 증명되었다. 튜링은 귀류법과 대각선 논법을 사용하여 정지 문제가 해결 불가능함을 증명했으며, 이는 계산 불가능 문제의 첫 번째 예시로 역사적으로 중요한 의미를 지닌다. 정지 문제는 프로그램의 종료를 보장하는 데 어려움을 야기하며, 라이스 정리, 괴델의 불완전성 정리 등과도 관련이 있다. 정지 문제의 변형 및 오라클 기계, 손실성 튜링 기계 등의 확장된 개념도 존재하며, 휴리스틱을 통한 근사적인 해결 시도도 이루어지고 있다.

더 읽어볼만한 페이지

계산 이론 - 튜링 완전
튜링 완전은 계산 이론에서 시스템이 튜링 기계와 동등한 계산 능력을 갖춰 튜링 기계가 계산할 수 있는 모든 함수를 계산하고 범용 튜링 기계를 시뮬레이션할 수 있음을 의미하며, 튜링 동등이라고도 한다.
계산 이론 - 디지털 물리학
디지털 물리학은 우주를 거대한 디지털 컴퓨터로 보고 정보 이론, 통계 역학, 양자역학 등을 융합하여 우주의 작동 방식을 디지털 계산 과정으로 설명하려는 이론적 관점이다.
계산 가능성 이론 - 처치-튜링 논제
처치-튜링 논제는 모든 효과적인 계산 과정이 튜링 기계로 수행될 수 있다는 가설로, 알고리즘과 계산 가능성의 본질에 대한 논의를 촉발하며 컴퓨터 과학과 철학 분야에서 활발히 연구되고 있다.
계산 가능성 이론 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
논리학 - 모순
모순은 논리학, 철학, 과학 등 다양한 분야에서 사용되는 개념으로, 서로 상반되는 두 가지 주장이나 사실이 동시에 존재하는 상태를 의미하며, 특히 헤겔과 마르크스의 변증법적 유물론에서 사물의 내재적 대립으로서 역사 발전의 원동력으로 간주된다.
논리학 - 특수
특수는 철학에서는 개별적이고 구체적인 존재를, 언어학에서는 눈에 띄는 또는 예외적인 의미를 가지며, 사회적으로 특별함이 중요하게 여겨지기도 한다.

정지 문제
개요
유형	결정 문제
연구 분야	계산 복잡도 이론, 계산 가능성 이론
해결 방법	해결 불가능
역사
제시 시기	1936년
제시자	앨런 튜링
성질
완전성	튜링 완전성
같이 보기
관련 항목	라이스의 정리 정지 문제의 증명 바쁜 비버 콜모고로프 복잡도 처치-튜링 명제

2. 역사적 배경

정지문제는 처음으로 증명된 판정불가능한 문제라는 점에서 역사적으로 중요한 의미를 갖는다. (튜링의 증명은 1936년 5월에 출판되었으나, 알론조 처치는 1936년 4월에 람다 셈법을 이용하여 판정불가능한 문제가 존재함을 증명하였다.) 이 문제 이후로, 수많은 다른 문제들도 환원과 같은 방법을 사용하여 판정불가능함이 증명되었다.

1900년 다비트 힐베르트는 파리에서 열린 제2차 국제 수학자 회의에서 힐베르트의 문제로 알려진 23가지 문제를 제시했다. 이 중 두 번째 문제는 페아노 공리의 일관성을 증명하는 것으로, 수학의 엄밀성과 관련된 중요한 문제였다.^[5]
1920년부터 1921년까지 에밀 포스트는 태그 시스템의 정지 문제를 연구하며, 이를 해결 불가능한 문제의 후보로 고려했다.^[6] 이 문제의 해결 불가능성은 나중에 마빈 민스키에 의해 증명되었다.
1928년 힐베르트는 볼로냐 국제 회의에서 자신의 두 번째 문제를 재구성하여, 수학의 완전성, 일관성, 결정 가능성에 대한 세 가지 질문을 던졌다. 세 번째 질문이 바로 '결정 문제(Entscheidungsproblem)'이다.
1930년 쿠르트 괴델은 힐베르트의 첫 두 질문(완전성, 일관성)에 대한 답을 제시하는 증명을 발표했다. 괴델 자신은 이 연구가 힐베르트의 형식주의적 관점과 모순되지 않는다고 생각했다.
1931년 괴델은 Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I|형식적으로 결정 불가능한 명제에 대하여 I^de 논문을 발표했다.^[7]
1935년 4월 19일 알론조 처치는 An Unsolvable Problem of Elementary Number Theory|초등 정수론의 해결 불가능한 문제^영어를 발표했다. 그는 '효과적으로 계산 가능한' 함수의 개념을 일반 재귀 함수 또는 람다 셈법으로 형식화할 수 있다고 제안하고, 람다 셈법에서의 정지 문제(주어진 람다 표현식이 정규 형식을 갖는지 여부)가 효과적으로 계산 불가능함을 증명했다.
1936년 처치는 계산 가능한 함수 개념을 사용하여 '결정 문제'가 해결 불가능하다는 첫 증명을 발표했다.^[8]
1936년 10월 7일 에밀 포스트의 논문 Finite Combinatory Processes. Formulation I|유한 조합 과정. 형식화 I^영어가 접수되었다. 포스트는 자신의 "과정"에 "(C) 정지" 지침을 포함시켰다.
1936년 5월부터 1937년 1월 사이에 앨런 튜링의 논문 On Computable Numbers, with an Application to the Entscheidungsproblem|계산 가능한 수와 결정 문제 응용^영어이 출판되었다.^[9] 튜링은 이 논문에서 기계에 의한 계산 개념을 도입하여 "만족" 문제, "인쇄" 문제, 그리고 '결정 문제' 세 가지가 해결 불가능함을 증명했다. 이는 결정 불가능성이 증명된 결정 문제의 초기 사례 중 하나로 평가받는다.
1939년 J. 바클리 로서는 괴델, 처치, 튜링이 정의한 "효과적인 방법"이 본질적으로 동일함을 지적했다.^[10]
1943년 스티븐 클리니는 완전한 알고리즘 이론을 설명하며, 절차가 반드시 종료되어 '예' 또는 '아니요'라는 명확한 답을 제공해야 한다고 언급했다.
1952년 클리니는 튜링 기계에 대한 정지 문제의 해결 불가능성에 대한 논의를 포함시키며, 기계가 "결국 멈추는지" 여부를 결정하는 알고리즘은 없다고 재구성했다.
1952년 마틴 데이비스는 일리노이 대학교 강의에서 '정지 문제(halting problem)'라는 용어를 사용했으며, 이것이 이 용어의 첫 사용으로 여겨진다.^[11]

많은 문헌에서 정지 문제의 결정 불가능성 증명을 튜링의 1936년 논문으로 돌리지만, 이는 정확하지 않다. 튜링은 1936년 논문을 포함한 어떤 출판물에서도 "정지(halt)"라는 용어를 사용하지 않았다.^[12] "정지 문제"라는 용어가 학술 문헌에 처음 등장한 것은 1957년 로저스(Rogers)의 저술로 보이지만, 로저스는 데이비스(Davis)의 1958년 저술 초고를 참고했다고 밝혔으며, 데이비스는 1952년부터 이 용어를 사용했다고 언급했다.^[11] 따라서 이 용어는 마틴 데이비스에게서 비롯된 것으로 보는 것이 일반적이다. 데이비스는 자신의 1958년 저서에서 정지 문제를 다음과 같이 정의했다.

> "[...] 우리는 [튜링 기계] Z가 주어진 초기 상태에 놓였을 때 결국 정지할지 여부를 결정하고자 한다. 우리는 이 문제를 Z에 대한 정지 문제라고 부른다. [...]

> 정리 2.2 ''정지 문제가 재귀적으로 풀 수 없는 튜링 기계가 존재한다''.

> 관련 문제는 기호 S_i에 대한 간단한 튜링 기계 Z의 ''인쇄 문제''이다."

데이비스 공식화의 가능한 선행 작업으로는 클리니의 1952년 진술이 있으며, 표현만 다를 뿐 본질적으로 같은 내용을 담고 있다.

> 어떤 주어진 기계가 어떤 주어진 상황에서 시작했을 때 결국 멈출지 여부를 결정하는 알고리즘은 없다.

3. 정지 문제의 정의와 증명

계산 가능성 이론에서 정지 문제(Halting problem)는 주어진 프로그램(일반적으로 튜링 기계의 설명으로 제공됨)과 해당 프로그램에 대한 입력이 주어졌을 때, 그 입력으로 프로그램을 실행했을 경우 프로그램이 계산을 끝내고 정지할지, 아니면 영원히 계속 실행될지(무한 루프에 빠지는 등)를 결정하는 판정 문제이다.

예를 들어, 의사 코드로 표현된 다음 두 프로그램을 생각해보자.

프로그램 1:

```text

while (true) continue

```

이 프로그램은 명백히 정지하지 않고 무한 루프를 계속 실행한다.

프로그램 2:

```text

print "Hello, world!"

```

이 프로그램은 "Hello, world!"를 출력하고 즉시 정지한다.

이처럼 간단한 프로그램의 정지 여부는 쉽게 판단할 수 있지만, 프로그램이 복잡해질수록 정지 여부를 예측하기는 매우 어려워진다. 단순히 프로그램을 일정 시간 동안 실행해보는 것만으로는 충분하지 않다. 왜냐하면 프로그램이 아직 실행 중일 때, 이것이 언젠가 정지할 것인지 아니면 영원히 멈추지 않을 것인지 알 수 없기 때문이다.

1936년 앨런 튜링은 튜링 기계 모델을 사용하여, 임의의 프로그램과 그 입력에 대해 정지 여부를 항상 올바르게 판정하는 일반적인 알고리즘은 존재할 수 없음을 증명했다. 즉, 정지 문제는 알고리즘적으로 판정 불가능(undecidable)하다. 이는 컴퓨터 과학과 수학적 논리의 근본적인 한계를 보여주는 중요한 결과이다.

정지 문제의 판정 불가능성은 주로 귀류법과 대각선 논법을 이용하여 증명된다. 증명의 핵심 아이디어는 만약 정지 문제를 해결하는 가상의 알고리즘(예: `halt(프로그램, 입력)`)이 존재한다고 가정하면, 이 알고리즘을 이용하여 자기 자신에 대해 모순된 결과를 내놓는 특수한 프로그램을 구성할 수 있음을 보이는 것이다. 이러한 모순은 처음의 가정, 즉 정지 문제를 해결하는 알고리즘이 존재한다는 가정이 잘못되었음을 의미한다. 정지 문제의 역사적 중요성과 구체적인 증명 방법, 그리고 관련 개념들에 대해서는 하위 섹션에서 더 자세히 다룬다.

3. 1. 정지 문제의 중요성과 의미

정지 문제는 역사적으로 중요한 의미를 가지는데, 이는 판정 불가능하다고 처음으로 증명된 문제이기 때문이다. 앨런 튜링의 증명은 1936년 5월에 출판되었으나, 알론조 처치는 이보다 앞선 1936년 4월에 람다 셈법을 이용하여 판정 불가능한 문제가 존재함을 먼저 증명하였다.

정지 문제의 증명 이후, 수많은 다른 문제들 역시 비슷한 방식을 통해 판정 불가능함이 증명되었다. 이러한 증명에는 주로 환원이라는 기법이 사용된다. 환원은 어떤 새로운 문제를 판정하는 방법이 존재한다고 가정했을 때, 그 방법을 이용하여 이미 판정 불가능하다고 알려진 기존 문제(예: 정지 문제)의 모든 경우를 해결할 수 있음을 보이는 방식이다. 만약 새로운 문제의 판정 방법으로 기존의 판정 불가능한 문제를 풀 수 있다면, 이는 "기존 문제를 풀 수 없다"는 사실과 모순된다. 따라서 가정했던 '새로운 문제를 판정하는 방법'은 존재할 수 없으며, 결국 새로운 문제 역시 판정 불가능하다는 결론에 이르게 된다.

문제

P

가 계산 불가능 문제임을 증명하는 일반적인 방법은 정지 문제를

P

로 환원하는 것이다. 예를 들어, 주어진 자연수에 대한 명제가 참인지 거짓인지 결정하는 일반적인 알고리즘은 존재할 수 없다. 특정 프로그램이 특정 입력을 받았을 때 정지할 것인지에 대한 명제는 자연수에 대한 동등한 명제로 변환될 수 있기 때문이다. 만약 자연수에 대한 모든 명제의 진리 값을 찾는 알고리즘이 존재한다면, 이 변환된 명제의 진리 값도 찾을 수 있어야 하며, 이는 결국 정지 문제를 해결할 수 있다는 의미가 되어 모순이다.

라이스 정리는 이러한 정지 문제의 판정 불가능성을 더욱 일반화한 정리이다. 이 정리는 프로그램이 계산하는 부분 함수가 가지는 어떠한 자명하지 않은 속성에 대해서도, 그 속성을 만족하는지 여부를 일반적으로 판정할 수 있는 절차는 존재하지 않는다고 말한다. 여기서 '자명하지 않은 속성'이란, 모든 프로그램이 만족하거나 혹은 어떤 프로그램도 만족하지 않는 속성을 제외한 모든 속성을 의미한다. 예를 들어, "입력 0에 대해 정지하는가?"는 자명하지 않은 속성이므로 라이스 정리에 따라 판정 불가능하다.

그레고리 차이틴은 Ω라는 정지 확률을 정의했는데, 이는 무작위로 생성된 프로그램이 정지할 확률을 나타내는 실수이다. 이 상수는 정지 문제와 동일한 튜링 차수를 가지며, 정의 가능한 수이지만 계산 가능한 수는 아니다. 즉, Ω의 값을 계산하는 알고리즘은 존재하지 않는다.

정지 문제의 해결 불가능성은 튜링 기계로 대표되는 계산 모델의 근본적인 한계를 보여준다. 이는 처치-튜링 명제가 제시하는 유효 방법으로 달성할 수 있는 것의 범위를 제한하는 중요한 결과이다. 그러나 인간의 상상력으로 생각할 수 있는 모든 기계가 처치-튜링 명제의 적용을 받는 것은 아니다(예: 오라클 기계). 실제 물리 과정이 튜링 기계를 넘어서는 계산 능력을 가질 수 있는지, 그리고 그러한 과정이 하이퍼컴퓨터와 같이 정지 문제 해결에 활용될 수 있는지, 더 나아가 인간의 뇌가 이러한 과정과 관련되어 인간이 정지 문제를 해결할 수 있는지 등은 여전히 열려 있는 질문이다.

3. 2. 증명 개요 (귀류법)

증명은 귀류법을 이용한다. 우선 모든 프로그램을 최소한 하나의 문자열과 연관시킬 수 있는 프로그래밍 언어를 가정한다. 임의의 문자열 i와 임의의 프로그램을 나타내는 문자열 a에 대해, i를 입력으로 프로그램 a를 실행했을 때 그 실행이 끝나면 '''true''', 끝나지 않고 영원히 계속되면 '''false'''를 반환하는 `halt(a, i)`라는 알고리즘이 존재한다고 가정해보자. 이 가상의 `halt` 알고리즘은 어떤 프로그램과 입력에 대해서도 항상 정확한 답(정지 여부)을 내놓는다고 전제한다.

이 가상의 `halt` 알고리즘을 이용하여 다음과 같이 `trouble`이라는 프로그램을 만들 수 있다:

```text

'''function''' trouble(''string'' s)

'''if''' halt(s, s) == '''false'''

'''return true'''

'''else'''

loop forever

```

이 프로그램은 프로그램 문자열 s를 입력받아, 자기 자신(s)을 입력으로 실행했을 때의 정지 여부(`halt(s, s)`)를 확인한다. 만약 `halt(s, s)`가 '''false''' (즉, 프로그램 s를 입력 s로 실행하면 멈추지 않음)를 반환하면, `trouble` 프로그램은 멈춘다 ('''true'''를 반환). 반대로 `halt(s, s)`가 '''true''' (즉, 프로그램 s를 입력 s로 실행하면 멈춤)를 반환하면, `trouble` 프로그램은 무한 루프에 빠져 영원히 멈추지 않는다.

모든 프로그램은 어떤 문자열로 표현될 수 있으므로, 위에서 정의한 `trouble` 프로그램 자체를 나타내는 문자열 t가 존재할 것이다. 이제 이 `trouble` 프로그램에 자기 자신의 문자열 표현인 t를 입력으로 넣어 `trouble(t)`를 실행하면 어떻게 될까? 두 가지 가능성을 따져볼 수 있다.

# `trouble(t)`가 멈춘다고 가정해보자. `trouble` 함수의 정의에 따라, 이는 `halt(t, t)`가 '''false'''를 반환했기 때문이다. 그런데 `halt(t, t)`가 '''false'''라는 것은 정의상 프로그램 t (즉, `trouble` 프로그램)를 입력 t로 실행했을 때 멈추지 않아야 한다는 의미이다. 따라서 `trouble(t)`는 멈추지 않아야 하는데, 이는 처음의 가정("`trouble(t)`가 멈춘다")과 모순된다.

# `trouble(t)`가 멈추지 않고 무한히 실행된다고 가정해보자. `trouble` 함수의 정의에 따라, 이는 `halt(t, t)`가 '''true'''를 반환했기 때문이다. 그런데 `halt(t, t)`가 '''true'''라는 것은 정의상 프로그램 t (즉, `trouble` 프로그램)를 입력 t로 실행했을 때 멈춰야 한다는 의미이다. 따라서 `trouble(t)`는 멈춰야 하는데, 이는 처음의 가정("`trouble(t)`가 멈추지 않는다")과 모순된다.

두 가지 경우 모두 모순이 발생한다. 이는 처음의 가정, 즉 정지 여부를 완벽하게 판정하는 알고리즘 `halt`가 존재한다는 가정이 잘못되었음을 의미한다. 따라서 정지 문제는 알고리즘적으로 해결하는 것이 불가능하다.

이러한 증명 방식은 칸토어의 대각선 논법과 유사한 구조를 가진다. 만약 모든 프로그램과 모든 입력에 대한 `halt` 함수의 결과를 표로 나열한다고 상상할 때, `trouble` 함수는 이 표의 대각선에 해당하는 값(`halt(s, s)`)과 반대로 동작하도록 특별히 구성된다. 이로 인해 `trouble` 함수 자신에 해당하는 행이 그 표 안에 모순 없이 존재할 수 없게 되어, `halt` 함수의 보편성이 깨지게 된다.

3. 3. 정형화된 증명

임의의 프로그램 ''i''가 임의의 입력 ''x''에서 정지하는지 여부를 결정하는 전체 계산 가능한 함수는 존재하지 않는다는 것을 증명하는 것이 목표이다. 즉, 다음 함수 ''h''(정지를 의미하는 "halts")는 계산 가능하지 않다.

:

h(i,x) =\begin{cases}1 & \text{if } \text{  프로그램 }i\text{ 는 입력 }x\text{ 에서 정지, } \\0 & \text{그렇지 않음.}\end{cases}

여기서 ''프로그램 i''는 고정된 튜링 완전 계산 모델의 모든 프로그램의 열거에서 ''i''번째 프로그램을 나타낸다.

f(i,j)		i
f(i,j)		1	2	3	4	5	6
j	1	1	0	0	1	0	1
	2	0	0	0	1	0	0
	3	0	1	0	1	0	1
	4	1	0	0	1	0	0
	5	0	0	0	1	1	1
	6	1	1	0	0	1	0
style="height:12px;"\|
style="height:12px;"\|	f(i,i)	1	0	0	1	1	0
style="height:12px;"\|	g(i)	U	0	0	U	U	0

전체 계산 가능 함수 ''f''에 대한 가능한 값을 2차원 배열로 정렬한 예시. 주황색 셀은 대각선 ''f''(''i'',''i'')를 나타내고, 녹색 셀은 그에 따라 정의되는 ''g''(''i'')의 값을 보여준다. ''U''는 함수 ''g''가 해당 입력 값에 대해 정의되지 않음(즉, 프로그램 ''e''가 정지하지 않음)을 나타낸다.

증명은 두 개의 인수를 갖는 임의의 전체 계산 가능 함수 ''f''가 주어졌을 때, 이 ''f''가 정지 함수 ''h''가 될 수 없음을 보이는 방식으로 진행된다. ''f''를 이용하여 다음과 같은 부분 함수 ''g''를 정의한다. 이 함수 ''g''는 어떤 프로그램 ''e''에 의해 계산 가능하다.

:

g(i) =\begin{cases}0  & \text{if } f(i,i) = 0,\\\text{정의되지 않음} & \text{그렇지 않음.}\end{cases}

''g''가 계산 가능함을 검증하는 것은 다음 구조(또는 그와 동등한 것)에 의존한다:

계산 가능한 서브 프로그램 (''f''를 계산하는 프로그램은 프로그램 ''e''의 서브 프로그램이다),
값 복제 (프로그램 ''e''는 ''g''에 대한 입력 ''i''로부터 ''f''에 대한 입력 ''i'',''i''를 계산한다),
조건 분기 (프로그램 ''e''는 ''f''(''i'',''i'')에 대해 계산하는 값에 따라 두 개의 결과 중 하나를 선택한다),
정의된 결과를 생성하지 않음 (예: 영원히 루프),
값 0을 반환한다.

''e''에 대한 다음 의사 코드는 ''g''를 계산하는 간단한 방법을 보여준다.

procedure e(i):

if f(i, i) == 0 then

return 0

else

loop forever

''g''는 부분 계산 가능하므로, 계산 모델이 튜링 완전하다는 가정에 의해 ''g''를 계산하는 프로그램 ''e''가 존재해야 한다. 이 프로그램 ''e''는 정지 함수 ''h''가 정의된 모든 프로그램 중 하나이다. 증명의 다음 단계는 ''h''(''e'',''e'')가 ''f''(''e'',''e'')와 동일한 값을 가질 수 없음을 보이는 것이다.

''g''의 정의에 따라 다음 두 경우 중 정확히 하나만 성립한다:

''f''(''e'',''e'') = 0 이면 ''g''(''e'') = 0이다. 이 경우 프로그램 ''e''는 입력 ''e''에서 정지하므로, 정의에 따라 ''h''(''e'',''e'') = 1이다.
''f''(''e'',''e'') ≠ 0 이면 ''g''(''e'')는 정의되지 않는다. 이 경우 프로그램 ''e''는 입력 ''e''에서 정지하지 않으므로, 정의에 따라 ''h''(''e'',''e'') = 0이다.

두 경우 모두 ''f''(''e'',''e'') ≠ ''h''(''e'',''e'') 이다. 즉, 함수 ''f''는 최소한 (''e'',''e'')라는 입력에 대해서는 정지 함수 ''h''와 다른 값을 가진다. ''f''는 두 개의 인수를 갖는 ''임의의'' 전체 계산 가능 함수였으므로, 어떤 전체 계산 가능 함수도 정지 함수 ''h''와 동일할 수 없다. 따라서 정지 함수 ''h''는 계산 가능하지 않다.

이 증명은 칸토어의 대각선 논법과 유사하다. 위의 표와 같이 각 자연수에 대해 하나의 열과 하나의 행이 있는 2차원 배열을 상상할 수 있다. ''f''(''i'',''j'')의 값은 열 ''i'', 행 ''j''에 위치한다. ''f''가 전체 계산 가능 함수라고 가정했으므로, 배열의 모든 요소는 ''f''를 사용하여 계산할 수 있다. 함수 ''g''의 구성은 이 배열의 주 대각선을 이용하여 시각화할 수 있다. 배열의 위치 (''i'',''i'')에 0이 있으면 ''g''(''i'')는 0이고, 그렇지 않으면 ''g''(''i'')는 정의되지 않는다. 모순은 ''g'' 자체를 계산하는 프로그램 ''e''에 해당하는 열이 배열에 존재한다는 사실에서 발생한다. 만약 ''f''가 정지 함수 ''h''였다고 가정하면, ''g''(''e'')가 정의될 때 (즉, ''g''(''e'') = 0), 이는 프로그램 ''e''가 입력 ''e''에서 정지함을 의미하므로 ''f''(''e'',''e'') = ''h''(''e'',''e'') = 1이어야 한다. 하지만 ''g''의 정의상 ''g''(''e'') = 0은 ''f''(''e'',''e'') = 0일 때만 가능하므로 모순이다. 반대로, ''g''(''e'')가 정의되지 않을 때, 이는 프로그램 ''e''가 입력 ''e''에서 정지하지 않음을 의미하므로 정지 함수 ''f''(''e'',''e'') = ''h''(''e'',''e'') = 0이어야 한다. 하지만 ''g''의 정의상 ''f''(''e'',''e'') = 0이면 ''g''(''e'') = 0이 되어야 하므로, ''g''(''e'')가 정의되지 않는다는 가정과 모순된다. 두 경우 모두 모순이 발생하므로, 임의의 계산 가능한 함수 ''f''는 정지 함수 ''h''가 될 수 없다.

3. 4. 칸토어의 대각선 논법과의 관계

대각선 논법은 게오르크 칸토어가 집합 S에서 그 멱집합 P(S)로의 전단사 함수가 존재하지 않음을 보이기 위해 사용한 증명 방법이다(칸토어의 정리). 정지 문제가 판정불가능하다는 고전적인 증명 역시 이 대각선 논법을 이용한다.

증명을 이해하기 위해, 모든 프로그램을 나타내는 문자열 'a'와 모든 입력을 나타내는 문자열 'i'에 대해, 프로그램 'a'에 입력 'i'를 주었을 때 프로그램이 정지하면 1 (또는 'true'), 정지하지 않으면 0 (또는 'false')을 값으로 가지는 함수 `halt(a, i)`를 생각해보자. 이 함수의 값들을 표로 배열한다고 상상해 볼 수 있는데, 행(row)은 프로그램을 나타내는 문자열 'a'에 해당하고, 열(column)은 입력 문자열 'i'에 해당한다. 이때, `halt(s, s)`와 같이 프로그램과 입력이 동일한 경우는 이 표의 대각선에 해당하게 된다. 정지 문제 증명은 이 대각선 상의 값들을 이용한다.

정지 문제 증명에서 대각선 논법을 적용하는 과정은 다음과 같다.

1. 프로그램과 자연수의 대응: 모든 컴퓨터 프로그램은 특정 규칙에 따라 고유한 자연수로 표현될 수 있다고 가정한다. 즉, 프로그램 전체의 집합과 자연수 전체의 집합

\mathbb{N}

을 동일시할 수 있다. (실제로는 모든 자연수가 유효한 프로그램에 대응되지는 않지만, 논의를 단순화하기 위해 모든 자연수가 어떤 프로그램을 나타낸다고 가정한다.)

2. 함수 φ 정의: 프로그램 ''A''에 입력 ''x''를 주었을 때의 실행 결과를 나타내는 함수

\phi:\mathbb{N} \times \mathbb{N} \mapsto \{0,1\}

를 다음과 같이 정의한다.

프로그램 ''A''가 입력 ''x''에 대해 실행 후 정지하면 φ(''A'',''x'') = 1
프로그램 ''A''가 입력 ''x''에 대해 실행 후 정지하지 않으면 (무한 루프 등) φ(''A'',''x'') = 0

이 함수를 φ_''A''(''x'')로 표기하기도 한다.

3. 함수 g 정의: 새로운 함수

g:\mathbb{N} \mapsto \{0,1\}

를 다음과 같이 정의한다.

g(''A'') = ￢φ_''A''(''A'')

여기서 "￢"는 논리 부정을 나타내는 기호로, 0을 1로, 1을 0으로 바꾼다. 즉, 함수 g는 프로그램 ''A''가 자기 자신을 입력으로 받았을 때의 정지 여부(φ_''A''(''A''))를 반대로 뒤집은 값을 가진다.

4. 대각선 논법 적용: 대각선 논법에 따르면, 함수 ''g''는 어떤 프로그램 ''M''에 대해서도 φ_''M''과 같아질 수 없다. 즉, ''g'' = φ_''M''을 만족하는 프로그램 ''M''은 존재하지 않는다. 왜냐하면 만약 그런 ''M''이 존재한다면, ''g''(''M'') = φ_''M''(''M'')이 되어야 하는데, ''g''의 정의에 의해 ''g''(''M'') = ￢φ_''M''(''M'') 이므로, φ_''M''(''M'') = ￢φ_''M''(''M'') 이라는 모순이 발생하기 때문이다.

5. 정지 문제 해결 불가능 증명: 만약 정지 문제를 항상 올바르게 판정하는 프로그램 ''H''가 존재한다고 가정해보자. 이 프로그램 ''H''는 입력으로 프로그램 ''A''와 데이터 ''x''를 받아, ''A''(''x'')가 정지하면 YES(1)를, 정지하지 않으면 NO(0)를 출력한다고 하자. 즉, ''H''(''A'',''x'') = φ_''A''(''x'') 이다.

이제 프로그램 ''H''를 이용하여 새로운 프로그램 ''M''을 다음과 같이 구성한다.

''M''(''A'') : ''H''(''A'',''A'')의 결과가 NO(0)이면, 0을 출력하고 정지한다. ''H''(''A'',''A'')의 결과가 YES(1)이면, 무한 루프에 빠져 정지하지 않는다.

이 프로그램 ''M''의 동작을 φ 함수로 표현하면, φ_''M''(''A'')는 ''H''(''A'',''A'')가 NO(0)일 때 1(정지하므로)이고, YES(1)일 때 0(정지하지 않으므로)이다. 이는 정확히 ''g''(''A'') = ￢φ_''A''(''A'') = ￢''H''(''A'',''A'') 와 같다. 즉, ''g'' = φ_''M'' 이 성립한다.

하지만 앞서 대각선 논법에 의해 ''g'' = φ_''M''을 만족하는 프로그램 ''M''은 존재할 수 없다는 것을 보였다. 따라서, 정지 문제를 해결하는 프로그램 ''H''가 존재한다는 초기 가정이 잘못되었으며, 정지 문제는 판정불가능하다는 결론에 도달한다.

이 과정을 시각적으로 이해하기 위해, 함수 ''f''(''i'',''j'') (여기서는 φ(''i'',''j''))의 값을 2차원 배열로 나타낸 것을 생각해 볼 수 있다. ''i''는 프로그램 번호(행), ''j''는 입력 번호(열)이다.

f(i,j)		i (프로그램 번호)
f(i,j)		1	2	3	4	5	6
j (입력 번호)	1	1	0	0	1	0	1
	2	0	0	0	1	0	0
	3	0	1	0	1	0	1
	4	1	0	0	1	0	0
	5	0	0	0	1	1	1
	6	1	1	0	0	1	0
style="height:12px;"\|
style="height:12px;"\|	f(i,i) (대각선)	1	0	0	1	1	0
style="height:12px;"\|	g(i) = ￢f(i,i)	0	1	1	0	0	1

함수 ''f''(''i'',''j'') (프로그램 ''i''가 입력 ''j''에서 정지하면 1, 아니면 0)의 가상적인 값 배열. 주황색 셀은 대각선 ''f''(''i'',''i'')를 나타낸다. 함수 ''g''(''i'')는 이 대각선 값의 부정을 취한 것이다 (녹색 셀). 대각선 논법은 이 함수 ''g''가 배열의 어떤 행(어떤 프로그램 ''M''에 대한 ''f''(''M'',''j'') = φ_''M''(''j''))과도 일치할 수 없음을 보여준다.

결국, 정지 문제의 해결 불가능성은 계산 가능성 이론의 근본적인 결과이며, 이는 대각선 논법을 통해 명확하게 증명될 수 있다.

4. 정지 문제의 응용 및 확장

정지 문제는 계산 가능성 이론의 핵심적인 문제 중 하나로, 그 자체의 이론적 중요성 외에도 다양한 분야에 응용되거나 확장된 형태로 연구되고 있다. 실제 프로그래밍에서는 정지 문제의 한계를 인식하면서도 무한 루프를 활용하거나, 반대로 프로그램의 종료를 보장하기 위한 여러 기법들이 사용된다.^[1]^[2]^[3] 또한, 정지 문제의 결정 불가능성은 괴델의 불완전성 정리와 같은 다른 근본적인 수학적 결과와도 연결된다.

정지 문제는 다양한 형태로 일반화되거나 변형되어 연구되기도 한다. 예를 들어, 특정 프로그램이 모든 입력에 대해 정지하는지를 묻는 범용 정지 문제, 일부 입력에 대해서만 정지 여부를 판별하는 부분 해법 인식 문제, 테이프 내용이 손실될 수 있는 튜링 기계에서의 정지 문제, 그리고 정지 문제를 풀 수 있는 가상의 오라클 기계를 가정한 문제 등이 있다.^[19] 이러한 변형 문제들은 표준 정지 문제와 동일하거나 더 높은 수준의 계산 복잡성을 가지기도 한다.

비록 정지 문제를 모든 경우에 대해 완벽하게 해결하는 알고리즘은 존재하지 않지만, 특정 프로그램의 종료 여부를 증명하거나, 자동화된 휴리스틱 기법을 통해 근사적인 해답을 찾으려는 연구, 즉 자동 종료 분석 분야도 활발히 진행되고 있다.^[15]^[16]^[17]^[18]

4. 1. 프로그래밍의 함의

정지 문제의 어려움은 어떤 프로그램과 입력이 주어지든 항상 정지 여부를 판별하는 결정 절차가 존재해야 한다는 요구 사항에서 비롯된다. 특정 프로그램과 특정 입력에 대해서는 정지할 수도, 정지하지 않을 수도 있다. 예를 들어, 항상 "정지한다"고 답하는 알고리즘과 항상 "정지하지 않는다"고 답하는 알고리즘을 생각할 수 있는데, 특정 경우에는 둘 중 하나가 정답이겠지만, 어떤 것이 맞는지는 알 수 없다. 따라서 이 두 알고리즘 모두 일반적인 정지 문제를 해결하지는 못한다.

실제 프로그래밍에서는 무한 루프가 유용하게 쓰이기도 한다. 예를 들어, 이벤트 루프는 보통 무한 루프로 작성된다.^[1] 하지만 대부분의 서브루틴은 종료되도록 설계하는 것이 일반적이다.^[2] 특히, 실시간 컴퓨팅과 같이 시간 제약이 중요한 분야에서는 프로그래머들이 서브루틴이 단순히 종료하는 것을 넘어, 정해진 시간 안에 반드시 종료하도록 만들기 위해 노력한다.^[3]

이러한 종료 보장을 위해, 프로그래머들은 때때로 튜링 완전 언어를 사용하더라도 MISRA C나 SPARK와 같이 특정 규칙을 따르는 제한된 방식으로 코드를 작성하기도 한다. 이렇게 하면 프로그램이 정해진 시간 안에 종료된다는 것을 증명하기 쉬워진다. 다른 방법으로는 최소 권한의 원칙에 따라 의도적으로 튜링 완전하지 않은 언어를 사용하는 것이다. 예를 들어 Coq와 같은 언어는 모든 서브루틴이 반드시 종료함을 보장하기도 한다.

4. 2. 괴델의 불완전성 정리와의 관계

정지 문제의 결정 불가능성을 이용하여 괴델의 제1 불완전성 정리를 증명할 수 있다.

계산 모델을 적절하게 산술화하면, "프로그램 ''M''은 입력 ''x'' 하에서 정지한다"라는 술어 ''Halt''(''M'',''x'')가 Σ₁ 술어가 되도록 할 수 있다. 정지 문제의 결정 불가능성은 이 술어가 Π₁ 술어가 아님을 말하고 있다. 따라서 "프로그램 ''M''은 입력 ''x'' 하에서 '''정지하지 않는다'''"라는 술어는 Π₁이지만 Σ₁이 아니다.

술어 논리를 적절하게 산술화해 둔다. ''T''를 로빈슨 산술을 포함하는 재귀적이고 Σ₁ 건전한 이론으로 한다. 여기서 ''T''가 재귀적이란, "''x''는 ''T''의 공리의 코드이다"라는 술어가 재귀적임을 말한다. 또한 ''T''가 Σ₁ 건전하다는 것은, 거짓인 Σ₁ 문을 증명하지 않음을 말한다. "''x''는 ''T''에서 증명 가능한 논리식의 코드이다"라는 술어 ''Pr''(''x'')는 재귀적 가산이며, 따라서 Σ₁ 술어이다.

''T''가 임의의 Π₁ 문을 증명하거나 반증한다고 가정하고 모순을 이끌어낸다. 술어 ''Halt''(''M'',''x'')를 정의하는 Σ₁ 논리식 ''halt''(''M'',''x'')를 취한다. 여기서 ¬''halt''(''M'',''x'')는 ''T'' 상에서 Π₁ 논리식임에 주의하라. ''T''는 Σ₁ 완전하고 무모순하므로 Π₁ 건전하다. 가정에 따라 ''T''는 임의의 Π₁ 문을 증명하거나 반증하므로, ''T''는 Π₁ 완전하다. 따라서, 임의의 프로그램 ''M''과 입력 ''x''에 대해, 이하는 동치이다.

¬''Halt''(''M'',''x'')가 성립한다.
¬''halt''(''M'',''x'')는 ''T''에서 증명 가능하다.
''Pr''(¬''halt''(''M'', ''x''))가 성립한다.

그런데 ''Pr''(¬''halt''(''M'', ''x''))는 Σ₁ 술어이므로, ¬''Halt''(''M'',''x'')도 Σ₁ 술어이다. 이는 위에 언급한 것과 모순된다.

이 증명은 직관적으로 다음과 같은 의미이다. 만약 ''T''가 임의의 문을 증명하거나 반증한다면(즉, 완전하다면), ''T''의 정리를 열거하는 프로그램을 실행하여 ''halt''(''M'',''x'') 또는 ¬''halt''(''M'',''x'') 형태의 정리가 나타나면 YES 또는 NO를 출력하고 정지하는 방법으로 정지 문제를 긍정적으로 해결할 수 있다. (이 프로그램의 정당성은 ''T''의 Σ₁ 건전성과 Π₁ 건전성, 프로그램의 정지성은 임의의 문을 증명하거나 반증한다는 가정에 의해 보장된다.) 이는 정지 문제의 결정 불가능성에 반하므로, ''T''에서는 증명도 반증도 할 수 없는 문(즉, 결정 불가능한 문)이 존재해야 한다.

이상의 증명의 정지 문제를 재귀적이지 않은 임의의 귀납적 가산 집합으로 바꿀 수 있다. 예를 들어 정지 문제 대신 람다 계산의 정규화 가능성 문제나 술어 논리의 증명 가능성 문제를 사용할 수도 있다.

4. 3. 정지 문제의 일반화 및 변형

계산 가능성 이론 교과서에서는 정지 문제의 다양한 변형들을 다루고 있다.^[19] 일반적으로 이러한 변형 문제들은 재귀적 열거 완전(RE-complete)하며, 산술 위계에서

\Sigma^0_1

복잡성을 가지는 집합을 설명한다. 이는 표준적인 정지 문제와 동일한 수준의 복잡성을 의미한다. 따라서 이러한 변형 문제들 역시 결정 불가능하며, 표준 정지 문제는 각각의 변형 문제로 환원될 수 있고, 그 반대 방향으로의 환원도 가능하다.

하지만 모든 변형이 표준 정지 문제와 동일한 복잡성을 가지는 것은 아니다. 일부 변형들은 표준 정지 문제보다 더 높은 미해결 정도를 가지며, 이 때문에 표준 정지 문제로 환원될 수 없다. 이러한 더 복잡한 문제들의 예시는 하위 섹션에서 다룬다.

4. 3. 1. 모든 입력에 대한 정지

범용 정지 문제(universal halting problem)는 주어진 컴퓨터 프로그램이 모든 입력에 대해 정지하는지 여부를 결정하는 문제이다. 이 문제는 재귀 이론에서 '전체성(totality)'이라고도 불리는데, 이는 계산된 함수가 전체 함수인지에 대한 등가 질문에서 유래한 이름이다.

이 문제는 정지 문제와 마찬가지로 해결 불가능할 뿐만 아니라, 그보다 더 해결하기 어렵다. 산술 위계의 관점에서 보면, 이는

\Pi^0_2

-완전 문제에 해당한다. 이는 특히 정지 문제에 대한 해답을 알려주는 가상의 장치인 오라클을 사용하더라도 범용 정지 문제를 결정할 수 없다는 것을 의미한다.

4. 3. 2. 부분 해법 인식

어떤 프로그램들은 일부 입력에 대해서는 정지 문제에 대한 정답을 반환하지만, 다른 입력에 대해서는 답을 전혀 반환하지 않기도 한다. 이러한 프로그램을 부분 정지 해결사라고 부를 수 있다.

하지만 "주어진 프로그램 '''p'''가 부분 정지 해결사인가?"를 묻는 문제는 원래의 정지 문제만큼이나 어렵다. 이를 확인하기 위해, 어떤 프로그램이 부분 정지 해결사인지 판별하는 알고리즘 PHSR("부분 정지 해결사 인식기")이 존재한다고 가정해보자. 만약 PHSR이 있다면, 이를 이용해 정지 문제를 해결할 수 있다.

예를 들어, 특정 프로그램 '''x'''가 입력 '''y'''에 대해 정지하는지 알고 싶다고 하자. 이때, 입력 ('''x''', '''y''')에 대해서는 참(true)을 반환하고 다른 모든 입력에 대해서는 발산하는 새로운 프로그램 '''p'''를 만든다. 그런 다음, 이 프로그램 '''p'''를 PHSR로 검사한다. 만약 PHSR이 '''p'''를 부분 정지 해결사라고 판별한다면, 이는 '''p'''가 적어도 입력 ('''x''', '''y''')에 대해서는 정답(참)을 반환하고 정지한다는 의미이므로, 원래 프로그램 '''x'''가 입력 '''y'''에서 정지한다는 것을 알 수 있다.

이 과정은 정지 문제를 부분 정지 해결사 인식 문제로 환원하는 예시이다. 같은 방식으로, "모든 입력에 대해 정지하는가?"와 같이 정지 문제보다 더 어려운 문제들도 부분 정지 해결사 인식 문제로 환원될 수 있다. 이는 부분 정지 해결사 인식 문제가 단순히 결정 불가능할 뿐만 아니라, 산술 계층에서 더 높은 수준에 위치하며, 구체적으로는

\Pi^0_2

-완전(complete)하다는 것을 의미한다.

4. 3. 3. 손실 계산

'''손실성 튜링 기계'''는 테이프의 일부가 비결정적으로 사라질 수 있는 튜링 기계이다. 손실성 튜링 기계의 정지 문제는 결정 가능하지만 원시 귀납 함수는 아니다.

4. 3. 4. 오라클 기계

정지 문제가 튜링 기계로는 해결할 수 없다는 사실은, 처치-튜링 명제가 유효 방법을 구현하는 모든 기계의 능력에 한계가 있음을 보여준다. 하지만 인간의 상상력으로 생각할 수 있는 모든 기계가 처치-튜링 명제의 적용을 받는 것은 아니며, 오라클 기계가 그 예시 중 하나이다.

오라클 기계는 특정 튜링 기계가 주어진 입력에 대해 멈출지 여부를 판별할 수 있는 능력을 가진 가상의 계산 장치이다. 그러나 오라클 기계라 할지라도, 자기 자신과 동일한 종류의 오라클 기계가 일반적으로 멈출지 여부는 결정할 수 없다는 한계를 지닌다. 이는 정지 문제가 계층적으로 존재함을 시사한다.

4. 4. 정지 문제 근사

튜링의 증명은 알고리즘이 멈추는지 여부를 결정하는 기계적이고 일반적인 방법(즉, 튜링 기계 또는 이에 상응하는 계산 모델의 프로그램)이 존재할 수 없음을 보여준다. 그러나 정지 문제의 각 개별 사례는 결정적인 답을 가지고 있으며, 실질적으로 계산 가능할 수도 있고 그렇지 않을 수도 있다. 특정 알고리즘과 입력을 고려하면, 알고리즘이 멈추거나 멈추지 않는다는 것을 종종 보여줄 수 있으며, 실제로 컴퓨터 과학자들은 정확성 증명의 일부로 그렇게 한다. 증명 구성을 시도하기 위해 자동화된 방식으로 사용할 수 있는 일부 휴리스틱이 있으며, 이는 일반적인 프로그램에서 자주 성공한다. 이러한 연구 분야는 자동 종료 분석이라고 알려져 있다.

정지 문제 휴리스틱의 이론적 성능에 대한 몇 가지 결과가 확립되었으며, 특히 재귀적 알고리즘으로 정확하게 분류될 수 있는 주어진 크기의 프로그램 비율이다. 이러한 결과는 분수가 계산 불가능하고 "크기"를 결정하는 데 사용된 프로그램 인코딩 선택에 크게 의존하기 때문에 정확한 숫자를 제공하지 않는다. 예를 들어, 프로그램의 상태 수로 프로그램을 분류하고 프로그램이 테이프의 왼쪽으로 벗어나는 경우 (멈추지 않고) 오류가 발생하는 특정 "튜링 세미 무한 테이프" 계산 모델을 고려해 보자. 그러면

\lim_{n\to\infty} P(x\,\text{정지 여부 결정 가능} \mid x\,\text{상태 수}\,n\,\text{상태}) = 1

이며, 상태 수에 의해 균일하게 선택된 프로그램

x

에 대해 해당한다. 그러나 이 결과는 어떤 의미에서 "사소"한데, 이러한 결정 가능한 프로그램은 단순히 테이프에서 벗어나는 프로그램이고, 휴리스틱은 단순히 오류로 인해 멈추지 않는다고 예측하는 것이기 때문이다. 따라서 겉보기에는 무관해 보이는 세부 사항, 즉 오류가 있는 프로그램의 처리가 프로그램 비율을 결정하는 결정적인 요인이 될 수 있다.^[15]

이러한 문제를 피하기 위해, 프로그램 "크기"에 대한 몇 가지 제한된 개념이 개발되었다. 조밀한 괴델 넘버링은 각 계산 가능한 함수가 1에서 n까지의 각 인덱스 시퀀스에서 양의 분수를 차지하도록 프로그램을 할당한다. 즉, 괴델화 φ는 모든

i

에 대해

c > 0

이 존재하여

\liminf_{n\to\infty} \#\{j \in \N : 0 \leq j < n, \phi_i = \phi_j\}/n\geq c

이면 조밀하다. 예를 들어, 자명하지 않은 프로그램에 인덱스

2^n

을 할당하고 다른 모든 인덱스를 오류 상태로 할당하는 넘버링은 조밀하지 않지만, 구문적으로 올바른 브레인퍽 프로그램의 조밀한 괴델 넘버링이 존재한다.^[16] 조밀한 괴델 넘버링은 다른 모든 괴델 넘버링

\alpha

에 대해 1-1 전체 재귀 함수

f

와 상수

c

가 존재하여 모든

i

에 대해

\alpha_i=\phi_{f(i)}

이고

f(i) \leq c i

인 경우 최적이라고 한다. 이 조건은 모든 프로그램이 다른 괴델 넘버링에서 인덱스보다 그리 크지 않은 인덱스를 갖도록 한다. 최적의 괴델 넘버링은 범용 튜링 머신의 입력을 번호 매김으로써 구성된다.^[17] 크기의 세 번째 개념은 이진 문자열에서 작동하는 범용 머신을 사용하고 입력 프로그램을 설명하는 데 필요한 문자열의 길이를 측정한다. 범용 머신 ''U''는 모든 다른 머신 ''V''에 대해

V (x) = U (h(x))

를 만족하는 전체 계산 가능한 함수 h가 존재하는 머신이다. 최적의 머신은 콜모고로프 복잡성 불변성 경계를 달성하는 범용 머신, 즉, 모든 머신 ''V''에 대해 모든 출력 ''x''에 대해, 길이 ''n''의 ''V'' 프로그램이 ''x''를 출력하는 경우, 최대 길이

n+c

인 ''U'' 프로그램이 ''x''를 출력하도록 하는 ''c''가 존재하는 머신이다.^[18]

부분 계산 가능한 함수 (알고리즘)

A

를 고려한다. 각

n

에 대해 크기 측정값이 최대

n

인 모든 프로그램에서 오류의 비율

\epsilon_n(A)

를 고려하며,

A

가 종료되지 않거나, "알 수 없음" 답변을 생성하거나, 잘못된 답변을 생성하는 각 프로그램

x

를 계산한다. 즉,

x

가 멈추고

A(x)

가 DOES_NOT_HALT를 출력하거나,

x

가 멈추지 않고

A(x)

가 HALTS를 출력하는 경우이다. 동작은 조밀한 괴델화 및 최적의 머신에 대해 다음과 같이 설명할 수 있다.^[16]^[18]

모든 알고리즘 $A$ 에 대해 $\liminf_{n\to\infty} \epsilon_n(A) > 0$ 이다. 즉, 모든 알고리즘은 문제의 크기가 극도로 커지더라도 양의 최소 오류율을 갖는다.
모든 알고리즘 $A$ 에 대해 $\limsup_{n\to\infty} \epsilon_n(A) \geq \epsilon$ 을 만족하는 $\epsilon > 0$ 이 존재한다. 즉, 문제의 크기가 무한정 커지더라도 모든 알고리즘이 해당 오류율보다 더 나쁜 양의 오류율이 있다.
$\inf_{A} \liminf_{n\to\infty} \epsilon_n(A) = 0$ 이다. 즉, 특정 증가하는 크기 시퀀스에 대해 오류율이 0에 임의로 가까워지는 알고리즘 시퀀스가 있다. 그러나 이 결과는 잘못된 답을 생성하는 알고리즘 시퀀스를 허용한다.
정의되지 않을 수는 있지만 절대로 잘못된 답변을 생성하지 않는 "정직한" 알고리즘만 고려하는 경우, 측정 방식에 따라 $\inf_{A\,\textrm{정직}} \liminf_{n\to\infty} \epsilon_n(A)$ 가 0일 수도 있고 아닐 수도 있다. 특히 왼쪽 전체 범용 머신의 경우 0이지만 효과적으로 최적의 머신의 경우 0보다 크다.^[18]

이러한 경계의 복잡한 특성은

\epsilon_n(A)

의 진동적 거동 때문이다. 드물게 발생하는 새로운 종류의 프로그램이 임의로 큰 "블록"으로 들어오고, 반복의 비율이 끊임없이 증가한다. 새로운 종류의 블록이 완전히 포함되면 오류율은 최소

\epsilon

이지만, 블록 사이에서 올바르게 분류된 반복의 비율은 임의로 높을 수 있다. 특히 처음 N개의 입력을 기억하고 그에 상응하는 입력을 인식하는 "집계" 휴리스틱은 무한히 낮은 오류율에 도달할 수 있게 한다.^[16]

참조

_[1] 서적 Code Complete https://books.google[...] Pearson Education
_[2] 서적 The HCS12 / 9S12: An Introduction to Software and Hardware Interfacing "{{GBurl|5atwJG7D_HM[...] 2009
_[3] 서적 An Embedded Software Primer "{{GBurl|xG2ZD55_BJA[...] 1999
_[4] harvnb Minsky
_[5] harvnb Hodges
_[6] harvnb Absolutely unsolvable problems and relatively undecidable propositions – account of an anticipation
_[7] harvnb
_[8] harvnb A Note on the Entscheidungsproblem
_[9] harvnb
_[10] harvnb Informal Exposition of Proofs of Gödel's Theorem and Church's Theorem
_[11] harvnb letter from Davis to Copeland, 12 December 2001
_[12] harvtxt Textual search of Turing's collected works
_[13] 간행물 An impossible program https://academic.oup[...] 1965-01-01
_[14] 간행물 The halting problem and security's language-theoretic approach: Praise and criticism from a technical historian https://dijkstrascry[...] 2021-08-26
_[15] 간행물 The Halting Problem Is Decidable on a Set of Asymptotic Probability One https://projecteucli[...] 2022-11-05
_[16] 서적 Fundamentals of Computation Theory 2005
_[17] 간행물 Approximations to the halting problem https://core.ac.uk/d[...] 1974-10
_[18] 간행물 Generic algorithms for halting problem and optimal machines revisited 2016-04-05
_[19] harvnb
_[20] 문서 ここを「アルゴリズム」としてしまうと、[[循環論法]]になってしまって問題としておかしくなる。

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com