Approximations to the halting problem

摘要

The halting set Kφ={x|φx(x) converges}, for any Gödel numbering φ={φ0, φ1,…}, is nonrecursive. It may be possible, however, to approximate Kφ by recursive sets. We note several results indicating that the degrees of recursive approximability of halting sets in arbitrary Gödel numberings have wide variation, while restriction to “optimal Gödel numberings” only narrows the possibilities slightly.