Decidable tree for binary diagonal avoidance

ID: decidable-tree-for-binary-diagonal-avoidance

For an effective enumeration of unary partial computable functions, admit a length- string if it disagrees with every binary value of observed within steps for . The bounded halting predicate makes membership decidable, and the tests are prefix compatible. Its paths are exactly the binary diagonally noncomputable functions. The path space is nonempty and perfect because infinitely many indices of divergent programs leave arbitrarily late bits free; no path is computable. Dead ends in this decidable presentation are essential.

New to topics? Read the docs here!