| [ QuizWit ] in KIDS 글 쓴 이(By): Nyang (바하동생) 날 짜 (Date): 2003년 7월 10일 목요일 오후 02시 28분 24초 제 목(Title): Re: 잠수함 찾기 > 곁다리인데... > > ----- > > unbounded finite time에 어떤 문제를 푸는 기계와 > infinite time에 어떤 문제를 푸는 기계(문제는 못풀고 시간만 > 잡아먹는 기계)를 > > 구별할 수 있는 기계가 있을까요? > > ----- > > 이건 halting problem 아닌가요? 저도 곁다리얘기... 저 문제가 halting problem이라면 undecidable이라는 얘기고, 따라서 구별할 수 있는 기계가 없다는 얘기겠지요? 그렇다면, unbounded finite time에 잠수함을 찾는 알고리즘과 infinite time에 잠수함을 찾는(\equiv 잠수함을 못찾는) 알고리즘을 구별할 수 없겠군요. 결국은, random search하는 algorithm과 outsider님의 algorithm을 아무도 구별 못한다는 얘기가 되는군요.^^ -> thread가 이렇게 길어지게 된 이유가 여기에 있었던거군요. ^^ @LFo |