Post correspondence problem (original) (raw)
Postův korespondenční problém (PCP) je nerozhodnutelný problém představený matematikem Emilem Postem v roce 1946. Problém je algoritmicky nerozhodnutelný. z PCP nebo jeho doplňku se používají k důkazům nerozhodnutelnosti.
| Property | Value |
|---|---|
| dbo:abstract | Postův korespondenční problém (PCP) je nerozhodnutelný problém představený matematikem Emilem Postem v roce 1946. Problém je algoritmicky nerozhodnutelný. z PCP nebo jeho doplňku se používají k důkazům nerozhodnutelnosti. (cs) Das Postsche Korrespondenzproblem (nach Emil Leon Post, abgekürzt auch PKP oder englisch PCP) ist ein Beispiel für ein unentscheidbares Problem in der Theoretischen Informatik.Es wird häufig verwendet, um mittels Reduktion die Unentscheidbarkeit anderer Probleme zu zeigen. Gegeben ist eine endliche Folge von Paaren von nicht-leeren Wörtern über einem endlichen Alphabet. Man nennt auch einen Problemfall oder eine Instanz. Eine nicht-leere Folge von Indizes aus heißt eine Lösung zum Problemfall , falls die Konkatenation (Verkettung) der Wörter gleich der Konkatenation der Wörter ist. Das Korrespondenzproblem ist dann die Aufgabe, zu einem beliebigen Problemfall anzugeben, ob er eine Lösung besitzt oder nicht. Das Korrespondenzproblem ist unentscheidbar, das heißt, es gibt keinen Algorithmus, der zu jedem beliebigen Problemfall die richtige Antwort gibt. (de) El Problema de Correspondencia de Post es un problema de decisión indecidible que fue propuesto por Emil Post. Por ser más sencillo que el Problema de parada y que el Entscheidungsproblem, resulta útil para realizar pruebas de indecidilidad. Informalmente, el problema puede ser descrito como sigue: Dado un diccionario bilingüe que contiene pares de frases, es decir, listas de palabras, que significan lo mismo, decidir si existe una frase que significa lo mismo en ambos lenguajes. (es) 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. (en) En mathématiques et en informatique théorique, et plus précisément en théorie de la calculabilité, le problème de correspondance de Post (PCP) est un problème de décision indécidable qui fut introduit par Emil Post en 1946. Comme il est plus simple que le problème de l'arrêt et que le problème de la décision, il apparaît souvent dans des démonstrations d'indécidabilité, comme celle de l'ambiguïté d'une grammaire. (fr) Het correspondentieprobleem van Post (Engels: Post Correspondence Problem) is een onbeslisbaar probleem uit de theoretische informatica dat in 1946 door Emil Leon Post werd geformuleerd. Het wordt vaak gebruikt om de onbeslisbaarheid van andere problemen te bewijzen. Het probleem is ook bekend onder zijn (Engelse) afkorting: PCP. (nl) Problem odpowiedniości Posta (ang. Post correspondence problem, PCP) – przykład nierozstrzygalnego problemu decyzyjnego. Został on przedstawiony przez Emila Leona Posta w 1946 roku. (pl) O problema da correspondência de Post é um problema de decisão que foi introduzido por Emil Post em 1946.. PCP é mais simples que o problema da parada e o Entscheidungsproblem por isso ele é frequentemente usado em provas de indecidibilidade. (pt) 波斯特对应问题（英語：Post correspondence problem）是美国数学家（Emil Post）于1946年提出的一个不可判定问题。 (zh) Проблема збіжності Поста — Вивчаючи нерозв'язні породжуючі множини, що виникають в математичній практиці, можна було виявити, що їх проблеми розв'язку в деякому розумінні зводяться один до одного. Підкреслимо, що йдеться не про усі нерозв'язні породжуючі множини, а лише про ті, що історично виникли(включаючи всілякі конкретні приклади «діагональних» великих кількостей). В силу сказаного нерозв'язність проблеми розв'язку для будь-якої такої множини можна звести до нерозв'язності «еталонної» проблеми розв'язку для якої-небудь з діагональних множин; саме таке зведення — в прямій або непрямій формі — здійснювалося і продовжує здійснюватися в математичній літературі. Встає природна проблема — чи носить це явище універсальний характер, тобто чи дійсно усі проблеми розв'язку для усіх нерозв'язних множин, що перераховують, збіжні один до одного; зрозуміло, слово «збіжні» потребує при цьому належного уточнення. (uk) |
| dbo:wikiPageExternalLink | http://jamesvanboxtel.com/projects/pcp-solver/ http://webdocs.cs.ualberta.ca/~games/PCP/ https://www.interviewbit.com/blog/post-correspondence-problem/ http://www.atlantis-press.com/php/download_paper.php%3Fid=3059 https://github.com/dcatteeu/PCPSolver https://web.archive.org/web/20050214072238/http:/www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fourse7.html https://web.archive.org/web/20090309162234/http:/www.theory.informatik.uni-kassel.de/~stamer/pcp/pcpcontest_en.html |
| dbo:wikiPageID | 64685 (xsd:integer) |
| dbo:wikiPageLength | 25211 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1111533163 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Entscheidungsproblem dbr:Decision_problem dbr:NP-complete dbr:Computation_history dbc:Undecidable_problems dbr:EXPTIME dbr:Halting_problem dbc:Computability_theory dbc:Theory_of_computation dbr:Chomsky_hierarchy dbr:Monoid_morphism dbr:Boolean_satisfiability_problem dbr:Michael_Sipser dbr:Sequence dbr:Turing_machine dbr:Undecidable_problem dbr:Substring dbr:Turing_degree dbr:Emil_Post dbr:Finite_state_machine dbr:Conjugacy |
| dbp:align | center (en) |
| dbp:gap | 5 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Col-begin dbt:Col-break dbt:Col-end dbt:Distinguish dbt:Reflist |
| dct:subject | dbc:Undecidable_problems dbc:Computability_theory dbc:Theory_of_computation |
| gold:hypernym | dbr:Problem |
| rdf:type | owl:Thing dbo:Disease |
| rdfs:comment | Postův korespondenční problém (PCP) je nerozhodnutelný problém představený matematikem Emilem Postem v roce 1946. Problém je algoritmicky nerozhodnutelný. z PCP nebo jeho doplňku se používají k důkazům nerozhodnutelnosti. (cs) El Problema de Correspondencia de Post es un problema de decisión indecidible que fue propuesto por Emil Post. Por ser más sencillo que el Problema de parada y que el Entscheidungsproblem, resulta útil para realizar pruebas de indecidilidad. Informalmente, el problema puede ser descrito como sigue: Dado un diccionario bilingüe que contiene pares de frases, es decir, listas de palabras, que significan lo mismo, decidir si existe una frase que significa lo mismo en ambos lenguajes. (es) 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. (en) En mathématiques et en informatique théorique, et plus précisément en théorie de la calculabilité, le problème de correspondance de Post (PCP) est un problème de décision indécidable qui fut introduit par Emil Post en 1946. Comme il est plus simple que le problème de l'arrêt et que le problème de la décision, il apparaît souvent dans des démonstrations d'indécidabilité, comme celle de l'ambiguïté d'une grammaire. (fr) Het correspondentieprobleem van Post (Engels: Post Correspondence Problem) is een onbeslisbaar probleem uit de theoretische informatica dat in 1946 door Emil Leon Post werd geformuleerd. Het wordt vaak gebruikt om de onbeslisbaarheid van andere problemen te bewijzen. Het probleem is ook bekend onder zijn (Engelse) afkorting: PCP. (nl) Problem odpowiedniości Posta (ang. Post correspondence problem, PCP) – przykład nierozstrzygalnego problemu decyzyjnego. Został on przedstawiony przez Emila Leona Posta w 1946 roku. (pl) O problema da correspondência de Post é um problema de decisão que foi introduzido por Emil Post em 1946.. PCP é mais simples que o problema da parada e o Entscheidungsproblem por isso ele é frequentemente usado em provas de indecidibilidade. (pt) 波斯特对应问题（英語：Post correspondence problem）是美国数学家（Emil Post）于1946年提出的一个不可判定问题。 (zh) Das Postsche Korrespondenzproblem (nach Emil Leon Post, abgekürzt auch PKP oder englisch PCP) ist ein Beispiel für ein unentscheidbares Problem in der Theoretischen Informatik.Es wird häufig verwendet, um mittels Reduktion die Unentscheidbarkeit anderer Probleme zu zeigen. Gegeben ist eine endliche Folge von Paaren von nicht-leeren Wörtern über einem endlichen Alphabet. Man nennt auch einen Problemfall oder eine Instanz. Eine nicht-leere Folge von Indizes aus heißt eine Lösung zum Problemfall , falls die Konkatenation (Verkettung) der Wörter gleich der Konkatenation der Wörter ist. (de) Проблема збіжності Поста — Вивчаючи нерозв'язні породжуючі множини, що виникають в математичній практиці, можна було виявити, що їх проблеми розв'язку в деякому розумінні зводяться один до одного. Підкреслимо, що йдеться не про усі нерозв'язні породжуючі множини, а лише про ті, що історично виникли(включаючи всілякі конкретні приклади «діагональних» великих кількостей). (uk) |
| rdfs:label | Postův korespondenční problém (cs) Postsches Korrespondenzproblem (de) Problema de correspondencia de Post (es) Problème de correspondance de Post (fr) Post correspondence problem (en) Problem odpowiedniości Posta (pl) Correspondentieprobleem van Post (nl) Problema da correspondência de Post (pt) 波斯特对应问题 (zh) Проблема збіжності Поста (uk) |
| owl:differentFrom | dbr:PCP_theorem |
| owl:sameAs | freebase:Post correspondence problem yago-res:Post correspondence problem wikidata:Post correspondence problem dbpedia-cs:Post correspondence problem dbpedia-de:Post correspondence problem dbpedia-es:Post correspondence problem dbpedia-fa:Post correspondence problem dbpedia-fr:Post correspondence problem dbpedia-he:Post correspondence problem dbpedia-is:Post correspondence problem dbpedia-nl:Post correspondence problem dbpedia-nn:Post correspondence problem dbpedia-no:Post correspondence problem dbpedia-pl:Post correspondence problem dbpedia-pt:Post correspondence problem dbpedia-tr:Post correspondence problem dbpedia-uk:Post correspondence problem dbpedia-zh:Post correspondence problem https://global.dbpedia.org/id/4xScg |
| prov:wasDerivedFrom | wikipedia-en:Post_correspondence_problem?oldid=1111533163&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Post_correspondence_problem |
| is dbo:knownFor of | dbr:Emil_Leon_Post |
| is dbo:wikiPageDisambiguates of | dbr:PCP |
| is dbo:wikiPageRedirects of | dbr:Marked_PCP dbr:Marked_Post_Correspondence_Problem dbr:Post's_correspondence_problem dbr:Post_correspondance_problem dbr:Bounded_PCP dbr:Bounded_Post_correspondence_problem dbr:Bounded_post_correspondence_problem |
| is dbo:wikiPageWikiLink of | dbr:Proof_of_impossibility dbr:List_of_computability_and_complexity_topics dbr:List_of_pioneers_in_computer_science dbr:Double_pushout_graph_rewriting dbr:Index_of_philosophy_articles_(I–Q) dbr:List_of_mathematical_logic_topics dbr:Context-free_grammar dbr:Generic-case_complexity dbr:Emil_Leon_Post dbr:LL_grammar dbr:Combinatorics_on_words dbr:PCP dbr:Recursively_enumerable_language dbr:Ambiguous_grammar dbr:List_of_NP-complete_problems dbr:RE_(complexity) dbr:Géraud_Sénizergues dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_undecidable_problems dbr:Outline_of_logic dbr:Marked_PCP dbr:Marked_Post_Correspondence_Problem dbr:Post's_correspondence_problem dbr:Post_correspondance_problem dbr:Bounded_PCP dbr:Bounded_Post_correspondence_problem dbr:Bounded_post_correspondence_problem |
| is dbp:knownFor of | dbr:Emil_Leon_Post |
| is owl:differentFrom of | dbr:PCP_theorem |
| is foaf:primaryTopic of | wikipedia-en:Post_correspondence_problem |