Post correspondence problem
http://dbpedia.org/resource/Post_correspondence_problem an entity of type: Thing
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
Problem odpowiedniości Posta (ang. Post correspondence problem, PCP) – przykład nierozstrzygalnego problemu decyzyjnego. Został on przedstawiony przez Emila Leona Posta w 1946 roku.
rdf:langString
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.
rdf:langString
波斯特对应问题（英語：Post correspondence problem）是美国数学家（Emil Post）于1946年提出的一个不可判定问题。
rdf:langString
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.
rdf:langString
Проблема збіжності Поста — Вивчаючи нерозв'язні породжуючі множини, що виникають в математичній практиці, можна було виявити, що їх проблеми розв'язку в деякому розумінні зводяться один до одного. Підкреслимо, що йдеться не про усі нерозв'язні породжуючі множини, а лише про ті, що історично виникли(включаючи всілякі конкретні приклади «діагональних» великих кількостей).
rdf:langString
rdf:langString
Postův korespondenční problém
rdf:langString
Postsches Korrespondenzproblem
rdf:langString
Problema de correspondencia de Post
rdf:langString
Problème de correspondance de Post
rdf:langString
Post correspondence problem
rdf:langString
Problem odpowiedniości Posta
rdf:langString
Correspondentieprobleem van Post
rdf:langString
Problema da correspondência de Post
rdf:langString
波斯特对应问题
rdf:langString
Проблема збіжності Поста
xsd:integer
64685
xsd:integer
1111533163
rdf:langString
center
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
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.
rdf:langString
Problem odpowiedniości Posta (ang. Post correspondence problem, PCP) – przykład nierozstrzygalnego problemu decyzyjnego. Został on przedstawiony przez Emila Leona Posta w 1946 roku.
rdf:langString
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.
rdf:langString
波斯特对应问题（英語：Post correspondence problem）是美国数学家（Emil Post）于1946年提出的一个不可判定问题。
rdf:langString
Проблема збіжності Поста — Вивчаючи нерозв'язні породжуючі множини, що виникають в математичній практиці, можна було виявити, що їх проблеми розв'язку в деякому розумінні зводяться один до одного. Підкреслимо, що йдеться не про усі нерозв'язні породжуючі множини, а лише про ті, що історично виникли(включаючи всілякі конкретні приклади «діагональних» великих кількостей). В силу сказаного нерозв'язність проблеми розв'язку для будь-якої такої множини можна звести до нерозв'язності «еталонної» проблеми розв'язку для якої-небудь з діагональних множин; саме таке зведення — в прямій або непрямій формі — здійснювалося і продовжує здійснюватися в математичній літературі. Встає природна проблема — чи носить це явище універсальний характер, тобто чи дійсно усі проблеми розв'язку для усіх нерозв'язних множин, що перераховують, збіжні один до одного; зрозуміло, слово «збіжні» потребує при цьому належного уточнення.
xsd:integer
5
xsd:nonNegativeInteger
25211