3
$\begingroup$

Is there an intractability theorem that says that in any sufficiently rich system for defining really big numbers, there will be two numbers for which it's very, very, ... very difficult to decide which one is bigger?

Here I'm thinking of the kind of system that's embodied in the whimsical pictures in Rich Schwartz's book "Really Big Numbers". Such a system should allow for recursively defining new functions in terms of old, so that one can build up multiplication, exponentiation, tetration, ..., (and things beyond that size-$\omega$ hierarchy) from addition. There are many different systems of this kind, but I am imagining some sort of diagonalization argument that would apply to all of them.

I expect that the phrase "very difficult to decide" can be made concrete in a number of different way; I ask that the phrase be interpreted with some latitude, as I am interested in learning about all known results of this kind.

Improve this question
$\endgroup$
5
  • $\begingroup$ Given any such system there is always another which will produce a bigger output when given the same input. One way it can be seen is through a diagonal argument. $\endgroup$
    – ARi
    Commented Nov 14, 2015 at 18:42
  • 2
    $\begingroup$ I agree, but how does this relate to the question? I was asking about a routine that accepts as input a pair of definitions of natural numbers (like a googolplex and Graham's number) and outputs a single bit that says which one is bigger. So the notion of a "bigger output" does not immediately apply. $\endgroup$
    – James Propp
    Commented Nov 14, 2015 at 20:26
  • $\begingroup$ I can imagine the existence of a theory T which is an extension of Peano's Arithmetic (PA). Further T could be consistent if PA is. In T the relation "bigger than " could then be defined. There might be two numbers "a" and "b" which are both definable in T, whose definitions are such that each of the statements "a is bigger than b" and "b is bigger than a" are unprovable in T but are consistent with T when added as axioms to T. $\endgroup$
    – Garabed Gulbenkian
    Commented Nov 14, 2015 at 21:10
  • $\begingroup$ If there is such a function it can not be 'total'. Producing a result on every input pair would effectively enable one to decide if an arbitrary mu recursive function terminates. $\endgroup$
    – ARi
    Commented Nov 15, 2015 at 3:38
  • $\begingroup$ There are some small numbers for which it is very difficult to decide which one is bigger, e.g., one-half, and the number of zeros of the zeta function in the critical strip but off the critical line. $\endgroup$
    – Gerry Myerson
    Commented Nov 15, 2015 at 22:27

2 Answers 2

Reset to default
3
$\begingroup$

This is related to Richardson's Uniformity Conjecture, which Richardson himself disproved some years later.

From a computer science perspective, this is especially interesting because of the prominent features of sharing (and lack thereof), as well as depth of an expression relating to how close to being 'the same' two different expressions can be.

Improve this answer
$\endgroup$
0
$\begingroup$

This discussion of bit operations is one sort of answer. Comparison for greater than is another thing that falls into this "we assume away (by definition) that it's O(n)" list of operations.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .