호프스태터의 법칙 (Hofstadter's Law)
개요
Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law.
호프스태터의 법칙: 호프스태터의 법칙을 고려했을 때조차도, 언제나 예상한 것보다 시간이 더 걸린다.1
더글라스 호프스태터(Douglas Hofstadter)의 Gödel, Escher, Bach에 나오는 법칙으로, 재귀적 과정의 실행 시간을 정확하게 추정하는 일이 어렵다는 것을 말한다.
재미있게도 재귀적 문장 구조를 갖고 있다.
괴델, 에셔, 바흐
컴퓨터 체스의 초창기에는 컴퓨터(또는 프로그램)를 체스 세계 챔피언으로 만드는 데에 10년쯤 걸릴 것으로 추정했다. 그러나 10년이 지난 후에도 컴퓨터가 세계 챔피언이 되려면 여전히 10년 이상 걸릴 것으로 보였다……. 이것은 재귀적인 호프스태터의 법칙에 대한 또 하나의 증거이다.1
위의 인용문은 참 재미있는 부분인데, 체스 프로그램이 하나의 체스 게임에서 승리하기 위한 행마를 검토하기 위해 재귀적으로 탐색한다는 것을 설명한 다음 체스 프로그램이 세계 챔피언이 되는 승리를 얻는데 필요한 시간을 또 추정하고 있는 문장이기 때문이다. 재귀적인 상황에 대해 재귀적으로 설명하고 있는 셈.
참고문헌
- 괴델, 에셔, 바흐 / 더글러스 호프스태더 저/박여성 역 / 까치(까치글방) / 개역판 1쇄 2017년 07월 10일 / 원서: Godel, Escher, Bach: An Eternal Golden Braid