바쁜 비버
package.lua 80번째 줄에서 Lua 오류: module 'Module:Message box/localize' not found. package.lua 80번째 줄에서 Lua 오류: module 'Module:Namespace detect/data' not found. 이해하기 쉽게 설명하자면, 이론 컴퓨터 과학에서 바쁜 비버 게임(package.lua 80번째 줄에서 Lua 오류: module 'Module:Langname/data' not found.: busy beaver game)은 주어진 크기에서 가능한 최대치의 출력값을 구하는, 스스로 종결하는 프로그램을 구하는 것을 목표로 한다.[1]
좀 더 정확하게는, 바쁜 비버 게임은 주어진 상태 모음만 사용하여 테이프에 제일 많은 1들을 기록하는 것을 목표로 하는, 정지하는 2진법 튜링 기계로 이루어진다. 이 게임의 규칙은 다음과 같다:
- 기계는 정지 상태를 포함해 두 상태를 가져야 하고,
- 테이프는 처음에는 0들만을 포함한다.
참여자는 기계가 결국 멈출 것을 전제로, 1들로 이루어진 제일 긴 출력을 목표로 하는 전이표를 가지고 있어야 한다.
n번째 바쁜 비버(package.lua 80번째 줄에서 Lua 오류: module 'Module:Langname/data' not found.: nth busy beaver), BB-n, 단순히 바쁜 비버(package.lua 80번째 줄에서 Lua 오류: module 'Module:Langname/data' not found.: busy beaver)는 n 개의 상태를 지니는 바쁜 비버 게임을 수행하는 튜링 기계다. 즉, 이 기계는 존재할 수 있는 모든 n 개의 상태를 지니는 튜링 기계들 사이에서 제일 큰 개수의 1들을 출력한다. 예를 들자면 BB-2 튜링 머신은 네 개의 1들을 여섯 단계 동안 달성한다.
바쁜 비버 게임은 계산 가능성 이론, 정지 문제, 복잡도 이론과 연관되어 있다. 이 개념은 1962년에 출판한 티보르 라도(:en:Tibor Radó)의 논문, "On Non-Computable Functions"에서 최초로 소개되었다.
각주[편집]
This article "바쁜 비버" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:바쁜 비버. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
|
This page exists already on Wikipedia. |
