🚀궤도사령부(궤도)

궤도님 책 읽고 있는데 결정 가능성 문제에 대해 이해하기 쉽게 설명해주실뿐

질문

조지포지

23.02.05

일단 제가 이해한거로는 책 내용대로 “명제가 참인지 거짓인지 판별하는 방법은 존재할 수 없다.”를 가정하여 예시를 들자면

"소수는 무한한가? or 유한한가?" “자유의지는 존재하나? or 존재하지 않나?” 와 같은 어려운 명제들을 우리는 거짓인지 참인지 무조건 판별할 수 있는 능력은 존재하지 않는다. 로 이해를 했는데

맞나요? 설령 이게 맞다 한들 더 정확하고 깊게 이해할 수 있을 것 같은데 모르겠습니다 하하 특히 튜링기계 관련해서 설명할때 이해가 잘 안되네요

정수론민수

23.02.05

궤도님의 책을 읽어봐진 못해서 어떤 뉘앙스에서 하신 말씀인진 모르겠지만, 제 생각에 임의의 명제의 참/거짓 여부를 판별하는 방법은 존재하지 않는다는 뜻인 것 같습니다. 소수의 무한성같은 경우는 그 여부를 판별할 수 있지요. 증명을 통해서 말입니다. 하지만 그 증명은 소수의 무한성의 참/여부만을 알려줄 수 있지, 자유의지의 존재여부를 판단하는데는 사용할 수 없습니다. 하나의 명제의 참/거짓 여부는 수학이라면 증명을, 과학이라면 실험을, 다른 분야라면 다른 분야의 맞는 방법론을 통해서 보일 수 있지만, 일반적으로 어떤 명제가 참인지 거짓인지 알아내는 알고리즘은 없다는 뜻인 것 같습니다.

궤소리방정식

23.02.05

결정 가능성 문제가 나오게 된 배경을 알면 이해하는데 도움이 될 것 같습니다. 20세기 초반에 힐베르트라는 수학자를 중심으로 수학을 더욱 더 엄밀히 하기 위한 노력이 있었는데요, 말씀하신 결정 가능성 문제는 1928년 힐베르트가 제시한 문제입니다. 인터넷에 Entscheidungsproblem이라 치면 자료가 많이 나올 겁니다. 제가 알고있는 결정 가능성 문제는 "임의의 수학적 명제의 참/거짓 여부를 판별하는 유한한 방법이 있는가?" 인데요, 여기서의 "유한한 방법"이라는 말은 알고리즘으로 이해하시면 됩니다. 근데 힐베르트가 살고 있었을때에는 알고리즘이라는 개념이 수학적으로 정의가 되지 않았습니다.

궤소리방정식

23.02.05

괴델, 처치 등 수많은 많은 수학자들이 알고리즘을 엄밀히 정의하려 노력했지만 오늘날 컴퓨터공학에서 쓰이는 알고리즘의 정의를 내린건 앨런 튜링입니다. 1936년, 고작 22세의 나이에 말입니다. 이 논문에서 튜링은 튜링 기계라는, 유한한 상태와 무한한 저장공간에 정해진 규칙에 따라 기호를 썼다 지웠다 하는 기계를 정의합니다. 이 튜링기계에 어떠한 입력값을 주면 이 기계는 정해진 규칙에 따라 테이프에 기호를 썼다가 지웠다가 하며 상태가 바뀝니다. 수락 상태에 도달할 수도 있고, 거절 상태에 도달할수도 있고, 이 둘에 도달하지 못한 채 무한루프에 빠질 수도 있습니다. 이제 어떤 명제가 결정 가능하다는 뜻은 그 명제를 참으로 하는 입력값을 주었을때 수락 상태에 반드시 도달하고, 그 명제를 거짓으로 하는 입력값으로 주었을때 거절 상태에 반드시 도달하는 튜링기계가 존재한다는걸 말합니다. 예를 들어 주어진 수가 소수인지 판별하는 튜링기계가 있다고 해봅시다. 3을 입력값으로 주면 수락 상태에 도달하고, 10을 넣으면 거절 상태에 도달하게 됩니다. 이 “주어진 수가 소수인지 판별하는 문제”는 결정 가능합니다. 무한루프에 빠지지 않는 튜링기계가 존재하니까요.

이제 알고리즘을 정의했으니 다시 결정 가능성 문제로 가봅시다. 아까는 "임의의 수학적 명제의 참/거짓 여부를 판별하는 유한한 방법이 있는가?" 였죠? 이제 튜링기계가 나왔으니 "임의의 수학적 명제의 참/거짓 여부를 판별하는 결정 가능한 튜링기계가 있는가?" 가 됩니다. 그리고 앨런 튜링은 아까 말한 1936년 논문에서 이 문제에 대답합니다. 없다 라고요. 그 어떤 결정 가능한 튜링기계를 만들어도 임의의 수학적 명제를 판단할 수는 없더라 라는게 튜링이 증명한 내용입니다. 어떻게 보면 컴퓨터공학이라는 분야는 자기 자신의 한계를 알고 태어났다고 볼 수 있겠네요.

얘기가 길어졌는데요, 말씀하신 “자유의지는 존재하나?” 등의 명제는 아직 수학적으로 정의하지 못합니다. 튜링기계가 있는지 없는지도 모르지요. 또 수학적으로 정의할 수 있는지도 모릅니다. “소수는 무한한가?” 등의 명제는 수학적으로 정의할 수 있지만요.

결정가능성 문제를 이해하는데 도움이 됬길 바랍니다. 마침 이번주에 배운 내용이라 아주 반갑네요 ㅎㅎ

궤소리방정식

23.02.05

결정 가능성에 대해 좀 더 간단히 비유를 들어보겠습니다. 여기 작은 꼬마 요정이 있다고 해봅시다. 이 꼬마 요정은 소수가 뭔지 모릅니다. 유한하다는것도 뭔지 모르고요. 자유의지도 뭔지 잘 모릅니다. 하지만 이 꼬마 요정이 굉장히 잘하는것이 있는데요, 무한한 테이프에 0과 1을 쓰는 것입니다. 하지만 꼬마이다 보니 한번에 숫자 하나밖에 못 봅니다. 또 모자를 쓰는것도 좋아해서 집 안에 다양한 모자가 있습니다. 이제 이 요정에게 0과 1을 어떻게 쓸지에 관한 책을 줍니다. 책의 표지에는 이렇게 적혀 있습니다. "주어진 수가 소수인지 판별하기. 시작하려면 빨간 모자를 쓰시오." 책의 안에는 이렇게 적혀 있습니다.

만약 빨간 모자를 쓰고 있고 현재 0을 보고 있다면, 0을 1로 바꾸고 오른쪽으로 한칸 이동하시오. 그 후 노란 모자를 쓰시오.

만약 빨간 모자를 쓰고 있고 현재 1을 보고 있다면, 1을 그대로 두고 왼쪽으로 한칸 이동하시오. 그 후 파란 모자를 쓰시오.

만약 빨간 모자를 쓰고 있고 현재 빈칸을 보고 있다면, 빈칸을 0으로 바꾸고 오른쪽으로 한칸 이동하시오. 빨간 모자를 그대로 두시오.

만약 파란 모자를 쓰고 있고 현재 1을 보고 있다면, 1을 지우고 오른쪽으로 한칸 이동하시오. 그 후 보라색 모자를 쓰시오.

만약 하얀 모자를 쓰게 됐다면 책을 덮으시오. 그리고 "수락" 이라고 큰 소리로 외치시오.

만약 검은 모자를 쓰게 됐다면 책을 덮으시오. 그리고 "거절" 이라고 큰 소리로 외치시오.

이런 내용들이 빼곡히 담겨 있습니다. 이제 소수가 뭔지 모르는 꼬마 요정에게 7이 소수인지 아닌지 판별하게 해보겠습니다. 테이프에 111(7을 이진법으로 표현) 쓰고 빨간 모자를 씌운 요정에게 줍니다. 그럼 이 요정은 책의 규칙에 따라 현재 빨간 모자를 쓰고 있고 1을 보고 있으니 테이프의 왼쪽으로 한칸 이동하고 파란 모자로 갈아입습니다. 또 1을 보고 있지만 이번에는 파란 모자를 쓰고 있으니 1을 지우개로 지우고 오른쪽으로 이동한 뒤 보라색 모자를 씁니다. 이렇게 계속 반복합니다. 한 30분쯤 지나니까 꼬마 요정이 하얀 모자를 쓰고 "수락" 이라 외칩니다. 소수가 뭔지 몰랐음에도 7이 소수란걸 알아낸거죠. 물론 제가 무한루프에 빠지게 만드는 책을 줬을 수도 있습니다. 그러면 꼬마 요정은 열심히 테이프에 0과 1을 썼겠죠. 하지만 요정은 자기가 멈출지 말지 모릅니다. 그저 책의 규칙에 따라 0과 1을 쓸 뿐입니다. 만약 요정이 반드시 멈추게 된다면 그 책을 "결정 가능하다" 라고 말합니다. 요정이 무한루프에 빠질 수도 있다면 그 책을 "결정 가능하지 않다" 라고 하고요.

튜링이 증명한 것은 "임의의 수학적 명제의 참/거짓 여부를 판별하는 법" 이라 쓰여진 결정 가능한 책은 존재할 수 없다 라는 것입니다. 지구상 모든 도서관을 뒤져봐도, 아니 과거에서부터 미래까지 존재할 그 어떤 도서관에 가도 그러한 책은 없다는 것입니다.

그리고 이 요정이 이론상 할 수 있는 모든일이 우리가 생각하는 알고리즘의 개념과 같다는게 처치-튜링 논제입니다. 이건 철학적 주장입니다. 증명된게 아니에요. 하지만 많은 컴퓨터공학자들이 이게 맞다고 믿습니다. 왜냐하면 지금껏 알고리즘의 수학적 정의가 여럿 나왔는데, 그 수많은 정의들이 튜링기계의 정의와 사실은 같다는게 증명되어서 그렇습니다. 앞서 말한 처치도 람다 대수라는 알고리즘의 정의를 내렸는데요, 튜링기계와 이론적으로 같다고 1937년에 튜링이 밝혀냈습니다. 또 모든 프로그래밍 언어 (파이썬, C 등) 는 이론상 튜링기계로 구현할 수 있습니다. 여기서 더 들어가면 물리적 처치-튜링 논제가 있습니다. 물리적 처치-튜링 논제가 주장하는건 물리현상이 계산하는 그 어떤 것도 책을 랜덤하게 넘기는 요정이 시뮬레이션할 수 있다 라는 것입니다. 확률적 튜링기계라고 합니다 (맞는 비유는 아닙니다). 만약 물리적 처치-튜링 논제가 참이라면 "자유의지는 존재하나?" 라는걸 언젠가는 수학적으로 모델링 할 수 있을거라 생각합니다. 결정 가능한지는 둘째 치고요.

@궤소리방정식

조지포지 글쓴이

23.02.05

오오 감사합니다 좀 정리가 되었습니다!!

@궤소리방정식