| [ QuizWit ] in KIDS 글 쓴 이(By): guest (123) <booker-cs.cs.unc> 날 짜 (Date): 2003년 7월 10일 목요일 오전 03시 45분 38초 제 목(Title): Re: 잠수함 찾기 진짜 극악하게 말하자면, 뱅뱅 도는 놈이건, sqrt(2) 에 나타나는 놈이건, pi에 나타나는 놈이건(!), 다 잡을 수 있습니다. 랜덤만 아니면 됩니다. 즉, "잠수함은 어떤 (랜덤이 아닌) 규칙을 갖고 있다. 그래서 겉으로 보기엔 동에 번쩍 서에 번쩍하는 것 같지만 실은 매 시간 t마다 t를 그 프로그램에 넣고 돌려서 나오는 위치 (x(t), y(t))에 출현한다. (단 그 프로그램은 유한한 길이로 정의할 수 있어야 한다.)" 이러면 언젠가는 반드시 잡을 수 있습니다. (가능한 튜링 머신의 종류는 countable...) |