The Cook-Berger problem -A guide to the solution
Dag Normann · Electronic Notes in Theoretical Computer Science · 2000
We show that to any computable, total functional Φ of pure type 3, there is a total PCP-definable functional . We discuss how the program for can be viewed as the result of replacing non-deterministic constants in Plotkin's program for Φ by deterministic procedures.