British Museum algorithm: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 00:05, 28 February 2023

The British Museum algorithm is a general approach to finding 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.

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."

Sources

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.

[newell-1] 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.

[1]

@@ Line 1: / Line 1: @@
+{{Use dmy dates|date=August 2015}}
-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.
+{{Use British English|date=August 2015}}
+The '''British Museum algorithm''' is a general approach to finding 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 problems. (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).
+Newell, Shaw, and Simon<ref name="newell">{{Cite journal | last1 = Newell | first1 = A. | author-link1 = Allen Newell | last2 = Shaw | first2 = J. C.  | author-link2 = Cliff Shaw | last3 = Simon | first3 = H. A. | author-link3 = Herbert A. Simon | year = 1958 | title = Elements of a Theory of Human Problem Solving | journal = [[Psychological Review]] | volume = 65 | issue = 3 | pages = 151–166 | publisher = [[American Psychological Association]] | url = https://digitalcollections.library.cmu.edu/node/35224   | doi = 10.1037/h0048495 }}</ref>
-Similar arguments can be made to show that optimizations, theorem proving, language recognition, etc. is possible or impossible.
+called this procedure the British Museum algorithm
+:"... since it seemed to them as sensible as [[infinite monkey theorem|placing monkeys in front of typewriters]] in order to reproduce all the books in the [[British Museum]]."
 == See also ==
-* [[breadth-first search]]
+* [[Bogosort]]
-* [[brute-force search]]
+* [[Branch and bound]]
-* [[exhaustive search]]
+* [[Breadth-first search]]
+* [[Brute-force search]]
+== Sources ==
-''This article contains text from a public domain entry [http://www.nist.gov/dads/HTML/britishmusm.html] from the [[NIST Dictionary of Algorithms and Data Structures]].''
+{{DADS|British Museum technique|britishMuseum}}.
+==References==
+{{Reflist}}
 [[Category:Algorithms]]
+[[Category:British Museum|Algorithm]]