Halting Problem

Halting Problem (정지 문제)

Halting Problem은 튜링 머신의 계산이 종료 되는가? 에 대한 결정성 문제입니다.

 

이때, 결정성이란, 어떤 문제에 대한 계산의 결과가 단순히 예, 아니오가 될 때, 결정성을 갖는다고 정의됩니다.

 

Turing Machine M과 입력 스트링 w가 주어졌을 때, q0w 에서 시작한 계산이 종료되는 가에 대한 판단 문제로, 다음 예시가 있습니다.

 

ex) 튜링 머신 M과 입력스트링 w가 주어집니다. 이때, w는 무한히 주어지고, 어느 조건에 걸렸을 때 M이 종료됩니다. 그렇다면, 종료될 때 까지 무한히 계산할 텐데 이것을 M은 무한 루프로 판단하고 정지할것인지 말 것인지의 판단 문제가 있습니다. why ? 무한 루프로 판단하고 정지했는데, 바로 다음 입력스트링이 최종 상태로 향하는 스트링일지 알 수 없기 때문

 

그렇다면, 이러한 정지 문제를 계산할 수 있는 튜링 머신의 존재 여부를 확인해야합니다.

한 튜링머신 M과 M에 주어진 입력스트링 w, M을 코딩한 스트링 wM이 있을 때,

q0 wM w ├* x1 qy x2 (M이 w를 처리한 후 종료되는 경우)

q0 wM w ├* y1 qn y2 (M이 w를 처리한 후 종료되지 않는 경우)

 

이 순간 묘사를 만족하는 또 다른 튜링머신 H가 존재하는가 입니다. (qy와 qn은 모두 H의 F)

 

하지만 튜링머신 H는 존재하지 않는다고 1936년 Alan Turing에 의해 밝혀졌습니다.

 

따라서, 정지문제는 비결정적이고, NP(Non-deterministic polynomial time, 비결정적 다항 시간)에 속하지 않는 판단 문제 중 하나로 증명됐습니다.