| dbpprop:abstract
|
- 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.
- 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 <math>P</math> von Paaren <math>\left(\ldots,\right)</math> von nicht-leeren Wörtern <math>x_1, x_2, \ldots, x_m, y_1, y_2, \ldots, y_m</math> über einem endlichen Alphabet. Man nennt <math>P</math> auch einen Problemfall oder eine Instanz. Eine nicht-leere Folge <math>I = i_1, i_2, \ldots, i_n</math> von Indices aus <math>\{1, 2, \ldots, m\}</math> heißt eine Lösung zum Problemfall <math>P</math>, falls die Konkatenation (Verkettung) der Wörter <math>\left. {x_{i_1},x_{i_2},\ldots,x_{i_n}}\right. </math> gleich der Konkatenation der Wörter <math>\left. {y_{i_1},y_{i_2},\ldots,y_{i_n}}\right. </math> 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 einem beliebigen Problemfall die richtige Antwort gibt.
- Postův korespondenční problém (PCP) je nerozhodnutelný problém představený matematikem Emilem Postem v roce 1946. Problém je algoritmicky nerozhodnutelný. Redukce z PCP nebo jeho doplňku se používají k důkazům nerozhodnutelnosti.
- 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 indecibilidad. 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.
- Problem odpowiedniości Posta (Post correspondence problem, w skrócie PCP) - jest to przykład nierozstrzygalnego problemu decyzyjnego, czyli takiego, dla którego nie istnieje program komputerowy, czy też algorytm go rozwiązujący. Został on przedstawiony przez Emila Leona Posta w 1946 roku.
|
| rdfs:comment
|
- 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.
- 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.
- Postův korespondenční problém (PCP) je nerozhodnutelný problém představený matematikem Emilem Postem v roce 1946. Problém je algoritmicky nerozhodnutelný. Redukce z PCP nebo jeho doplňku se používají k důkazům nerozhodnutelnosti.
- 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 indecibilidad. 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.
- Problem odpowiedniości Posta (Post correspondence problem, w skrócie PCP) - jest to przykład nierozstrzygalnego problemu decyzyjnego, czyli takiego, dla którego nie istnieje program komputerowy, czy też algorytm go rozwiązujący. Został on przedstawiony przez Emila Leona Posta w 1946 roku.
|
![[RDF Data]](/statics/sw-cube.png)
