Suppose we knew the answer to the halting problem, and the halting problem for this new system with the old halting problem solved. And so on. Would this allow us to compute every definable number?
4
-
2$\begingroup$ When you say definable number, do you mean a subset of natural numbers definable in the first-order structure $(\mathbb{N},0,1,*,+)$? (This is the interpretation that made most sense to me in connection with the halting problem.) Saying "definable number" by itself is pretty dangerous as shown here. $\endgroup$– BurakJan 4, 2016 at 10:23
-
$\begingroup$ Wikipedia definition en.wikipedia.org/wiki/Definable_real_number $\endgroup$– T45665Jan 4, 2016 at 10:24
-
5$\begingroup$ You should check out this answer by Joel Hamkins that explains why the Wikipedia article does not make sense. $\endgroup$– BurakJan 4, 2016 at 10:27
-
$\begingroup$ OK. I am still interested in an answer to my question under any reasonable definition of definable. $\endgroup$– T45665Jan 4, 2016 at 10:40
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Depending on exactly what you mean by "and so on" (continue through the finite? the computable infinite?), you've described either the arithmetic or the hyperarithmetic sets of natural numbers. The former correspond to those sets which are first-order definable in the structure $(\mathbb{N}; +, \times)$; the latter, to those sets which are definable by a computable infinitary first-order formula in the structure $(\mathbb{N}; +, \times)$.
But these certainly aren't the only kinds of definability out there. We could consider other logics (non-computable infinitary first order? second-order? etc.) or other structures (first-order definability in the set-theoretic universe is extremely powerful); each provides a way to leap well outside even the hyperarithmetic sets.
The bottom line is: what do you mean by "definable"? Definability only makes sense once we specify both
- a structure,
and
- a logic;
and the precise answer to your question will vary wildly depending what you mean.
If you want to continue your process past the computable infinite, you run into trouble. Let $\omega_1^{CK}$ be the least noncomputable ordinal: what is the "$\omega_1^{CK}$th Halting Problem?" Unlike, say, the first infinite ordinal $\omega$ - where "the $\omega$th Halting Problem" $0^{(\omega)}$ is quite reasonably defined as $$\{\langle m, n\rangle: m\in 0^{(n)}\},$$ and in fact we can prove that any other reasonable way of "stitching together" the first $\omega$-many halting problems yields the same Turing degree - the fact that $\omega_1^{CK}$ is not computable prevents any nice definition. There are ways we can get past this, but that's a bit of a digression.
answered Jan 4, 2016 at 12:45
$\begingroup$
$\endgroup$
1
No.
For any model of computation; the set of computable reals is countable.
Through cantors diagnolisation argument we can prove the existence of a real which is not in this countably infinite set : --- simultaneously defining it and proving it's incomputability in the chosen model.
eg. If for computation (even if) we have a Universal Turing Machine with the access to the n- th oracle; the set of all programs which halt on it;
is in-computable on the same setup : But the set is definable.(this being the definition)
-
$\begingroup$ Of course, this depends on the definition of "definable." E.g. if "definable" means "first-order definable in $(\mathbb{N}; +, \times)$," then the answer is "yes". $\endgroup$ Jan 4, 2016 at 19:56