British Museum algorithm: Difference between revisions
→See also: Added BogoSort as a reference, as it is a specific example of this algorithm |
No edit summary |
||
| Line 5: | Line 5: | ||
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 is enormous. |
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 is 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) {{Citation needed|date=August 2013}}. |
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, although this can be overcome with [[dovetailing]].) 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) {{Citation needed|date=August 2013}}. |
||
Similar arguments can be made to show that optimizations, theorem proving, language recognition, etc. are possible or impossible. |
Similar arguments can be made to show that optimizations, theorem proving, language recognition, etc. are possible or impossible. |
||
Revision as of 14:59, 6 November 2017
Template:Graph search 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 is 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, although this can be overcome with dovetailing.) 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) [citation needed].
Similar arguments can be made to show that optimizations, theorem proving, language recognition, etc. are possible or impossible.
Newell, Shaw, and Simon[1] called this procedure the British Museum algorithm
- "... since it seemed to them as sensible as placing monkeys in front of typewriters in order to reproduce all the books in the British Museum."
See also
Sources
- Original text by
This article incorporates public domain material from Paul E. Black. "British Museum technique". Dictionary of Algorithms and Data Structures. NIST..
References
- ^ Newell, A.; Shaw, J. C.; Simon, H. A. (1958). "Elements of a Theory of Human Problem Solving". Psychological Review. 65 (3). American Psychological Association: 151–166. doi:10.1037/h0048495.