PCP
Posts Correspondence Problem
Definition
Das Posts Correspondence Problem ist ein bekanntes unentscheidbares Problem in der theoretischen Informatik. Es fragt, ob aus gegebenen Wortpaaren eine Folge gebildet werden kann, bei der die Konkatenation der oberen und unteren Wörter übereinstimmt.