Definable non-computable number which contain no information

Question

We have three types of numbers AFAIK: a) Computable b) Definable and non-computable, but contains information about Halting of some turing machines, extractable in a computable way if you were given the number c) Non-computable random junk, which are most numbers

Non-computable numbers that we can define seem all to be some function of the solution set of the halting problem.

Is there a definable number in c) ? Ie is there a number we can define and which is not computable and knowledge of it would not give us any more information about halting of some turing machines or probabilities thereof?

Can we define any of these random junk numbers which contain no information and which constitute the majority of numbers?

Answer 1

It's a little unclear exactly what you mean by "contains information about Halting of some turing machines", but under every reasonable interpretation of this I can think of the answer is "yes."

For instance, consider the following:

Definition. A set $X$ has halting information if there is some computable set $C$ of (indices for) Turing machines such that: $(i)$ the set $\{i\in C: \Phi_i(i)\downarrow\}$ is not computable, but $(ii)$ the set $\{i\in C: \Phi_i(i)\downarrow\}$ is computable from $X$.

Here I use "$\downarrow$" to denote "halts."

Then we have:

Fact. There are noncomputable sets which do not have halting information. Moreover, there are such sets which are arithmetic - that is, definable in first-order arithmetic.

Proof: Note that $\{i\in C: \Phi_i(i)\downarrow\}=K\cap C$, where $K$ is the Halting Problem. So it's enough to build an $X$ such that for every computable $C$, either $K\cap C$ is computable or $K\cap C\not\le_TX$. Specifically, we have countably many sets $A_i$ (the sets of the form $K\cap C$ which are non-computable) and we want a noncomputable $X$ which does not compute any $A_i$. Such an $X$ can be built by diagonalization. It's now an easy exercise to show that this construction can be performed computably in, say, $0''''$ (actually much lower, but no need to go that far) - show that $0''''$ can compute a listing of the $A_i$s, and moreover can compute the necessary diagonalization process. But every set computable in $0''''$ is definable in first-order arithmetic (specifically, $\Delta^0_5$), so we're done.