Halting problem

Halting problem

• 임의의 A라는 프로그램에 임의의 B라는 입력을 넣었을 때
  언젠가 알고리즘이 끝날 것인가 혹은 영원히 끝나지 않을 것인가?

귀류법

• 어떤 명제가 참임을 증명하려 할 때 그 명제의 결론을 부정함으로써 가정 또는 공리 등이 모순됨을 보여 간접적으로 그 결론이 성립한다는 것을 증명

EX) 고등어는 물고기다
p: 고등어는 물고기가 아니다
고등어가 물고기가 아니라면,
물고기의 특징들을 가지고 있을 수 없다
하지만 고등어는 물고기의 특징들을 다 가지고 있다
~p: 고등어는 물고기다.

정지 문제를 판별하는 알고리즘:halting(A,B)

function check (A) {
 if (halting(A,A) == false)
   return true;
 else
   infinite loop;
   
   check(check); //성곡적으로 계산을 마쳤다고 가정

• halting(A,B)은 A라는 프로그램에 B라는 입력을 넣었을 때 정상적으로 알고리즘이 마친다면 true, 그렇지 않다면 false
• A는 임의의 프로그램, B는 임의의 입력
  • 프로그램이 0,1의 반복 문자열로 있을 수 있기에 프로그램 자체를 다른 프로그램 인자로 넣을 수 있다
• check라는 더 큰 함수가 halting이라는 함수를 내부적으로 포함
• 입력으로써 A라는 프로그램을 받았다

check(check)가 성공적으로 끝냈다 가정

• halting(check,check) == false가 되야함
• halting()의 인자값으로 check라는 프로그램에 check를 넣은 값이 false이므로
  • check라는 프로그램에 어떠한 입력 값을 넣었을 때 false가 되어야하므로 무한루프에 빠진다는 얘기다

check(check) 무한루프에 빠졌다 가정

• halting(check,check) == true라는 의미
• halting()의 인자값으로 check라는 프로그램에 check를 넣은 값이 true이므로
  • check라는 프로그램에 어떠한 입력 값인 check 넣었을 때 유한한 시간안에 종류 되어야 한다

void loop(int x)
{
  if (x==1)
    return;
  else
    while (true);
}
//loop(1) 멈출 수 있음
//loop(0) 멈출 수 없음

int halt(func, cond){
  if (func terminates with cond)
    return 1;  //멈출 수 있음
  else
    return 0;  //멈출 수 없음
}

void verify(func) {
  if (halt(func, func))
    loop(0);  //멈출 수 없는 함수를 호출
  else
    loop(1);  //멈출 수 있는 함수를 호출
 }
 
 verify(verify); //멈출 것이냐, 멈추지 않을 것이냐