Halting Problem
Halting Problem (정지 문제) Halting Problem은 튜링 머신의 계산이 종료 되는가? 에 대한 결정성 문제입니다. 이때, 결정성이란, 어떤 문제에 대한 계산의 결과가 단순히 예, 아니오가 될 때, 결정성을 갖는다고 정의됩니다. Turing Machine M과 입력 스트링 w가 주어졌을 때, q0w 에서 시작한 계산이 종료되는 가에 대한 판단 문제로, 다음 예시가 있습니다. ex) 튜링 머신 M과 입력스트링 w가 주어집니다. 이때, w는 무한히 주어지고, 어느 조건에 걸렸을 때 M이 종료됩니다. 그렇다면, 종료될 때 까지 무한히 계산할 텐데 이것을 M은 무한 루프로 판단하고 정지할것인지 말 것인지의 판단 문제가 있습니다. why ? 무한 루프로 판단하고 정지했는데, 바로 다음 입력스트..
2023. 12. 27.