컴퓨터가 모든 것을 할 수 없다는 증거(중단뮨제)
해당 영상은 1936년 튜링이 증명한 컴퓨터 과학에서 매우 영향력 있는 결과인 정지문제(Halting Problem)을 보여줍니다.
이야기는 계산문제를 잘 하는 장치 A와 체커게임을 잘 하는 장치 C로부터 시작됩니다.
그리고 이제 계산문제를 체커장치 C에 집어넣어주고, 체커게임을 계산장치 A에 집어넣어줍니다.
그러니까 둘 다 멈춰버립니다!!
이 멈춰버리는 문제를 예방(?)하기 위해 H라는 기계가 어떤 기계의 청사진과, 그 기계에 입력할 내용을 넣어주면 어떤 입력이 적절하고 어떤 입력을 받으면 멈춰 버릴지를 결정합니다.
컴퓨터가 모든 것을 해낼 수 없다는 것을 증명하기 위해, 우리는 H가 존재할 수 없다는 증명을 합니다.(정지 정리)
그 증명을 하기위해, X라는 기계를 만듭니다.
{X의 맨 위에는 하나의 입력과 두 개의 출력을 가지는 P라는 기계를 배치해 둡니다. P는 입력받은 내용 하나를 복사해서 두 개로 출력해줍니다.
X 내부의 P 아래에는 아까 그 장치 H를 둡니다.
X 내부의 P와 H의 아래에는 Stuck이 입력되면 :-)을 출력하고 Not Stuck이 입력되면 멈춰버리는 N이라는 장치를 둡니다
}
이제 X에 본인 자신의 청사진을 집어넣어봅니다.P는 H에게 입력받은 청사진의 복사본 2개를 전달해줍니다. 이제 두 가지 가정을 해볼 수 있습니다.
i)H가 멈추지 않는다고 결과를 도출하는 경우
H가 멈추지 않는다는 출력물을 N에게 입력해주었으므로 N은 멈춰버립니다.
=>X에 자신의 청사진을 넣으면 멈춰버리는 결론 도출됩니다
따라서, H는 멈추지 않는다!를 출력했으나 멈춰버렸으니 H는 틀린 답을 도출한 것이 됩니다.
그렇다면
ii)H가 멈춘다고 결과를 내는 경우
N은 :-)을 출력합니다. 그렇게 되면 장치 X는 동작한 것이 되고, 또 H가 틀린 것이 됩니다.
하지만 모든 것을 할 수 있는 컴퓨터, H는 언제나 옳은 답을 출력해야합니다.
하지만 H는 위에서 보았듯이 틀린 답을 출력했으므로, 우리는 컴퓨터가 모든 것을 할 수 없다는 것을 증명할 수 있습니다.
사실 저는 교수님이 완벽한 컴퓨터는 없다!라고 말씀하실 때마다 막연히 그렇겠지!라고만 생각해왔었는데, 이렇게 애니매이션 영상으로 표현된 증명을 보고나니 확실히 "어떤 시스템이 자기 자신에 대한 정지 문제를 풀 수 있다면 그 시스템은 튜링 머신을 Simulate할 능력이 없가"라는 말이 맞다-라는 생각이 들었습니다.
나무위키에서 발견한 추가 내용으로는,
정지 문제는 판정 문제의 한 갈래로, "주어진 프로그램이 해결하고자 하는 문제를 해결하는지 말해줄 수 있는 일반화된 알고리즘이 존재하는가?" 라는 질문이라는 것입니다.
1936년 앨런 튜링은 이것을 해결할 수 있는 일반화된 방법은 없다라는 결론을 내렸으며, 이는 논리학적으로 undecidable이 증명된 최초의 문제입니다.
정지 문제를 포함한 어떠한 문제라도 단 한번의 동작으로 풀 수 있는 가상의 장치인 Oracle장치를 튜링 머신에 달아놓은 Oracle Machine이라는 가상의 시스템을 가정할 경우에도 이 기계는 자기 자신의 정지 문제를 풀 수가 없습니다.
아래의 귀류법을 통한 증명에서 따라나오는 결론은 "어떤 시스템이 자기 자신에 대한 정지문제를 풀 수 있다면 그 시스템은튜링 머신을 Simulate할 능력이 없다는 것입니다.
컴퓨터가 모든 것을 할 수 없다는 증거(중단뮨제)
해당 영상은 1936년 튜링이 증명한 컴퓨터 과학에서 매우 영향력 있는 결과인 정지문제(Halting Problem)을 보여줍니다.
이야기는 계산문제를 잘 하는 장치 A와 체커게임을 잘 하는 장치 C로부터 시작됩니다.
그리고 이제 계산문제를 체커장치 C에 집어넣어주고, 체커게임을 계산장치 A에 집어넣어줍니다.
그러니까 둘 다 멈춰버립니다!!
이 멈춰버리는 문제를 예방(?)하기 위해 H라는 기계가 어떤 기계의 청사진과, 그 기계에 입력할 내용을 넣어주면 어떤 입력이 적절하고 어떤 입력을 받으면 멈춰 버릴지를 결정합니다.
컴퓨터가 모든 것을 해낼 수 없다는 것을 증명하기 위해, 우리는 H가 존재할 수 없다는 증명을 합니다.(정지 정리)
그 증명을 하기위해, X라는 기계를 만듭니다.
{X의 맨 위에는 하나의 입력과 두 개의 출력을 가지는 P라는 기계를 배치해 둡니다. P는 입력받은 내용 하나를 복사해서 두 개로 출력해줍니다.
X 내부의 P 아래에는 아까 그 장치 H를 둡니다.
X 내부의 P와 H의 아래에는 Stuck이 입력되면 :-)을 출력하고 Not Stuck이 입력되면 멈춰버리는 N이라는 장치를 둡니다
}
이제 X에 본인 자신의 청사진을 집어넣어봅니다.P는 H에게 입력받은 청사진의 복사본 2개를 전달해줍니다. 이제 두 가지 가정을 해볼 수 있습니다.
i)H가 멈추지 않는다고 결과를 도출하는 경우
H가 멈추지 않는다는 출력물을 N에게 입력해주었으므로 N은 멈춰버립니다.
=>X에 자신의 청사진을 넣으면 멈춰버리는 결론 도출됩니다
따라서, H는 멈추지 않는다!를 출력했으나 멈춰버렸으니 H는 틀린 답을 도출한 것이 됩니다.
그렇다면
ii)H가 멈춘다고 결과를 내는 경우
N은 :-)을 출력합니다. 그렇게 되면 장치 X는 동작한 것이 되고, 또 H가 틀린 것이 됩니다.
하지만 모든 것을 할 수 있는 컴퓨터, H는 언제나 옳은 답을 출력해야합니다.
하지만 H는 위에서 보았듯이 틀린 답을 출력했으므로, 우리는 컴퓨터가 모든 것을 할 수 없다는 것을 증명할 수 있습니다.
사실 저는 교수님이 완벽한 컴퓨터는 없다!라고 말씀하실 때마다 막연히 그렇겠지!라고만 생각해왔었는데, 이렇게 애니매이션 영상으로 표현된 증명을 보고나니 확실히 "어떤 시스템이 자기 자신에 대한 정지 문제를 풀 수 있다면 그 시스템은 튜링 머신을 Simulate할 능력이 없가"라는 말이 맞다-라는 생각이 들었습니다.
나무위키에서 발견한 추가 내용으로는,
정지 문제는 판정 문제의 한 갈래로, "주어진 프로그램이 해결하고자 하는 문제를 해결하는지 말해줄 수 있는 일반화된 알고리즘이 존재하는가?" 라는 질문이라는 것입니다.
1936년 앨런 튜링은 이것을 해결할 수 있는 일반화된 방법은 없다라는 결론을 내렸으며, 이는 논리학적으로 undecidable이 증명된 최초의 문제입니다.
정지 문제를 포함한 어떠한 문제라도 단 한번의 동작으로 풀 수 있는 가상의 장치인 Oracle장치를 튜링 머신에 달아놓은 Oracle Machine이라는 가상의 시스템을 가정할 경우에도 이 기계는 자기 자신의 정지 문제를 풀 수가 없습니다.
아래의 귀류법을 통한 증명에서 따라나오는 결론은 "어떤 시스템이 자기 자신에 대한 정지문제를 풀 수 있다면 그 시스템은튜링 머신을 Simulate할 능력이 없다는 것입니다.