Problema da correspondência de Post
De Wikipedia, a enciclopédia encyclopedia
O problema da correspondência de Post é um problema de decisão indecidível que foi introduzido por Emil Post em 1946..[1] PCP é mais simples que o problema da parada e o Entscheidungsproblem por isso ele é frequentemente usado em provas de indecidibilidade.