무한 서수를 사용해도 Nim은 항상 끝난다: 엡실론-0으로 가는 길

The road to epsilon-zero: Nim always ends, even with infinite ordinals

Nim 게임에 무한 서수(ordinal)를 나타내는 초록색 토큰을 도입하면 게임이 영원히 계속될 것처럼 보일 수 있습니다. 그러나 저자는 서수의 well-founded 성질 덕분에 어떤 유한한 시간 안에 게임이 반드시 끝난다는 것을 논증합니다. 이 글은 무한 토큰이 포함된 Nim 게임이 왜 항상 종료되는지, 그리고 이 성질이 재귀 프로그램의 종료를 보장하는 이론적 기반이 되는지를 설명합니다. 또한 프로그래밍 작업의 시간 추정에 대한 일화를 통해 무한 서수의 개념을 직관적으로 전달합니다.