| [ KAIST ] in KIDS 글 쓴 이(By): chopin (** 쇼팽 **) 날 짜 (Date): 2004년 1월 11일 일요일 오전 01시 50분 06초 제 목(Title): [계층구조론]이해-3.4 계산가능과 계산불능 <div id=l123___ style="absolute; width:600;"> 계산가능과 계산불능은 어떤 해법으로 주어진 문제의 답을 찾는데 얼마나 많은 계산량이 소요되는가를 나타내기 위해서 사용되는 개념이다. 바둑게임이 계산불능을 설명할 수 있는 좋은 예이다. 바둑은 가로세로 19개의 격자점에 돌을 놓을 수 있는 가짓수가 발생한다. 따라서 간단히 계산해도 (19x19)! =~ 2^2563으로 우주의 나이(150억년=~2^58초)를 압도하는 가짓수가 발생한다. 그렇기 때문에 바둑에서 최적의 수를 찾는 문제는 그 답이 분명히 정해져 있음에도 불구하고 일반적으로 계산불능에 속한다. <br> 많은 문제에서 계산가능/계산불능은 이해가능/이해불능과 아주 밀접한 관계를 갖는다. 계산이론분야에서는 계산가능과 계산불능을 다음과 같이 나눈다. 그 해를 찾는 것이 계산가능한 문제들은 계산량이 입력 초기조건 가짓수의 다항식(Polynomial Function)으로 표현될 수 있다는 것을 의미다. 그리고 그 해를 찾는 것이 계산불능인 문제들은 계산량이 지수함수(Exponential Function)로 표현되는 복잡도를 가진다는 것을 의미한다 [4]. <br> 예를 들어 x개의 수를 크기순으로 정렬하는 문제는 간단한 방법으로 x^2 만큼의 계산량을 요구한다. 이는 다항식에 속하기 때문에 계산가능에 속한다. x개의 셀을 가진 생명게임에서 임의의 배열을 만들어내는 초기조건을 찾는 문제는 2^x 만큼의 계산량을 요구하며, 이는 지수함수에 속하기 때문에 계산불능이라고 이야기한다. <br> 그 문제의 해를 찾는 것이 계산불능인 경우에는 그 문제가 발생시키는 생성결과들이 선형논리 패턴의 조합에 의해서 만들어지지 않는 경우이다. 계산불능문제는 언제나 비선형적인 논리체계에 의해서 구성되어 있다. 따라서 계산불능 문제는 이해불능에 속할 수밖에 없다. <br> 계산가능이냐 불능이냐가 이해에 있어서 중요한 이유는 많은 문제들에 대한 해법이 계산불능영역에 있기 때문이다. 현상을 이해할 때는 그것의 원리를 이해해야 하지만, 어떤 문제를 이해하기 위해서는 해법을 찾고 그 해법을 이해해야 한다. 그리고 그 해법이 계산가능한 해법인가를 따져 봐야한다. 만약, 해법자체가 계산불능에 속한다면 그 해법이 아무리 간단하고 단순하더라도 우리는 그 문제와 답을 완전히 이해했다고 말할 수 없다. <br> 바둑의 예를 다시 들어보자. 바둑에서 현재 주어진 판에서 가장 좋은 다음 수를 찾는 문제는 아주 다양한 여러가지 해법이 있을 수 있다. 그 중 가장 간단한 해법은 가능한 모든 수를 미리 수읽기해 보는 것이다. 이 해법은 앞서 말한 바와 같이 계산불능영역에 속하는 해법이기 때문에 실행불가능하다. 이 해법을 위해서 동원되는 방법은 매우 간단하지만, 그것이 생성하는 패턴들이 무제한적으로 많기 때문에 이해에 전혀 도움을 주지 않는다. <br> 이와 같이 주어진 문제의 해법이 매우 간단한 경우, 우리는 그 문제를 이해했다는 오해를 하기 쉽다. 바둑의 난해함을 이해하지 못하거나, 계산불능의 성격을 이해하지 못하는 사람들이 주로 바둑문제는 컴퓨터로 모든 수를 읽도록 만들면 쉽게 풀리는거 아니냐 하는 오해를 한다. 이런 오해를 피하기 위해서 잊지 말아야 할 중요한 점은, 해법이 존재한다 하더라도 그 해법이 계산불능이라면 문제 이해에 전혀 도움을 주지 않는다는 것이다. <br> --------------------------------------------------------- 이해에 대한 메모 5 - 계산불능 계산불능에 속하는 해법은 문제이해에 전혀 도움을 주지 않는다. --------------------------------------------------------- <br> 계산가능과 계산불능은 앞으로 우리가 그 문제를 주어진 방법으로 풀 수 있는가를 말해주기 때문에 매우 중요한 개념이다. “세상의 모든 것을 이해할 수 있을 것인가” 하는 의문을 풀기 위해 우리가 함께 여행을 하는 중 이라는 것을 다시 상기하자. 세상의 모든 것을 이해한다는 것은 궁극적으로 모든 문제에 대한 답이 풀리고 해법이 주어진다는 뜻이다. 그렇지만 그 해법이 계산불능이라면 우리는 그 문제와 답을 정확히 이해했다고 말할 수 없으며, 그 답이 진정으로 옳은 것인가를 검증하기도 어려워진다. <br> 또한 계산가능과 계산불능은 지금 문제를 풀기 위하여 접근하고 있는 많은 시도들이 가능성이 있는 것인가를 말해주기도 한다. 과학이라는 학문에서 도달할 수 있는 영역이 어디까지인가를 파악하는데 이 개념이 매우 큰 도움을 주기도 하며, 구체적으로 어떤 연구방법이 실효성이 있고 가능성이 있는지를 평가하는데도 큰 도움을 준다. 사고와 정신세계를 연구하는데 심리학적 접근과 신경세포학적인 접근이 어떤 한계와 가능성이 있는지를 말해주기도 한다. <br> 이 글에서는 앞으로 문제자체의 이해를 넘어, 문제의 해답을 찾는 과정에서의 가능성과 그것을 이해할 수 있는 가능성에 대해서 논할 때 이 계산가능과 계산불능의 개념이 아주 중요하게 사용될 것이다. <br> 주: [4] Sara Baase, “Computer Algorithms Introduction to Design and Analysis”, Addison Wesley, 2nd Edition, 1991. <br> </div> __ 쇼팽 e-mail: c h o p i n x e n a k i s 2 @ h o t m a i l . c o m homepage: http://brainew.com Copy right by author All rights reserved |