Editing Post correspondence problem (section)

{{short description|Undecidable decision problem introduced by Emil Post}}
{{distinguish|text=the [[Turing degree#Post's problem and the priority method|other Post's problem]] on the existence of incomparable r.e. Turing degrees}}
{{distinguish | PCP theorem}}

The '''Post correspondence problem''' is an [[undecidable problem|undecidable]] [[decision problem]] that was introduced by [[Emil Post]] in 1946.<ref name="Post46">{{cite journal|year = 1946|author = E. L. Post|author-link = Emil Post| title= A variant of a recursively unsolvable problem |journal = [[Bull. Amer. Math. Soc.]]| volume =  52|issue = 4|url=https://www.ams.org/bull/1946-52-04/S0002-9904-1946-08555-9/S0002-9904-1946-08555-9.pdf|doi=10.1090/s0002-9904-1946-08555-9|pages=264–269| s2cid=122948861 }}</ref> Because it is simpler than the [[halting problem]] and the ''[[Entscheidungsproblem]]'' it is often used in proofs of undecidability.