Post correspondence problem

undecidable decision problem
Thing Decision Problem Q798572

Facts

7 properties
Instance of
decision problem
Computational complexity
RE[6]
Defining formula
\alpha _{i_1}\dotsm \alpha _{i_K}=\beta _{i_1}\dotsm \beta _{i_K}\qquad(\alpha_1,\dotsc,\alpha_N,\beta_1,\dotsc,\beta_N\in\Sigma^*)
Different from
phencyclidine[4]
Discoverer or inventor
Emil Leon Post[1]
Time of discovery or invention
1946[3]
🏷️ Also known as
en Post correspondence problem en Post's correspondence problem cs Postův korespondenční problém de Post correspondence problem de Postsches Korrespondenzproblem de Post'sches Korrespondenzproblem de PCP de PKP es problema de correspondencia de Post fa مسئله تناظر پست fr Problème de correspondance de Post he בעיית ההתאמה של פוסט nl Correspondentieprobleem van Post nl Post Correspondence Problem pl Problem odpowiedniości Posta pt Problema da correspondência de Post tr Post Correspondence Problemi uk Проблема збіжності Поста zh 波斯特对应问题
🔖 Identifiers · 4
Dictionary of Algorithms and Data Structures ID
pcp
Freebase ID
/m/0h7t4
Microsoft Academic ID (discontinued)
123609886

Report an error or request removal Lineage (PROV-JSON)

🔗 Connections
Computational complexity 1
RE
Created notable works 1
Different from 1
Discoverer or inventor 1
Instance of 1
Maintained by WikiProject 1
Named after 1
Press Enter · cited answer in seconds

📑 Cite this page

Use these citations when quoting this entity in research, articles, AI prompts, or wherever provenance matters. We aggregate Wikidata + Wikipedia + authoritative open-data sources; the stitched, scored, cross-referenced view is what 4ort.xyz contributes.

APA 4ort.xyz Knowledge Graph. (2026). Post correspondence problem. Retrieved November 17, 2026, from https://4ort.xyz/entity/post-correspondence-problem
MLA “Post correspondence problem.” 4ort.xyz Knowledge Graph, 4ort.xyz, 17 Nov. 2026, https://4ort.xyz/entity/post-correspondence-problem.
BibTeX @misc{4ortxyz_post-correspondence-problem_2026, author = {{4ort.xyz Knowledge Graph}}, title = {{Post correspondence problem}}, year = {2026}, url = {https://4ort.xyz/entity/post-correspondence-problem}, note = {Accessed: 2026-11-17}}
LLM prompt According to 4ort.xyz Knowledge Graph (aggregator of Wikidata, Wikipedia, and authoritative open-data sources): Post correspondence problem — https://4ort.xyz/entity/post-correspondence-problem (retrieved 2026-11-17)

Canonical URL: https://4ort.xyz/entity/post-correspondence-problem · Last refreshed:

Edit History

Rolling log of changes to this entity's Wikidata record. Values shown reflect the current state of each edited property — follow the history link to see the precise diff for any edit.

  1. 1d ago · ValRai89 · 2026-11-17 view diff on Wikidata ↗
    Maintained by WikiProject → WikiProject Mathematics
    Different from → phencyclidine
    Instance of → decision problem
    Discoverer or inventor → Emil Leon Post
    + 2 other properties edited (see Wikidata diff for full list)
    "Added [fr] description: problème de décision indécidable qui fut introduit par Emil Post en 1946"
Live feed via Wikidata EventStreams. New edits appear within minutes of being made on Wikidata.