| [ QuizWit ] in KIDS 글 쓴 이(By): kimsr (Pabochet) 날 짜 (Date): 2003년 7월 10일 목요일 오후 11시 17분 21초 제 목(Title): Re: 잠수함 찾기 술먹고 쓰는 거라 횡수가 될가능성이 높지만... > 그렇다면, unbounded finite time에 잠수함을 찾는 알고리즘과 > infinite time에 잠수함을 찾는(\equiv 잠수함을 못찾는) 알고리즘을 > 구별할 수 없겠군요. 그렇지는 않습니다. Solvable이지만 undecidable인 문제들이 다 동등하다는 의미는 상당히 rough한 의미에서 그런 것입니다. 특정한 그룹의 알고리즘들은 (튜링머신이나 다른 것으로 표현했을 때) 튜링머신에 의해서 구별이 가능한 경우가 많습니다. Undecidable이란 말의 의미는 어떤 튜링 머신을 주어도 구별해 낼 수 있는 하나의 튜링 머신이 없다는 말입니다. > 결국은, random search하는 algorithm과 outsider님의 algorithm을 > 아무도 구별 못한다는 얘기가 되는군요.^^ 사람은 구별할 수 있고, 두개의 알고리즘을 구별해 낼수 있는 튜링 머신도 분명히 있습니다. 그 튜링 머신이 모든 경우를 구별하지는 못하지만 말입니다. > -> thread가 이렇게 길어지게 된 이유가 여기에 있었던거군요. ^^ 글쎄요. 유한성과 무한성의 문제는 기본적인 것입니다만 쉽지 않습니다. 수학의 역사를 봤을때 비교적 최근에야 이해된 것으로 쉬운 내용이 아닙니다. 그 난이도가 thread를 길게 만든 것이지 두 알고리즘을 구별할 방법이 없다는 점은 아닙니다. 두 알고리즘을 구별할 방법은 분명히 있습니다. 가장 중요한 문제점은 finite와 bounded가 많은 경우 혼동된다는 점인 것 같습니다. 일상적으로는 같은 의미로도 사용되고, 현실적인 의미에서 다른 점이 없습니다만, 수학적으로는 상당히 다른 의미를 가집니다. 엄밀한 의미의 유한이라는 점을 분명히 밝히지 않은 것이 문제라면 문제겠지요. |