Posts correspondence problem
Post's correspondence problem A well-known algorithmically unsolvable decision problem. Given a finite set of “dominoes” of the form shown in Fig. a, with u and v being strings, the question is whether or not one can form a sequence, as shown in Fig. b, such that reading all the us in order gives the same string as reading all the vs. Fig. c shows such a sequence, where Λ is the empty string. Even though there are only finitely many different dominoes given, there is an infinite supply of duplicates for each one; the same domino can thus be used more than once in the sequence. Dominoes cannot be inverted.
Depending on the dominoes given, it is sometimes obvious that the answer to the question is “no”. However there is no algorithm that can discover this in all cases.
Depending on the dominoes given, it is sometimes obvious that the answer to the question is “no”. However there is no algorithm that can discover this in all cases.
More From encyclopedia.com
Problem Solving , A managerial problem can be described as the gap between a given current state of affairs and a future desired state. Problem solving may then be tho… Correspond , cor·re·spond / ˌkôrəˈspänd; ˌkär-/ • v. [intr.] 1. have a close similarity; match or agree almost exactly: the carved heads described in the poem cor… Robin Givens , Givens, Robin
1964–
Actress
Actress Robin Givens has played a wide range of characters throughout her career. A similar diversity marked the roles sh… Experience , As the average person understands the term experience, it means no more than familiarity with some matter of practical concern, based on repeated pas… linear programming , linear programming A technique in optimization, pioneered by George B. Dantzig, that is widely used in economic, military, and business-management de… Conundrum , Conundrum
BIBLIOGRAPHY
Conundrums are problems of several types. They may be riddles with a pun for an answer. They may be puzzling problems that are…
You Might Also Like
NEARBY TERMS
Posts correspondence problem