바쁜 비버

이해하기 쉽게 설명하자면, 이론 컴퓨터 과학에서 바쁜 비버 게임(영어: busy beaver game)은 주어진 크기에서 가능한 최대치의 출력값을 구하는, 스스로 종결하는 프로그램을 구하는 것을 목표로 한다.

좀 더 정확하게는, 바쁜 비버 게임은 주어진 상태 모음만 사용하여 테이프에 제일 많은 1들을 기록하는 것을 목표로 하는, 정지하는 2진법 튜링 기계로 이루어진다. 이 게임의 규칙은 다음과 같다:

1. 기계는 정지 상태를 포함해 두 상태를 가져야 하고,
2. 테이프는 처음에는 0들만을 포함한다.

참여자는 기계가 결국 멈출 것을 전제로, 1들로 이루어진 제일 긴 출력을 목표로 하는 전이표를 가지고 있어야 한다.

n번째 바쁜 비버(영어: nth busy beaver), BB-n, 단순히 바쁜 비버(영어: busy beaver)는 n 개의 상태를 지니는 바쁜 비버 게임을 수행하는 튜링 기계다. 즉, 이 기계는 존재할 수 있는 모든 n 개의 상태를 지니는 튜링 기계들 사이에서 제일 큰 개수의 1들을 출력한다. 예를 들자면 BB-2 튜링 머신은 네 개의 1들을 여섯 단계 동안 달성한다.

바쁜 비버 게임은 계산 가능성 이론, 정지 문제, 복잡도 이론과 연관되어 있다. 이 개념은 1962년에 출판한 티보르 라도(:en:Tibor Radó)의 논문, "On Non-Computable Functions"에서 최초로 소개되었다.

같이 보기

• 라요 수