앨런 튜링이 풀지 못한 문제 :: 정지 문제

Halting problem

Halting problem 이란

홀팅 문제란 어떤 프로그램과 입력을 받았을 때, 그 프로그램을 실행했을 때 유한한 단계 후에 끝날지 혹은 영원히 끝나지 않을지를 판별할 수 있는 일반적인 방법이 있을까를 다루는 문제입니다.

왜 중요할까

결론을 먼저 말하자면 홀팅 문제를 푸는 알고리즘은 없습니다.
홀팅 문제는 최초로 풀지 못하는 문제로 증명되었다는 점에서 의미가 있습니다.

증명법

증명을 위해 홀팅 문제를 풀 수 있는 알고리즘이 있다고 하나의 가정을 세우겠습니다. 해당 가정이 모순임을 밝히면 귀류법에 의해서 증명이 끝나겠죠.

• a : 사용될 임의의 프로그램
• i : 사용될 임의의 입력

exit(a, i) : Boolean = 
 if a(i) executed in finite time then true 
 else false 
// a(i)의 

exit 함수는 프로그램 a와 입력 i를 받아 a(i) 프로그램이 유한 시간에 종료되면 true를 프로그램이 영원히 돌면 false를 반환하는 함수라고 해보겠습니다. 즉 홀팅 문제를 판별하는 알고리즘입니다.

subroutine(s) : Boolean = 
 if exit(s, s) == false then true
 else infinite loop

• s : 프로그램을 입력으로 받을 수 있는 프로그램.

subroutine 함수는 s라는 프로그램을 입력으로 받습니다. 그리고 exit(s, s)을 실행해 결과가 거짓이면 참으로 프로그램을 끝내고, 참이면 무한 루프를 돕니다. 즉 exit(s, s)의 결과값을 거꾸로 내보낸다는 걸 알 수 있습니다.
프로그램을 입력으로 받는 프로그램 s가 어떤 것이 있을까 싶을 수 있습니다. 주변의 함수를 생각해보면 함수를 입력으로 받는 함수도 있지만, 컴파일러를 떠올릴 수 있습니다. 컴파일러 프로그램은 다른 프로그램을 받아 오류가 있는지 확인해주죠. s(s) 라고 한다면 자기 자신의 오류를 체크하는 컴파일러라고도 생각할 수 있습니다.

마지막 질문입니다.

• exit(subroutine, subroutine)의 값을 결정할 수 있는가.

exit함수는 subroutine이라는 프로그램과 subroutine이라는 프로그램 입력을 받아 subroutine(subroutine)이라는 프로그램을 실행했을 때 무한히 돌지를 결정할 수 있어야 합니다.

1. 참이라면, exit의 정의에 따라 subroutine(subroutine) 은 유한시간내에 끝나야 합니다. 그렇지만 subroutine의 정의에 따르면 exit(subroutine, subroutine)의 값이 참이라고 했으니 subroutine(subroutine)는 무한루프를 돌게됩니다.

2. 거짓일 경우: exit의 정의에 의해 subroutine(subroutine)이 무한 루프를 돌아야 합니다. 그런데 exit(subroutine, subroutine)이 거짓이라고 가정했으므로 subroutine의 조건문에 의해 true를 리턴하고 끝납니다.

아래 영상에서 아주 직관적으로 설명하고 있습니다.

참고 자료

https://namu.wiki/w/정지 문제