| [ QuizWit ] in KIDS 글 쓴 이(By): outsider (하얀까마귀) 날 짜 (Date): 2003년 7월 10일 목요일 오전 10시 12분 02초 제 목(Title): Re: 잠수함 찾기 진짜 극악하게 말하자면, 뱅뱅 도는 놈이건, sqrt(2) 에 나타나는 놈이건, pi에 나타나는 놈이건(!), 다 잡을 수 있습니다. 랜덤만 아니면 됩니다. 즉, "잠수함은 어떤 (랜덤이 아닌) 규칙을 갖고 있다. 그래서 겉으로 보기엔 동에 번쩍 서에 번쩍하는 것 같지만 실은 매 시간 t마다 t를 그 프로그램에 넣고 돌려서 나오는 위치 (x(t), y(t))에 출현한다. (단 그 프로그램은 유한한 길이로 정의할 수 있어야 한다.)" 이러면 언젠가는 반드시 잡을 수 있습니다. (가능한 튜링 머신의 종류는 countable...) ----- 요건 안될 것 같은데요. 이렇게 수색하는 헬리콥터의 알고리즘을 H라고 할때 H 자체도 튜링머신으로 기술할 수 있다면 "H 를 따라 수색하는 헬리콥터가 t시간째에 수색하는 포인트를 (x(t), y(t))라고 하면 그때마다 (x(t)+1, y(t)+1)에서 부상한다" 는 프로그램에 따르는 잠수함은 언제나 헬리콥터보다 한발 앞서 가게 됩니다. 이것은 서로 모순되는 결과이므로 알고리즘 H는 튜링머신으로 기술할 수 없습니다. -- 빛이 어둠이고, 어둠이 빛이라면 @< 달은 커다란 검은 구멍일테고 //) 까마귀 날개는 은빛처럼 반짝이리. `//<_ 하얀까마귀 그리고 내 사랑 그대는 죄악처럼 어두우리. |