On the Complexity of the Bi-infinite Post Correspondence Problem
Questo articolo stabilisce che il Problema della Corrispondenza Post bi-infinito (PCP) è -completo all'interno della gerarchia aritmetica presentando una catena di riduzioni dal non-arresto di macchine di Turing e dimostrando la -completezza di diverse varianti infinite e traslate correlate.