Post correspondence problem

The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946.[1] Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.

Definition of the problem

Let be an alphabet with at least two symbols. The input of the problem consists of two finite lists and of words over . A solution to this problem is a sequence of indices with and for all , such that

The decision problem then is to decide whether such a solution exists or not.

Alternative definition

This gives rise to an equivalent alternative definition often found in the literature, according to which any two homomorphisms with a common domain and a common codomain form an instance of the Post correspondence problem, which now asks whether there exists a nonempty word in the domain such that

.

Another definition describes this problem easily as a type of puzzle. We begin with a collection of dominos, each containing two strings, one on each side. An individual domino looks like

and a collection of dominos looks like

.

The task is to make a list of these dominos (repetition permitted) so that the string we get by reading off the symbols on the top is the same as the string of symbols on the bottom. This list is called a match. The Post correspondence problem is to determine whether a collection of dominos has a match. For example, the following list is a match for this puzzle.

.

For some collections of dominos, finding a match may not be possible. For example, the collection

.

cannot contain a match because every top string is longer than the corresponding bottom string.

Example instances of the problem

Example 1

Consider the following two lists:

A solution to this problem would be the sequence (3, 2, 3, 1), because

Furthermore, since (3, 2, 3, 1) is a solution, so are all of its "repetitions", such as (3, 2, 3, 1, 3, 2, 3, 1), etc.; that is, when a solution exists, there are infinitely many solutions of this repetitive kind.

However, if the two lists had consisted of only and from those sets, then there would have been no solution (the last letter of any such α string is not the same as the letter before it, whereas β only constructs pairs of the same letter).

A convenient way to view an instance of a Post correspondence problem is as a collection of blocks of the form

there being an unlimited supply of each type of block. Thus the above example is viewed as

where the solver has an endless supply of each of these three block types. A solution corresponds to some way of laying blocks next to each other so that the string in the top cells corresponds to the string in the bottom cells. Then the solution to the above example corresponds to:

Example 2

Again using blocks to represent an instance of the problem, the following is an example that has infinitely many solutions in addition to the kind obtained by merely "repeating" a solution.

In this instance, every sequence of the form (1, 2, 2, . . ., 2, 3) is a solution (in addition to all their repetitions):

Proof sketch of undecidability

The most common proof for the undecidability of PCP describes an instance of PCP that can simulate the computation of an arbitrary Turing machine on a particular input. A match will occur if and only if the input would be accepted by the Turing machine. Because deciding if a Turing machine will accept an input is a basic undecidable problem, PCP cannot be decidable either. The following discussion is based on Michael Sipser's textbook Introduction to the Theory of Computation.[2]

In more detail, the idea is that the string along the top and bottom will be a computation history of the Turing machine's computation. This means it will list a string describing the initial state, followed by a string describing the next state, and so on until it ends with a string describing an accepting state. The state strings are separated by some separator symbol (usually written #). According to the definition of a Turing machine, the full state of the machine consists of three parts:

  • The current contents of the tape.
  • The current state of the finite-state machine which operates the tape head.
  • The current position of the tape head on the tape.

Although the tape has infinitely many cells, only some finite prefix of these will be non-blank. We write these down as part of our state. To describe the state of the finite control, we create new symbols, labelled q1 through qk, for each of the finite-state machine's k states. We insert the correct symbol into the string describing the tape's contents at the position of the tape head, thereby indicating both the tape head's position and the current state of the finite control. For the alphabet {0,1}, a typical state might look something like:

101101110q700110.

A simple computation history would then look something like this:

q0101#1q401#11q21#1q810.

We start out with this block, where x is the input string and q0 is the start state:

 
q0x#

The top starts out "lagging" the bottom by one state, and keeps this lag until the very end stage. Next, for each symbol a in the tape alphabet, as well as #, we have a "copy" block, which copies it unmodified from one state to the next:

a
a

We also have a block for each position transition the machine can make, showing how the tape head moves, how the finite state changes, and what happens to the surrounding symbols. For example, here the tape head is over a 0 in state 4, and then writes a 1 and moves right, changing to state 7:

q40
1q7

Finally, when the top reaches an accepting state, the bottom needs a chance to finally catch up to complete the match. To allow this, we extend the computation so that once an accepting state is reached, each subsequent machine step will cause a symbol near the tape head to vanish, one at a time, until none remain. If qf is an accepting state, we can represent this with the following transition blocks, where a is a tape alphabet symbol:

There are a number of details to work out, such as dealing with boundaries between states, making sure that our initial tile goes first in the match, and so on, but this shows the general idea of how a static tile puzzle can simulate a Turing machine computation.

The previous example

q0101#1q401#11q21#1q810.

is represented as the following solution to the Post correspondence problem:

Variants

Many variants of PCP have been considered. One reason is that, when one tries to prove undecidability of some new problem by reducing from PCP, it often happens that the first reduction one finds is not from PCP itself but from an apparently weaker version.

  • The problem may be phrased in terms of monoid morphisms f, g from the free monoid B to the free monoid A where B is of size n. The problem is to determine whether there is a word w in B+ such that f(w) = g(w).[3]
  • The condition that the alphabet have at least two symbols is required since the problem is decidable if has only one symbol.
  • A simple variant is to fix n, the number of tiles. This problem is decidable if n ≤ 2,[4] but remains undecidable for n ≥ 5. It is unknown whether the problem is decidable for 3 ≤ n ≤ 4.[5]
  • The circular Post correspondence problem asks whether indexes can be found such that and are conjugate words, i.e., they are equal modulo rotation. This variant is undecidable.[6]
  • One of the most important variants of PCP is the bounded Post correspondence problem, which asks if we can find a match using no more than k tiles, including repeated tiles. A brute force search solves the problem in time O(2k), but this may be difficult to improve upon, since the problem is NP-complete.[7] Unlike some NP-complete problems like the boolean satisfiability problem, a small variation of the bounded problem was also shown to be complete for RNP, which means that it remains hard even if the inputs are chosen at random (it is hard on average over uniformly distributed inputs).[8]
  • Another variant of PCP is called the marked Post Correspondence Problem, in which each must begin with a different symbol, and each must also begin with a different symbol. Halava, Hirvensalo, and de Wolf showed that this variation is decidable in exponential time. Moreover, they showed that if this requirement is slightly loosened so that only one of the first two characters need to differ (the so-called 2-marked Post Correspondence Problem), the problem becomes undecidable again.[9]
  • The Post Embedding Problem is another variant where one looks for indexes such that is a (scattered) subword of . This variant is easily decidable since, when some solutions exist, in particular a length-one solution exists. More interesting is the Regular Post Embedding Problem, a further variant where one looks for solutions that belong to a given regular language (submitted, e.g., under the form of a regular expression on the set ). The Regular Post Embedding Problem is still decidable but, because of the added regular constraint, it has a very high complexity that dominates every multiply recursive function.[10]
  • The Identity Correspondence Problem (ICP) asks whether a finite set of pairs of words (over a group alphabet) can generate an identity pair by a sequence of concatenations. The problem is undecidable and equivalent to the following Group Problem: is the semigroup generated by a finite set of pairs of words (over a group alphabet) a group.[11]

References

  1. ^ E. L. Post (1946). "A variant of a recursively unsolvable problem" (PDF). Bull. Amer. Math. Soc. 52 (4): 264–269. doi:10.1090/s0002-9904-1946-08555-9. S2CID 122948861.
  2. ^ Michael Sipser (2005). "A Simple Undecidable Problem". Introduction to the Theory of Computation (2nd ed.). Thomson Course Technology. pp. 199–205. ISBN 0-534-95097-3.
  3. ^ Salomaa, Arto (1981). Jewels of Formal Language Theory. Pitman Publishing. pp. 74–75. ISBN 0-273-08522-0. Zbl 0487.68064.
  4. ^ Ehrenfeucht, A.; Karhumäki, J.; Rozenberg, G. (November 1982). "The (generalized) post correspondence problem with lists consisting of two words is decidable". Theoretical Computer Science. 21 (2): 119–144. doi:10.1016/0304-3975(89)90080-7.
  5. ^ T. Neary (2015). "Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words". In Ernst W. Mayr and Nicolas Ollinger (ed.). 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). STACS 2015. Vol. 30. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 649–661. doi:10.4230/LIPIcs.STACS.2015.649.
  6. ^ K. Ruohonen (1983). "On some variants of Post's correspondence problem". Acta Informatica. 19 (4). Springer: 357–367. doi:10.1007/BF00290732. S2CID 20637902.
  7. ^ Michael R. Garey; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. p. 228. ISBN 0-7167-1045-5.
  8. ^ Y. Gurevich (1991). "Average case completeness" (PDF). J. Comput. Syst. Sci. 42 (3). Elsevier Science: 346–398. doi:10.1016/0022-0000(91)90007-R. hdl:2027.42/29307.
  9. ^ V. Halava; M. Hirvensalo; R. de Wolf (2001). "Marked PCP is decidable". Theor. Comput. Sci. 255 (1–2). Elsevier Science: 193–204. doi:10.1016/S0304-3975(99)00163-2.
  10. ^ P. Chambart; Ph. Schnoebelen (2007). Post embedding problem is not primitive recursive, with applications to channel systems (PDF). Lecture Notes in Computer Science. Vol. 4855. Springer. pp. 265–276. doi:10.1007/978-3-540-77050-3_22. ISBN 978-3-540-77049-7.
  11. ^ Paul C. Bell; Igor Potapov (2010). "On the Undecidability of the Identity Correspondence Problem and its Applications for Word and Matrix Semigroups". International Journal of Foundations of Computer Science. 21 (6). World Scientific: 963–978. arXiv:0902.1975. doi:10.1142/S0129054110007660.

Read other articles:

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Oktober 2022. Artikel atau sebagian dari artikel ini mungkin diterjemahkan dari Cartesian oval di en.wikipedia.org. Isinya masih belum akurat, karena bagian yang diterjemahkan masih perlu diperhalus dan disempurnakan. Jika Anda menguasai bahasa aslinya, harap pertim...

 

This article is about the 2005 Cambodian film. For other films with similar titles, see Crocodile (disambiguation). 2005 Cambodian filmThe CrocodilePromotional PosterDirected byMao AyuthWritten byMao AyuthProduced byMao AyuthStarringDy SavethPreap SovathSim Solika Rathanak (Prek)Release date 2005 (2005) Running time120 minutesCountryCambodiaLanguageKhmerBudget$100,000 The Crocodile (Khmer: នេសាទក្រពើ, Nésat Krâpeu; lit. 'Crocodile Fishing') is a 2005 Cambo...

 

American college basketball season This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: 2019–20 Northern Illinois Huskies men's basketball team – news · newspapers · books · scholar · JSTOR (April 2021) (Learn how and when to remove this template message) 2019–20 Northern Illinois Huskies men's basketballMAC ...

Sebuah manjanik berpengimbang di Château des Baux, Prancis. Manjanik (dari bahasa Arab: منجنيق; manjiniq) adalah suatu alat atau senjata pelontar berpengimbang berat yang banyak digunakan dalam pertempuran pada Abad Pertengahan untuk menghancurkan dinding atau bangunan yang difortifikasi. Manjanik bekerja berdasarkan pada konsep keseimbangan benda dan mekanisme umban tongkat. Diduga manjanik pertama kali digunakan di Eropa oleh Bizantium. Manjanik dipercayai pertama kali dibuat di Cina...

 

American writer and blogger Jonathan MitchellMitchell in 2015Born (1955-09-07) September 7, 1955 (age 68)Los Angeles, California, USEducationPsychology (BS)[1]Alma materUCLAYears active2003-present (writer)RelativesMelanie Mitchell (sister)[2]Websitejonathans-stories.com Neurodiversity paradigm Philosophy Bodily autonomy Disability rights movement Independent living movement Self-advocacy Organizations Aspies For Freedom Autism Network International Autistic Sel...

 

Peta wilayah Komune Canicattì (merah) di Provinsi Agrigento (emas), Sisilia, Italia. Canicattì commune di Italia Canicattì (it) Tempat Negara berdaulatItaliaRegion otonom dengan status khususSiciliaProvinsi di ItaliaProvinsi Agrigento NegaraItalia Ibu kotaCanicattì PendudukTotal34.449  (2023 )GeografiLuas wilayah91,86 km² [convert: unit tak dikenal]Ketinggian465 m Berbatasan denganMontedoro (en) Caltanissetta Delia (en) Castrofilippo Racalmuto Naro Serradifalco (en) Ravanusa Ca...

Swedish multinational retail conglomerate For the city in Nigeria, see Ikeja. Inter IKEA Systems B.V.IKEA store in Conshohocken, PennsylvaniaTrade nameIKEACompany typePrivateIndustryRetailFounded28 July 1943; 80 years ago (1943-07-28)[1] in SwedenFounderIngvar KampradHeadquartersLeiden, NetherlandsNumber of locations462 (2023)[2]Area servedWorldwideKey people Jesper Brodin (Chairman and CEO of INGKA Holding)[3] Jon Abrahamsson Ring (Chairman and CEO o...

 

Demonic creature in Balkan mythology This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Psoglav – news · newspapers · books · scholar · JSTOR (Augus...

 

Connection that allows an object to rotate horizontally or vertically For other uses, see Swivel (disambiguation). A swivel in a chain link Stainless steel anchor swivel A swivel in a link A swivel is a connection that allows the connected object, such as a gun, chair, swivel caster, or an anchor rode to rotate horizontally or vertically. Swivel designs A common design for a swivel is a cylindrical rod that can turn freely within a support structure. The rod is usually prevented from slipping...

Collection of Middle Eastern folk tales For other uses, see One Thousand and One Nights (disambiguation), 1001 Nights (disambiguation), and Arabian Nights (disambiguation). One Thousand and One Nights Cassim in the Caveby Maxfield Parrish (1909)LanguageArabicGenreFrame story, folkloreSet inMiddle AgesTextOne Thousand and One Nights at Wikisource Part of a series onArabic culture ArchitectureStyles Islamic Yemeni Nabataean Umayyad Abbasid Fatimid Moorish Mamluk Features Ablaq Alfiz Arabes...

 

Part of a series onHorror films History Lists By decade 1896–1959 1890s 1900s 1910s 1920s 1930s 1940s 1950s 1960s 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970s 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980s 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990s 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000s 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010s 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020s 2020 2021 2022 2023 2024 2025 By continent A...

 

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Februari 2023. WSR-74 radar adalah sebuah Weather Surveillance Radar dirancang pada tahun 1974 untuk National Weather Service. Mereka ditambahkan ke jaringan yang ada dari Model WSR-57 untuk meningkatkan prakiraan dan peringatan cuaca buruk. Beberapa telah dijual ke...

Division of Air India Limited This article is about a defunct airline. For other airlines of India, see List of airlines of India. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Indian Airlines – news · newspapers · books · scholar · JSTOR (July 2012) (Learn how and when to remove this message) Indian Airli...

 

American civil rights leader; wife of Martin Luther King, Jr. (1927–2006) Coretta Scott KingKing in 1964BornCoretta Scott(1927-04-27)April 27, 1927Heiberger, Alabama, U.S.DiedJanuary 30, 2006(2006-01-30) (aged 78)Rosarito, Baja California, MexicoResting placeKing Center for Nonviolent Social ChangeEducationAntioch College (BA)New England Conservatory of Music (BM)OccupationsActivistauthorPolitical partyDemocraticSpouse Martin Luther King Jr. ​ ​(m. 1953;...

 

Kategoria Superiore 2008-2009 Competizione Kategoria Superiore Sport Calcio Edizione 70ª Organizzatore FSHF Date dal 24 agosto 2008al 23 maggio 2009 Luogo  Albania Partecipanti 12 Risultati Vincitore  Tirana(24º titolo) Retrocessioni  Bylis Ballsh Partizani Tirana Lushnja Elbasani Statistiche Miglior marcatore Migen Memelli (23) Cronologia della competizione 2007-2008 2009-2010 Manuale La Kategoria Superiore 2008-2009 fu la 70ª edizione della mas...

American labor union SUPSailors' Union of the PacificFoundedMarch 6, 1885LocationUnited StatesMembers 736 (2005)Key peopleGunnar Lundeberg, presidentAffiliationsAFL-CIOWebsitesailors.org The Sailors' Union of the Pacific (SUP), founded on March 6, 1885 in San Francisco, California, [1] is an American labor union of mariners, fishermen and boatmen working aboard US flag vessels. At its fourth meeting in 1885, the fledgling organization adopted the name Coast Sailor's Union and elected ...

 

الصراع الدرزي على السلطة (1658–1667) خريطة توزيع دروز لبنان في 1844، تُظهر نهر الكلب باعتباره الحدود الشمالية للدروز. معلومات عامة التاريخ 1667-1658 الموقع جبل لبنان، الجليل، حوران (سوريا العثمانية) النتيجة خسارة الأسرة المعنية لصفد المتحاربون  الإمبراطورية العثمانية عشائر الد�...

 

Sede do Grupo Folha.Capa do jornal Folha de S.Paulo de 6 de fevereiro de 2018. Empresa Folha da Manhã S.A. Periodicidade Diário (segunda a segunda) Formato Standard Sede São Paulo País Brasil Slogan O Jornal do FuturoUm Jornal a Serviço do Brasil Fundação 19 de fevereiro de 1921 (103 anos) Fundador(es) Olival Costa e Pedro Cunha Presidente Luiz Frias Diretor Otavio Frias Filho (1984-2018)Maria Cristina Frias (2018-2019)Sérgio Dávila (2019-) Orientação política Apartidár...

أغوستين كانوبيو معلومات شخصية الميلاد 1 أكتوبر 1998 (26 سنة)[1]  مونتفيدو[2]  الطول 1.75 م (5 قدم 9 بوصة) مركز اللعب مهاجم الجنسية الأوروغواي  الأب أوزفالدو كانوبيو  معلومات النادي النادي الحالي أتلتيكو باراناينسي الرقم 9 مسيرة الشباب سنوات فريق 2011–2016 سنت�...

 

Chemical compound (H–S–C≡N) Thiocyanic acid[1]   Carbon, C  Sulfur, S  Nitrogen, N  Hydrogen, H Names IUPAC name Thiocyanic acid[4] Other names Hydrogen thiocyanate[2]Sulfocyanic acid[3] Identifiers CAS Number 463-56-9 Y 3D model (JSmol) thiocyanic acid: Interactive imageisothiocyanic acid: Interactive image 3DMet B00344 ChEBI CHEBI:29200 Y ChEMBL ChEMBL84336 Y ChemSpider 760 Y ECHA Inf...