British Museum algorithm

British Museum algorithm

The British Museum algorithm is a general approach to find a solution by checking all possibilities one by one, beginning with the smallest. The term refers to a conceptual, not a practical, technique where the number of possibilities are enormous.

For instance, one may, in theory, find the smallest program that solves a particular problem in the following way: Generate all possible source codes of length one character. Check each one to see if it solves the problem. (Note: the halting problem makes this check troublesome.) If not, generate and check all programs of two characters, three characters, etc. Conceptually, this finds the smallest program, but in practice it tends to take an unacceptable amount of time (more than the lifetime of the universe, in many instances).

Similar arguments can be made to show that optimizations, theorem proving, language recognition, etc. is possible or impossible.

See also

* Breadth-first search
* Brute-force search
* Exhaustive search
* British Museum

Sources

* Original text by DADS|British Museum technique|britishMuseum.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • Outline of combinatorics — See also: Index of combinatorics articles The following outline is presented as an overview of and topical guide to combinatorics: Combinatorics – branch of mathematics concerning the study of finite or countable discrete structures. Contents 1… …   Wikipedia

  • Islamic contributions to Medieval Europe — Christian and Muslim playing chess in al Andalus, from The Book of Games of Alfonso X, el Sabio, c. 1285. The game of chess originated in India, but was transmitted to Europe by the Islamic world.[1] Islamic contributions to Medieval Europe …   Wikipedia

  • mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… …   Universalium

  • thought — thought1 /thawt/, n. 1. the product of mental activity; that which one thinks: a body of thought. 2. a single act or product of thinking; idea or notion: to collect one s thoughts. 3. the act or process of thinking; mental activity: Thought as… …   Universalium

  • Quicksort — Infobox Algorithm class=Sorting algorithm Quicksort in action on a list of numbers. The horizontal lines are pivot values. data=Varies time=O(nlog n) on average space=Varies by implementation optimal=Sometimes Stability= [Sorting… …   Wikipedia

  • Dice — For other uses, see Dice (disambiguation). Four coloured dice showing all six possible sides (on a right handed, 6 sided die with pips) A die (plural dice, from Old French dé, from Latin datum something which is given or played )[1] …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”