<div id="readability-page-1" class="page"><div>
 
 <article>
 <ul id="markdown-toc">
 <li><a href="#문제의-의의" id="markdown-toc-문제의-의의">문제의 의의</a></li>
 <li><a href="#문제-개요" id="markdown-toc-문제-개요">문제 개요</a></li>
 <li><a href="#증명" id="markdown-toc-증명">증명</a> <ul>
 <li><a href="#귀류법을-통한-증명" id="markdown-toc-귀류법을-통한-증명">귀류법을 통한 증명</a> <ul>
 <li><a href="#h를-만드는-것이-가능하다고-가정하자" id="markdown-toc-h를-만드는-것이-가능하다고-가정하자">H를 만드는 것이 가능하다고 가정하자</a></li>
 <li><a href="#h가-잘못된-결과를-리턴하는-경우를-찾아낸다" id="markdown-toc-h가-잘못된-결과를-리턴하는-경우를-찾아낸다">H가 잘못된 결과를 리턴하는 경우를 찾아낸다</a></li>
 </ul>
 </li>
 </ul>
 </li>
 <li><a href="#참고문헌-및-links" id="markdown-toc-참고문헌-및-links">참고문헌 및 Links</a></li>
</ul>

어떤 프로그램이 어떤 입력값을 받았을 때 유한한 단계의 절차를 마치고 멈추는지, 아니면 무한 루프하는지 판정하는 알고리즘이 존재하는가?

<h2 id="문제의-의의">문제의 의의</h2>

세상엔 컴퓨터로 풀기 쉬운 문제가 있고, 풀기 어려운 문제가 있다.

그런데 세상엔 컴퓨터로 풀 수 없는 문제도 있다.

정지 문제는 컴퓨터로 풀 수 없는 문제들 중 하나이다.

<ul>
 <li>"해결 불가능한(unsolvable)" 문제
 <ul>
 <li>풀 수 있는 알고리즘이 없는 문제.</li>
 <li>해결 불가능한 문제가 존재한다는 역사상 첫 번째 증명은, 앨런 튜링의 "정지 문제" 이다.</li>
 </ul>
 </li>
</ul>

<h2 id="문제-개요">문제 개요</h2>

모든 프로그램은 입력값을 넣고 실행하면 다음 둘 중 하나와 같이 된다.

<ol>
 <li>유한한 절차를 거친 다음, 리턴값을 내놓는다.</li>
 <li>무한 루프에 빠진다.</li>
</ol>

그런데 프로그램을 실행하기 전에 먼저 소스 코드를 검토해서, 무한루프할지 알아낼 수 있다면 유용하지 않을까?

그런 무한 루프를 검토하는 프로그램을 H라 하자.

프로그램 H는 모든 입력에 대해 정확한 결과를 리턴한다.

"H 를 만드는 것이 가능한가?"

<h2 id="증명">증명</h2>

H를 만드는 것은 불가능하다.

<h3 id="귀류법을-통한-증명">귀류법을 통한 증명</h3>

이는 귀류법을 통해 증명할 수 있다.

<ol>
 <li>H를 만드는 것이 가능하다고 가정한다.</li>
 <li>H가 잘못된 결과를 리턴하는 경우를 찾아낸다.</li>
 <li>전제에 모순되므로, H를 만드는 것은 가능하지 않다.</li>
</ol>

<h4 id="h를-만드는-것이-가능하다고-가정하자">H를 만드는 것이 가능하다고 가정하자</h4>

<ul>
 <li>H를 구현하는 함수 <code>H(P, I)</code> 가 있다고 가정하자.
 <ul>
 <li><code>P</code> 는 검사할 프로그램의 소스 코드이다.</li>
 <li><code>I</code> 는 <code>P</code> 에 입력할 입력값이다.</li>
 </ul>
 </li>
</ul>

H를 구현하는 <code>H(P, I)</code> 는 <code>P(I)</code> 가 무한 루프하는지 아닌지를 검사하는 프로그램이라 할 수 있다.

<ul>
 <li><code>P(I)</code>가 유한한 단계 내에 리턴값을 내놓는다면 <code>true</code>를 리턴한다.</li>
 <li><code>P(I)</code>가 무한루프한다면 <code>false</code>를 리턴한다.</li>
</ul>

이해를 돕기 위해 예를 들어 보자.

만약 다음의 python 함수를 <code>H(P, I)</code>에 집어넣는다면 어떻게 될까?

<div><pre><code>def test(I):
 while I &gt; 0:
 print("hello")
 return 42
</code></pre></div>

<ul>
 <li><code>test(3)</code> 은 <code>while</code>을 빠져나가지 못하고 무한히 hello를 출력할 것이다.
 <ul>
 <li>따라서 <code>H(test, 3)</code> 은 <code>false</code>를 리턴한다.</li>
 </ul>
 </li>
 <li><code>test(-1)</code> 은 <code>42</code>를 리턴할 것이다.
 <ul>
 <li>따라서 <code>H(test, -1)</code> 은 <code>true</code>를 리턴한다.</li>
 </ul>
 </li>
</ul>

H를 구현한 <code>H(P, I)</code>는 <code>test(3)</code>과, <code>test(-1)</code> 에 대해서는 잘 작동한다.

<h4 id="h가-잘못된-결과를-리턴하는-경우를-찾아낸다">H가 잘못된 결과를 리턴하는 경우를 찾아낸다</h4>

하지만 <code>H(P, I)</code> 가 판정에 실패하는 함수를 만들 수 있다면 어떨까?

다음 함수를 보자. 이 함수는 <code>H(P, I)</code>의 헛점을 드러내기 위해 악의적으로 만든 것이다.

<div><pre><code>def foo(x):
 if H(x, x):
 while true:
 print("hello")
 else:
 return 42
</code></pre></div>

이제 이 <code>foo</code> 함수의 입력값으로 <code>foo</code>를 넣어서… <code>foo(foo)</code>와 같이 호출한다고 하자.

그렇다면 <code>H(P, I)</code> 에 <code>H(foo, foo)</code>와 같이 입력할 수 있을 것이다.

<code>H(foo, foo)</code> 는 어떤 결과를 리턴할까?

아마도 둘 중 하나일 것이다.

<ul>
 <li><code>H(foo, foo)</code> 가 <code>true</code>를 리턴하는 경우.
 <ul>
 <li>즉, <code>foo(foo)</code>는 무한루프하지 않고 <code>42</code>를 리턴할 것이다.</li>
 <li>그런데 과연 그럴까? <code>foo(foo)</code>를 실행한다고 생각하며 소스코드를 들여다보자.</li>
 <li><code>H(foo, foo)</code> 가 <code>true</code> 이므로, <code>foo(x)</code> 의 안쪽에서 <code>while true</code> 로 진입한다.</li>
 <li>결과적으로 <code>H(foo, foo)</code> 가 <code>true</code> 를 리턴하기 때문에 <code>foo(foo)</code> 는 무한히 루프한다.</li>
 <li>즉, <code>H(foo, foo)</code> 는 <code>false</code>를 리턴해야 맞다.
</li>
 </ul>
 </li>
 <li><code>H(foo, foo)</code> 가 <code>false</code>를 리턴하는 경우.
 <ul>
 <li>즉, <code>foo(foo)</code>는 무한루프할 것이다.</li>
 <li>그런데 과연 그럴까? <code>foo(foo)</code>를 실행한다고 생각하며 소스코드를 들여다보자.</li>
 <li><code>H(foo, foo)</code> 가 <code>false</code> 이므로, <code>foo(foo)</code>는 <code>42</code>를 리턴하고 정지한다.</li>
 <li>결과적으로 <code>H(foo, foo)</code> 가 <code>false</code> 를 리턴하기 때문에 <code>foo(foo)</code> 는 무한히 루프하지 않는다.</li>
 <li>즉, <code>H(foo, foo)</code> 는 <code>true</code>를 리턴해야 맞다.</li>
 </ul>
 </li>
</ul>

따라서 H를 구현한 <code>H(P, I)</code> 가 정확히 판별할 수 없는 함수가 적어도 하나 존재한다.

이는 전제에 모순된다.

따라서 H를 만드는 것은 불가능하다.

<h2 id="참고문헌-및-links">참고문헌 및 Links</h2>

<ul>
 <li>Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일</li>
 <li>컴퓨터과학이 여는 세계 / 이광근 저 / 인사이트(insight) / 2017년 02월 28일</li>
 <li><a href="http://www.aistudy.co.kr/computer/halting_problem.htm">Halting problem (AI study)</a></li>
</ul>


 </article>


 
 
 



</div></div>

정지 문제

댓글