| [ QuizWit ] in KIDS 글 쓴 이(By): kimsr (Pabochet) 날 짜 (Date): 2003년 7월 10일 목요일 오전 10시 53분 41초 제 목(Title): Re: 잠수함 찾기 이렇게 수색하는 헬리콥터의 알고리즘을 H라고 할때 H 자체도 튜링머신으로 기술할 수 있다면 "H 를 따라 수색하는 헬리콥터가 t시간째에 수색하는 포인트를 (x(t), y(t))라고 하면 그때마다 (x(t)+1, y(t)+1)에서 부상한다" 는 프로그램에 따르는 잠수함은 언제나 헬리콥터보다 한발 앞서 가게 됩니다. 이것은 서로 모순되는 결과이므로 알고리즘 H는 튜링머신으로 기술할 수 없습니다. -------------------------------- 모순이 있기는 합니다만 그렇게 모순으로 설명하는 것 보다는 다음과 같은 설명이 더 직관적으로 이해하기 쉽지 않을까 합니다. 알고리즘 H나 그 알고리즘을 공격하는 알고리즘 J나 모두 '기술'하는 것은 가능합니다. 여기서 '기술'한다는 말은 모든 가능한 튜링 머신들을 순서대로 시뮬레이션 하면서, 그 결과를 보고 그 위치로 가는 H를 튜링 머신으로 만드는 것은 가능하다는 말이구요. outsider님이 '기술'할수 없다고 말씀하신 의미는 제대로 된 튜링 머신으로는 안된다는 말씀이셨을 것 같구요. '제대로 된'이라는 말은 주어진 t에 대해 실제로 계산을 끝낼 수 있는 튜링 머신이라고 생각하시면 될 듯 하네요. 여기서 '기술'한다는 말의 의미를 좀더 넓은 '튜링 머신 형태로 기술'한다로 보면 다음과 같이 H가 불가능한 이유를 설명할 수 있습니다. H가 모든 가능한 튜링 머신을 순서대로 시뮬레이션 하면서 t번째의 튜링 머신에 입력을 t로 주고, 출력을 기다린 다음, 출력이 (x(t), y(t))형태인지 확인하고, 그 위치를 검사한다고 합시다. 이렇게 t를 증가시켜 가면서 수행을 하다보면 언젠가는 계산을 멈추지 않는 튜링머신을 만나게 됩니다. 이 시점에서 H는 더 진행하지 못하게 됩니다. outsider님이 말씀하신 공격하는 튜링머신을 J라고 부르고 H가 J를 시뮬레션하는 상황을 생각해 보면 재미있으실 것입니다. (J도 튜링 머신이므로 H가 시뷸레이션하는 리스트에 나옵니다.) 결론적으로 모든 튜링 머신에 대해서 위치를 파악하는 것은 안되구요. 범위를 좁히면 가능합니다. 좁힌 이후에도 대단히 많은 튜링머신들을 포함하게 되구요. H는 적당한 시간 바운드 B(t)를 정해서 그 시간 안에 끝나는 튜링 머신들만을 검사하는 것입니다. 그러면, 시뮬레이션하다가 시간이 넘으면 포기할 수 있습니다. 이렇게 하면 위에서 본 J와 같은 모순은 발생하지 않습니다. B(t)가 t에 의존하는 이유는, 그렇지 않다면 간단하고 실제로 작은 t를 주었을 때 빨리 끝나는 튜링 머신들도 큰 t를 받았다는 이유만으로 검사되지 않는 경우가 있을 수 있기 때문입니다. 모든 튜링 머신을 검사할 수는 없지만 B(t)를 적당히 크게 잡는다면 쉽게 생각할 수 있는 대부분의 것들은 포함이 될 것입니다. |