Talk:Post correspondence problem
From Wikipedia, the free encyclopedia
[edit] 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)
[edit] 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.—The preceding unsigned comment was 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)
- 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)
[edit] 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)
