튜링 머신, Halting problem

Halting  problem

 

유한한 수의 단계 후에 특정한 프로그램이 멈출 것이라고 (문제가 풀릴것이라고) 우리에게 미리 말해줄 수 있는 어떤 일반적인 절차 (알고리듬) 가 있는가?

 

달리 말하면, 어떤 주어진 튜링기계 (Turing Machine) 프로그램 P 와 입력 자료들의 집합 I 에 대해서, P 와 I 를 받아들인 다음에 자료 I 를 처리할 때 P 가 유한한 수의 단계 후에 멈출 것인지의 여부를 우리에게 말해줄 수 있는 어떤 단일한 프로그램이 있는가? 이때 우리가 문제삼는 것이 모든 경우에 작동할 어떤 단일한 프로그램이라는 것을 주목하라. 바로 이것이 그 유명한 멈춤문제 (Halting Problem) 다.

 

...... 실제 프로그램에 대한 멈춤 규칙은 대개 "만일 이런저건 조건을 만족하는 그러그러한 값이 나오면 멈춰라. 그렇지 않으면 계속해서 계산하라" 와 같이 말하는, 앞에서 제시된 것과 종류가 같은 암묵적인 규칙이다. 멈춤문제에서 핵심적인 것은 프로그램의 멈춤 조건이 만족될 것이냐의 여부를 미리 말해주기 위해 그 프로그램과 입력자료들에 적용될 수 있는 어떤 효과적인 절차가 존재하느냐 하는 물음이다.

 1936 년에 Alan Turing 은 이 문제를 일거에 부정적으로 해결했다. 즉 주어진 프로그램 P 와 입력자료 집합 I 에 대해서, P 가 입력 I 를 처리하는 것을 끝낼지의 여부를 말해주는 어떤 일반적인 방법도 없다는 것이다.

 

튜링 기계라는 개념은 결국 계산이라는 생각을 견고한 수학적 토대 위에 올려놓았으며, 우리로 하여금 효과적 (effective) 절차라는 모호하고 직관적인 생각에서, 알고리듬이라는 정확하고 수학적으로 잘 정의된 개념으로 나아가게 했다 ..... (John Casti 2000)

 

정지문제는 비공식적으로 다음과 같이 묘사할 수 있는 판정문제 (Entscheidungsproblem) 이다.

"하나의 알고리즘과 초기 인수들이 주어졌을 때, 주어진 인수로서 수행되는 알고리즘 (Algorithm) 이 정지되는지, 정지하지 않고 영원히 수행되는지를 결정한다"

Alan Turing 은 1936 년에 모든 가능한 입력에 대해 정지문제를 해결할 수 있는 일반적인 방법이나 알고리즘은 없다는 것을 증명했다. 정지문제가 중요한 이유는 그것이 결정불가능성 (undecidable)을 증명하는 최초의 문제였다는 사실이다. 계속해서 많은 다른 문제들이 다루어졌으며, 결정불가능성인 문제를 증명하는 전형적인 방법은 그것을 정지문제로 축소시키는 것이다.

 

정지문제의 결정불가능성에 대한 결과는 판정문제 (Entscheidungsproblem) 가 해결될 수 없으며, 특히 자연수에 대한 어떤 문장이 참인지 거짓인지를 결정하는 일반적인 알고리즘은 있을 수 없다는 것이다. 그 이유는 어떤 알고리즘이 어떤 입력이 주어졌을 때 멈출 것이라고 진술하는 명제는 수에 관한 문장으로 자동적으로 다시 공식화할 수 있다는 것 때문이다. 즉 알고리즘에 관한 원래의 문장이 참인지 거짓인지 결정할 수 있는 알고리즘은 없기 때문에, 수에 관한 동등한 문장이 참인지 거짓인지 결정할 수 있는 알고리즘은 없다는 것이다.

 

그러나 정지문제의 결정불가능성에 관한 아주 놀라운 또다른 결과는, 알고리즘으로 정의되는 함수에 대한 어떤 중요한 (non-trivial) 문장의 진리여부는 결정될 수 없다는 Rice's theorem 이다. 예를들면, "이 알고리즘은 0 이 입력되면 멈출 것이다" 라는 결정문제는 이미 결정불가능하다. 이 정리는 알고리즘 그 자체가 아니라 알고리즘에 의해 정의된 함수를 가지고 있다는 것을 주목하라. 예를들면 어떤 알고리즘이 100 step 이내에 멈출 것인지를 결정하는 것은 가능하지만, 그러나 이것은 알고리즘에 의해 정의된 함수에 대한 문장이 아니다. ......

 

Gregory Chaitin 는 정지문제에 의존하지 않는 algorithmic information theory 에 관한 결정불가능 문제를 제시했다. 그는 임의로 만들어진 프로그램이 정지할 확률을 표현하는 halting probability 의 흥미로운 정의를 제시했다.

 

튜링의 정리가 알고리즘이 멈추는 지를 결정할 일반적인 방법이나 알고리즘이 있을 수 없다는 것을 보여주는 반면에, 개별 프로그램의 경우에는 공격에 매우 민감할 수 있다 (individual instances of that problem may very well be susceptible to attack). 특별한 알고리즘이 주어졌을 때, 어떤 입력일 경우에 그것이 멈춰야하는 지를 보일 수 있다. 그러나 사실 컴퓨터과학자는 하나의 correctness proof 의 부분으로서만 그것을 수행한다. 그러나 모든 그런 증명은, "알고리즘이 멈추는 지를 결정하는 mechanical, general way 가 없다" 는 새로운 추론을 요구한다.

 

또다른 경고가 있다. 정지문제의 결정불가능성은 알고리즘이 아마도 무한의 저장장치를 가진다고 가정한다는 사실이다. 어느 한순간에는 유한한 것들을 저장할 수 있지만, 그것은 항상 더 많은 것을 저장하고 결코 메모리를 초과하지 않는다. 만일 기계의 메모리와 외부 저장장치가 유한하다면, 그것은 실제로 존재하는 컴퓨터에 대한 것이고, 따라서 기계상에서 작동하는 프로그램에 대한 정지문제는 일반 알고리즘으로 해결될 수 있다 (비록 극히 비효율적인 것이지만). .............. (Wikipedia : Halting problem)

 

 

 

 

term :

튜링기계 (Turing Machine)   튜링 테스트 (Turing Test)   튜링 명제 (Turing Thesis)   계산가능성 이론 (Computability Theory)   계산 (Computation)   계산복잡도이론 (Computational Complexity Theory)   판정문제 (Entscheidungsproblem)   알고리즘 (Algorithm)

 

 

paper :

멈춤문제 (halting problem) : John Casti. Werner De Pauli

 

 

출처 : http://www.aistudy.co.kr/computer/halting_problem.htm