Post correspondence problem
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.
known for
Wikipage disambiguates
Ambiguous grammarBounded PCPBounded Post correspondence problemBounded post correspondence problemCombinatorics on wordsContext-free grammarDouble pushout graph rewritingEmil Leon PostGeneric-case complexityGéraud SénizerguesIndex of philosophy articles (I–Q)LL grammarList of NP-complete problemsList of computability and complexity topicsList of mathematical logic topicsList of pioneers in computer scienceList of terms relating to algorithms and data structuresList of undecidable problemsMarked PCPMarked Post Correspondence ProblemOutline of logicPCPPost's correspondence problemPost correspondance problemProof of impossibilityRE (complexity)Recursively enumerable language
Link from a Wikipage to another Wikipage
known for
differentFrom
primaryTopic
Post correspondence problem
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.
has abstract
Das Postsche Korrespondenzprob ...... all die richtige Antwort gibt.
@de
El Problema de Correspondencia ...... a lo mismo en ambos lenguajes.
@es
En mathématiques et en informa ...... esquelles ?] d'indécidabilité.
@fr
Het correspondentieprobleem va ...... zijn (Engelse) afkorting: PCP.
@nl
O problema da correspondência ...... em provas de indecidibilidade.
@pt
Postův korespondenční problém ...... k důkazům nerozhodnutelnosti.
@cs
Problem odpowiedniości Posta ( ...... Emila Leona Posta w 1946 roku.
@pl
The Post correspondence proble ...... d in proofs of undecidability.
@en
Проблема збіжності Поста — Вив ...... при цьому належного уточнення.
@uk
波斯特对应问题(英語:Post correspondence problem)是美国数学家(Emil Post)于1946年提出的一个不可判定问题。
@zh
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,022,576,980
Link from a Wikipage to another Wikipage
align
center
@en
wikiPageUsesTemplate
hypernym
comment
Das Postsche Korrespondenzprob ...... Konkatenation der Wörter ist.
@de
El Problema de Correspondencia ...... a lo mismo en ambos lenguajes.
@es
En mathématiques et en informa ...... esquelles ?] d'indécidabilité.
@fr
Het correspondentieprobleem va ...... zijn (Engelse) afkorting: PCP.
@nl
O problema da correspondência ...... em provas de indecidibilidade.
@pt
Postův korespondenční problém ...... k důkazům nerozhodnutelnosti.
@cs
Problem odpowiedniości Posta ( ...... Emila Leona Posta w 1946 roku.
@pl
The Post correspondence proble ...... d in proofs of undecidability.
@en
Проблема збіжності Поста — Вив ...... ональних» великих кількостей).
@uk
波斯特对应问题(英語:Post correspondence problem)是美国数学家(Emil Post)于1946年提出的一个不可判定问题。
@zh
label
Correspondentieprobleem van Post
@nl
Post correspondence problem
@en
Postsches Korrespondenzproblem
@de
Postův korespondenční problém
@cs
Problem odpowiedniości Posta
@pl
Problema da correspondência de Post
@pt
Problema de correspondencia de Post
@es
Problème de correspondance de Post
@fr
Проблема збіжності Поста
@uk
波斯特对应问题
@zh