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?

  • $\begingroup$ If you are familiar with the arithmetical hierarchy it shouldn't be to hard to find an example. I am pretty sure that solutions to the halting problem are always pi_1, and then any formula above is an example. $\endgroup$ – sss89 Jan 4 '16 at 11:40
  • $\begingroup$ Definable in what sense? $0^\#$ (<--- link) is not definable in any usual sense, and is highly non-computable but is hardly "random junk". $\endgroup$ – BrianO Jan 4 '16 at 18:13
  • $\begingroup$ @Brian: I disagree. $0^\#$ is definable in a very usual sense. It's the "informal" sense of definable that makes no sense. And if I recall correctly $0'$ is computable from $0^\#$. So it doesn't fit the "random junk" part. $\endgroup$ – Asaf Karagila Jan 4 '16 at 18:32
  • $\begingroup$ @Asaf I presumed that "definable" (with parameters) means "definable in some theory and guaranteed to exist by that theory". So, yes, $0^\#$ is definable, $\Delta^1_3$ even, if it exists -- equivalently, if $\operatorname{Det} \Sigma^1_1$ (lightface). I think you recall correctly that $0' \le_T 0^\#$, in fact iirc the hyperjump should be computable from it. None of these are 'random junk' ;) $\endgroup$ – BrianO Jan 4 '16 at 19:42
  • $\begingroup$ @Brian: You mean $\Sigma^1_1$ determinacy... :-) $\endgroup$ – Asaf Karagila Jan 4 '16 at 19:51

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.

  • $\begingroup$ Big-picture version: take $X$ "generic but not too generic" - for instance, $134$-generic but computable in $0^{(12389)}$. Then $X$ will not have halting information, but will be noncomputable, and definable. And we could replace "generic" with "random" here, or indeed generic for any reasonably nice forcing notion (note that "generic" is used as shorthand for "Cohen generic" in computability theory - a convention of which I'm not much of a fan . . .). $\endgroup$ – Noah Schweber Jan 5 '16 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy