정지 문제

정지문제는 어떠한 프로그램이 영원히 돌아갈지 멈출지 판단하는 프로그램이 존재하는가에 대한 문제입니다

input을 받아 input프로그램이 영원히돌지 멈출지 판단하는 완벽한 프로그램 H가 있다고 가정해봅시다

귀류법을 통해 H프로그램의 모순을 발견하면 그런 프로그램은 없다는 것을 알수있습니다.

def H(a,i):
        if a(i) ->inf return false
        else true

H(a,i)의 결과는 유한시간안에 종료가되면 true를 반환 그렇지 않다면 false 반환 할것입니다.

def N(s):
    if H(s,s)==true:
        return false
    else: return true Neg프로그램은   H결과값을 부정하는 역할을 합니다.

H(N,N)의 결과값을 알 수 있는지 확인 해봅시다.

H(N,N)은 N(N)의 결과 값을 결정해야합니다.
- N(N)의 결과가 참이라고 가정 그렇지만 def N 의 정의대로 거짓을 반환합니다
+N(N)의 결과가 거짓이라고 가정 그렇지만 def N 의 정의대로 참을 반환합니다

모순이되는 사례가 있으니 귀류법에 의하여 H라는 프로그램은 존재 할수 없습니다

Share this post