<p>This might be cheating, because I am reinterpreting your notion of "number" as "countable ordinal."  However, there is an extensive theory about exactly what you are asking about in your question -- which ordinals can be defined, with which definition-strengths.  I looked at Wikipedia, and the <a href="http://en.wikipedia.org/wiki/Large_countable_ordinal" rel="nofollow">large countable ordinal</a> page has a lot of information.  In particular, the "smallest number that is interesting because the system can't even prove it's a number" corresponds to the <a href="http://en.wikipedia.org/wiki/Large_countable_ordinal#.E2.80.9CUnrecursable.E2.80.9D_recursive_ordinals" rel="nofollow">unrecursable ordinals</a>, if we require nothing other than computability as the resource bound.</p>

CC BY-SA 2.5
2010-10-29T14:53:25.373Z
If you want to limit things to the naturals, you might need to talk about functions from the naturals to the naturals, instead of just individual numbers.  My favorite weird-result paper is [one that explicitly calulated the first 64 bits of the uncomputable Chaitin's Omega](http://www.expmath.org/expmath/volumes/11/11.3/Calude361_370.pdf).  Finite prefixes of uncomputable functions can be computed in polynomial time.
Aaron Sterling
CC BY-SA 2.5
2010-10-29T14:38:33.107Z
2010-10-29T14:38:33.107Z
Aaron Sterling
<p>There is an old joke about the smallest non-interesting number being interesting in itself (I have heard it attributed to Richard Hamming).  This is then used to justify the argument that every number must be interesting.  I have always found this induction unsatisfactory.</p>

<p>Here is an attempt at a more precise argument.  Consider a set of rules, represented as sentences of some logic.  The interesting numbers are then the smallest numbers that are models of some set of sentences.  In first-order logic each natural number can be distinguished from every other one, so the sentences true for any natural number will differ from those true for any other, and every number will be interesting.</p>

<p>Now suppose our rules are given in terms of a bounded model of computation, so that only finite sets of properties can be associated with each number, and so that every property can be checked with a bounded amount of some resource (for instance, time or space).</p>

<blockquote>
  <p>Is every number still interesting with resource-bounded properties?</p>
</blockquote>

<p><em>Edit:</em> to clarify, resource bounds is my focus here.  With unbounded resources this devolves into a question about definability and large ordinals, as discussed by Aaron and Kaveh.  The idea is that each interesting number should be definable by a sentence that can be checked given a bounded amount of resources.  (It might also make sense to allow some finite set of sentences as separate building blocks instead of making them into single sentences via conjunction.)</p>

CC BY-SA 2.5
2010-10-28T17:57:25.127Z
IMHO, this is not a soft-question. You are essentially talking about what is called definable elements in logic/model theory. Every element in $N$ is definable, using a single sentence $x=\bar{n}$, where $\bar{n}$ is the term resulting applying $s$ (successor function) $n$-times to $0$.
Kaveh
CC BY-SA 2.5
2010-10-28T22:37:58.540Z
I think the old joke gets formalized into a statement that essentially gives the opposite conclusion: namely, most numbers are Kolmogorov-random.  (But "interesting" numbers "should" be highly compressible.)
Joshua Grochow
CC BY-SA 2.5
2010-10-29T04:01:22.707Z
Theorem: All positive integers are boring. Proof by contradiction: Let $n$ be the smallest interesting positive integer. So what?
Jeffε
CC BY-SA 2.5
2010-10-29T22:01:32.660Z
How about defining the interesting numbers as those which has short description, i.e. small Kolmogorov complexity? Then most numbers will be uninteresting (random).
Kaveh
<cc.complexity-theory><lo.logic><descriptive-complexity>
Non-interesting numbers via resource-bounded properties?
András Salamon
# Non-interesting numbers via resource-bounded properties?

(Asked by: username_0 on 2010-10-28)

There is an old joke about the smallest non-interesting number being interesting in itself (I have heard it attributed to Richard Hamming). This is then used to justify the argument that every number must be interesting. I have always found this induction unsatisfactory.

Here is an attempt at a more precise argument. Consider a set of rules, represented as sentences of some logic. The interesting numbers are then the smallest numbers that are models of some set of sentences. In first-order logic each natural number can be distinguished from every other one, so the sentences true for any natural number will differ from those true for any other, and every number will be interesting.

Now suppose our rules are given in terms of a bounded model of computation, so that only finite sets of properties can be associated with each number, and so that every property can be checked with a bounded amount of some resource (for instance, time or space).

> Is every number still interesting with resource-bounded properties?

*Edit:* to clarify, resource bounds is my focus here. With unbounded resources this devolves into a question about definability and large ordinals, as discussed by Aaron and Kaveh. The idea is that each interesting number should be definable by a sentence that can be checked given a bounded amount of resources. (It might also make sense to allow some finite set of sentences as separate building blocks instead of making them into single sentences via conjunction.)

**Tags:** cc.complexity-theory, lo.logic, descriptive-complexity
> **Comments:**
> **username_1**: IMHO, this is not a soft-question. You are essentially talking about what is called definable elements in logic/model theory. Every element in $N$ is definable, using a single sentence $x=\bar{n}$, where $\bar{n}$ is the term resulting applying $s$ (successor function) $n$-times to $0$.  
> **username_2**: I think the old joke gets formalized into a statement that essentially gives the opposite conclusion: namely, most numbers are Kolmogorov-random.  (But "interesting" numbers "should" be highly compressible.)  
> **username_3**: Theorem: All positive integers are boring. Proof by contradiction: Let $n$ be the smallest interesting positive integer. So what?  
> **username_1**: How about defining the interesting numbers as those which has short description, i.e. small Kolmogorov complexity? Then most numbers will be uninteresting (random).  

---

## 1 answers

### Answer by username_4 on 2010-10-29. Score: 3

This might be cheating, because I am reinterpreting your notion of "number" as "countable ordinal." However, there is an extensive theory about exactly what you are asking about in your question -- which ordinals can be defined, with which definition-strengths. I looked at Wikipedia, and the [large countable ordinal](http://en.wikipedia.org/wiki/Large_countable_ordinal) page has a lot of information. In particular, the "smallest number that is interesting because the system can't even prove it's a number" corresponds to the [unrecursable ordinals](http://en.wikipedia.org/wiki/Large_countable_ordinal#.E2.80.9CUnrecursable.E2.80.9D_recursive_ordinals), if we require nothing other than computability as the resource bound.

> **Comments:**
> **username_4**: If you want to limit things to the naturals, you might need to talk about functions from the naturals to the naturals, instead of just individual numbers.  My favorite weird-result paper is [one that explicitly calulated the first 64 bits of the uncomputable Chaitin's Omega](http://www.expmath.org/expmath/volumes/11/11.3/Calude361_370.pdf).  Finite prefixes of uncomputable functions can be computed in polynomial time.  

---

