| 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
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 25211 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:align
| |
| dbp:gap
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| 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
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is owl:differentFrom
of | |
| is foaf:primaryTopic
of | |
