Talk:Post correspondence problem

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Low	This article has been rated as Low-priority on the project's priority scale.

Philosophy: Logic Low‑importance

This article is within the scope of WikiProject Philosophy, a collaborative effort to improve the coverage of content related to philosophy on Wikipedia. If you would like to support the project, please visit the project page, where you can get more details on how you can help, and where you can join the general discussion about philosophy content on Wikipedia.PhilosophyWikipedia:WikiProject PhilosophyTemplate:WikiProject PhilosophyPhilosophy articles

Low

This article has been rated as Low-importance on the project's importance scale.

Associated task forces:
/
	Logic

Proof of undecidability?

It seems to me this page would benefit greatly from a proof that the problem is undecidable. If there's one here already, it needs clarification because I missed it. LizardWizard 16:44, July 13, 2005 (UTC)

There's a proof of this in Sipser, and a proof sketch should certainly be added to the article based on it, but it's quite long and technical and we really don't need all the details. The essential concept is that we can represent a machine step using a certain kind of tile, in such a way that a match must display an accepting computation history of the Turing machine (a list of its states in order). Deco 18:48, 13 July 2005 (UTC)[reply]

Poor phrasing

The sentance "Informally the problem can be described as follows. Given a dictionary that contains pairs of phrases, i.e., a list of words, that mean the same, decide if there is a sentence that means the same in both languages." is pretty ill-worded. "pairs of phrases" are not a "list of words". And what "both" languages are we talking about? I don't see a single language mentioned, let alone two.—Preceding unsigned comment added by 71.115.227.235 (talk • contribs)

Yeah, I agree that it isn't a very helpful addition. I've removed it -- if someone wants to add a more clear informal description of the problem, go ahead. Neilc 16:18, 29 October 2006 (UTC)[reply]

I thought the remark was rather helpful and preferred it stay. So how about: "Informally the problem can be described as follows. Given a dictionary that contains pairs of phrases, i.e., pairs of lists of words that mean the same, decide if there is a sentence that means the same in both languages."? -- Jan Hidders 17:04, 29 October 2006 (UTC)[reply]

Is the 1st figure in the undecidability proof rigt?

It's written in the text that the top starts out with a "lead" of one state, and keeps this lead until the very end. Bit on the figure just above it the top is blank, while bottom contains the initial state.

Am I just stupid or is that a mistake, which should be fixed?

--62.89.75.143 10:31, 28 February 2007 (UTC)[reply]

That mistake has been corrected -- "lead" should have been "lag". — r.e.s. 13:18, 18 November 2009 (UTC)[reply]

Variant Citation

Is there a citation for the second variant listed (fixed number of tiles)? —Preceding unsigned comment added by 72.200.125.221 (talk) 02:40, 26 January 2010 (UTC)[reply]

The listing says "A simple variant is to fix n, the number of tiles. This problem is decidable if n ≤ 2, but remains undecidable for n ≥ 7. It is unknown whether the problem is decidable for 3 ≤ n ≤ 6."

Online sources for each of these claims can be found at this U. Alberta website. In particular ...

... the following paper proves decidability for n ≤ 2 ...

A. Ehrenfeucht, J. Karhumaki and G. Rozenberg. The (generalized) post correspondence problem with lists consisting of two words is decidable, Theoretical Computing Science, 119-144, 21, 2, 1982.

... while the following paper proves undecidability for n ≥ 7 ...

Y. Matiyasevich and G. Senizergues. Decision problems for semi-Thue systems with a few rules, 11th Annual IEEE Symposium on Logic in Computer Science, 1996.

... and the following paper asserts that the issue is unsettled for 3 ≤ n ≤ 6:

Ling Zhao. Tackling Post's Correspondence Problem. Computers and Games 2002: 326-344.

— r.e.s. (talk) 14:21, 26 January 2010 (UTC)[reply]

Proof Sketch

Either I'm missing something or that proof cannot work. The second block pair, described as "copy block", makes the associated post correspondence problem trivially solvable (as any PCP with a word occuring in both word sets), which obviously says nothing about the turing machine output. — Preceding unsigned comment added by 79.243.26.202 (talk) 23:38, 9 August 2015 (UTC)[reply]

Proof Sketch

I'm echoing the concern of the previous comment. The proof seems to be wrong due to the "copy blocks" of the form (a, a), which make the problem have a trivial solution. Unfortunately it seems that the one who originally created that section has been banned. Rmkeller (talk) 01:16, 24 November 2016 (UTC)[reply]

Proof Sketch

This section needs to be completely rewritten. For the starting reader, this pair of sentences just introduces random symbols (q7, q2, q4....) without signifying how they are used. The rest is this section simply incomprehensible after that and a waste of time to read:

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. — Preceding unsigned comment added by 2601:645:C200:70D:D59E:8F4A:1C57:4B69 (talk) 09:11, 23 June 2019 (UTC)[reply]