On the Complexity of the Bi-infinite Post Correspondence Problem
Dit artikel stelt vast dat het bi-oneindige Post Correspondence Problem (PCP) -compleet is binnen de arithmetische hiërarchie door een keten van reducties vanaf het niet-halten van Turingmachines te presenteren en de -compleetheid van verschillende gerelateerde oneindige en verschoven varianten te bewijzen.