바쁜 비버 함수

바쁜 비버 지난 학기에 논리회로 과목을 수강하던 중, 기말고사 시험 문제로 ‘바쁜 비버’에 대한 문제가 출제되었다. 바쁜 비버는 컴퓨터 과학에서 꽤 중요한 개념이다. 특징도 여러 가지 재미있는 게 많아서, 이에 대해 글을 써본다. 본 글의 목차는 다음과 같다. 바쁜 비버 게임을 소개한다. 바쁜 비버 함수와 최대 시프트 함수를 소개한다. 바쁜 비버 함수의 계산 불가능성을 증명한다. 최대 시프트 함수를 중심으로 성질과 하한을 찾아가는 과정을 다룬다. 이 과정에서 아커만 함수, ZF 공리계, 콜라츠 추측과의 연관 관계를 다룰 것이다. 바쁜 비버로부터 파생된 함수들을 다룬다. 바쁜 비버 게임 바쁜 비버 게임은 1962년 Tibor Radó의 논문 On Non-Computable Functions에서 처음 소개되..