| [ QuizWit ] in KIDS 글 쓴 이(By): guest (sptrkcz) 날 짜 (Date): 1996년06월09일(일) 00시21분23초 KDT 제 목(Title): Re: 수열문제...(Xorn님) 아주 의미부여가 불가능한 것은 아닙니다. 이런 종류의 퍼즐문제에 등장하는 수열이란 당연히 구성적이라는 것을 전제로 하는데, 이러한 수열은 그렇지 않은 수열에 비해 상당히 갯수가 적죠. 이제 모든 알고리즘을 표현할 수 있는 시스템을 하나 고정하고(예를 들어 튜링머신이나 C언어, L-system, lambda calculus, recursive functions, ...기타 등등 아무거나 취향대로) 그 위에 복잡성에 대한 척도를 하나 정해 두면(예를 들어 C언어로 짠 프로그램의 길이 같은 것이 그런대로 쓸만한 것이 되겠지요), 어떤 수열의 처음 몇 항이 주어지고 다음 항을 맞추는 문제는 '당연히' 그러한 것으로 가장 단순한 규칙을 가지는 것이어야 할 것입니다. 즉, 무한개의 항을 출력하는 알고리즘으로서 초기 항이 주어진 것과 일치하는 알고리즘중, 가장 복잡성이 작은 것을 골라야 하겠지요. 예를 들어 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18, 자 이제 다음 항이 뭐게?라고 물었다면 지독히 이상한 복잡성의 척도를 가정하지 않는 한 왠만하면 답은 19가 될 것입니다. 물론 어떤 시스템과 어떤 척도를 사용하느냐에 따라 답은 달라집니다. 뿐만 아니라, 어떤 알고리즘이 가장 효율적이라는 것을 증명하는 것은 대부분의 경우 불가능하다는 증명이 있습니다. 그러나 이론적으로 주어진 어떤 수열이 있을 때, '맞는 답'이라는 것이 있기는 있는 셈이지요. 또한 그 시스템과 척도에 대해서는, 좀 억지이기는 하지만 적당히 교육을 받은 사람의 뇌와 그것이 이해하는 복잡성이란 충분히 보편적이고, 따라서 이런 문제에 대해 거칠기는 하더라도 기준이 될 수 있다고 생각됩니다. 물론 이것은 원칙에 대한 문제이지요. ^_^ |