busy beaver

Computing Dictionary

Busy Beaver definition

theory
(BB) One of a series of sets of Turing Machine programs. The BBs in the Nth set are programs of N states that produce a larger finite number of ones on an initially blank tape than any other program of N states. There is no program that, given input N, can deduce the productivity (number of ones output) of the BB of size N.
The productivity of the BB of size 1 is 1. Some work has been done to figure out productivities of bigger Busy Beavers - the 7th is in the thousands.
(1994-10-24)

The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Explore Dictionary.com
Previous Definition: busy as a bee
Next Definition: busy bee
Words Near: busy beaver
More from Thesaurus.com
Synonyms and Antonyms for busy beaver
More from Reference.com
Search for articles containing busy beaver
More from Dictionary.com Translator
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature