튜링완전과 정지문제

튜링이라는 기계는 수학자 앨런 튜링이 설계한 기계로, 

특정 알고리즘을 통해 덧셈 뺄셈과 같은 간단한 계산부터 여러가지 동작을 할 수 있다.

 

여기서 튜링완전이라는 단어가 나오는데 튜링 머신으로 할 수 있는 것들을, 할 수 있다면 튜링완전하다고 한다.

컴퓨터도 튜링 기계이며 또한 튜링 완전한 기계가 할 수 있는 일은 다른 튜링 완전한 기계가 할 수 있다.

따라서 지금의 컴퓨터가 할 수 있는 일은 고전의 튜링기계가 할 수 있다. 다만 시간이 오래 걸린다.

이러한 기계는 튜링이 힐베르트의 결정문제를 해결하기 위해서 고안해낸 것이다.(만든 것은 아님)

 

 

 

앨런 튜링은 힐베르트의 결정문제를 튜링기계를 이용한 정지문제를 통하여 증명해냈다.

힐베르트의 결정문제와 정지문제는 다음과 같다.

 

힐베르트의 결정문제

'모든 수학적 문제에 대해서 참인지 거짓인지를 확실하게 결정해줄 수 있는 명확한 방법이 존재하는 가를 증명하시요'

 

엘런 튜링 정지문제

'프로그램에 처음 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라.'

 

 

 

참 거짓을 계산 가능 불가능으로 치환해서 해결한 셈인데,

결론 부터 말하자면 '판정할 수 없다'는게 결론이다.

 

그 방식은 위와 같다.

 

1. 튜링완전한 A라는 기계가 있고 이 기계는 계산 가능 여부를 알려준다고 가정한다, 또한 N이라는 기계가 A기계와 연결되어있다. 이를 AN머신이라고 부르자.
2. A는 어떤 문제를 넣었을 때 계산에 성공해서 끝난다면 1을 계산을 하지못해서 계산이 끝나지 않는다면 동작을 멈추고, N은 A가 1을 출력하면 동작을 멈추고 0을 출력하면 1을 출력한다.
3. 따라서 AN머신은 어떤 문제를 넣었을 때 A가 계산 가능하다면 동작을 멈추고, 계산 불가하다면 1을 출력한다.
4. 'AN머신이 멈출까요?'라는 문제를 AN머신에 넣었을 때, A머신은 AN머신이 멈춘다고 판단하면 0을, 그렇지 않다면 1을 출력한다.
5. 하지만 A머신이 0을 출력하면 AN머신은 멈추지 않고 1을 출력하고, A머신이 1을 출력하면 AN머신은 동작을 멈춘다.
6. 따라서 A머신이 계산 가능 여부를 알려준다는 가정은 틀리게 되고 A머신은 계산 가능 여부를 알려줄 수 없는 기계가 된다.

따라서 계산 가능 여부를 알려줄 수 있는 머신은 존재하지 않는다는 것이 결론이다.

---

1. 튜링머신과 정지문제를 쉽게 설명한 영상

튜링머신 1탄

튜링머신 2탄

 

튜링머신 3탄

 

튜링머신 4탄

 

튜링머신 5탄

2. 튜링머신을 이해하기 좋은 글

 

Neural Turing Machine