Finding a point in an infinite space

[halfeye]

The whole tangent on finite sums of infinite series is irrelevant anyways - the numbers must be finite in a discrete space, which means the number of steps must be finite. As for an algorithm I'd take a page from various numerical methods. Specifically.
1) Establish quadrant/origin (is X>0, is X<0, repeat for Y).
2) Methodically use an open search method. I'd probably just use logarithms, sequentially asking is X >10, is X >100, >1000, >10000, etc. You could also do something like use Knuth up arrow notation to start with, for much larger steps.
3) Once that hits I switch to a bisection search. As an example if I know it's between 10000 and 100000 I'd ask if X>55000. If I get another yes, is X>77500. Repeat until you find the number. I could also use a golden section search, which is theoretically faster, but whatever.
4) Repeat steps 2 and 3 for Y.

This should be faster than Warty's method. It can also be combined with Warty's method (e.g. using a base 1024 system and going digit by digit asking if it is greater than 513, then bisecting as needed. It gets the number of digits before the decimal pretty rapidly, then closes in O(log(n)) time. This also works with any arbitrary space that has the singular point, not just a plane.

The problem with this method, and all the other methods, is that most of the numbers are between the biggest number we can think of and infinity. All the numbers we can think of are much less than 0.001% of the numbers.

[JCarter426]

I think prime numbers would be best if you are looking at factors. Maybe something like:

1. Is the number divisible by prime p?
2. If Yes: store p and ask about two again, If no:
3. Is the next prime large than the number? If so: break. (There is probably a smaller end condition that could be used).
4. Is the number divisible by the next prime? Goto step 2

It takes iterations equal to amount of the number's prime factors + the number of primes less than the number that are not prime factors.

—Caerulea

Twice the amount of prime factors. For example:

Divisible by 2? Equal to 2? Yes. Divisible by 3? Yes. Equal to 6? No. Divisible by 5? No. Divisible by 7? Yes. Equal to 42? Yes.

In that example, 3 prime factors * 2 questions for each factor (is it divisible by p and is it equal to p * all the previous factors) + 1 prime less than the number that isn't a factor = 7 questions.

Of course, if we skipped asking whether it's equal to 2 and just went to whether it's divisible by 3, we'd get an answer and save one question. But the number could very well just be 2, or it could be 2 times an arbitrarily large prime and you wouldn't know the difference. There would certainly be more efficient algorithms for certain numbers, but I don't know if you can generalize that. If we're talking an infinite amount of possible numbers, then every prime combination should be equally likely.

[tonberrian]

You should start off with Is it Prime? first. If Yes, you don't have to ask about factors, and if No, you don't have to ask Is it 2? Also, you need to ask Is it 1 before any prime search.

Edit: And Is it 0?

[Peelee]

You should start off with Is it Prime? first. If Yes, you don't have to ask about factors, and if No, you don't have to ask Is it 2? Also, you need to ask Is it 1 before any prime search.

Edit: And Is it 0?

Or just add "is it composite" after "is it prime."

Of course, "yes" to the first reduces the remainder to ∞ possibilities, "yes" to the second similarly leaves with you only ∞ possibilities, and the odds of it being 1 or 0 are 1 in ∞. But hey, if both those trigger a "no," go you!

[Douglas]

I think we just proved uncomputable numbers don't exist in this hypothetical scenario, because there always exists a series of yes or no questions that we can ask our magic all-knowing questioner to compute any number to any degree of precision.

No, they're just restricted to being specified by things other than "the number this oracle is thinking of". The ability to compute an arbitrary amount of digits for this one specific number does not help in finding the value of the 20th Busy Beaver number.

[JCarter426]

It does if that's the number the oracle is thinking of.

[tonberrian]

It does if that's the number the oracle is thinking of.

An omniscient oracle who knows all things can indeed lead to the calculation any given uncomputable number.

Ergo, omniscient oracles can't exist...?

[crayzz]

I'm gonna try to put numbers on the various techniques suggested so far. I'm just gonna make up names for convenience. Since the integer points on a plane are easily mapped to a number line, I'm often going to assume we're looking for an arbitrarily large positive integer.

exponential bound + binary search

---

The idea here is to put an upper bound on what X could be, then find X. To do that, start with some base b and ask if X <= b; if not, ask if X <= b², etc etc. Doing this will take log_b(X) (rounded up) questions to put an upper bound on X. After that, you do a binary search. If it took n questions to place the bound, the range you need to search is between bⁿ and b^n-1, which leaves us with b^n-1(b-1) numbers to check. Doing a binary search will take roughly log₂(b^n-1(b-1)), which simplifies to nlog₂(b) for a very large b; since n = log_b(X), the search will take roughly log_b(X)log₂(b) questions.

So that gives us a total of log_b(X) + log_b(X)log₂(b) questions, or log_b(X)(1 + log₂(b)) questions. Since b is unbounded, we can choose one such that b is large enough that even log(b) >> 1, we can simplify to log_b(X)log₂(b), which through change of base simplifies to just log₂(X).

Assuming b = 2, we get a similar equation. Placing the upper bound takes log₂(X) questions, and doing the binary search takes log₂(X) - 1 questions (the search space will always be exactly half the bound, so it takes 1 less question to search on average). So using b = 2 takes roughly 2log₂(x) questions.

So, we can actually do better if we pick a larger exponential base to work with, but we get diminishing returns because we can never get faster than log₂(X). We can even get considerably slower if we accidentally pick b such that b >> X. I would say just pick some arbitrary b that satisfies the above simplifications and be done with it. b = 2¹⁰⁰ is probably good enough.

I did consider a faster growing scheme but I think you end up just creating more work for yourself. The speed of the binary search grows logarithmically. So if your bound grows faster than exponential growth, the binary search won't be able to keep up. You get less steps in the bound placing section but waaay more steps narrowing down on X after that. Consider growing things by up arrow notation. You ask if X <= 2, X<= 2^2, X <= 2^^2, ..., X<=2²^2, etc. If it takes n steps to place the bound, the binary search will take roughly log₂(2ⁿ^2), which works out to 2^(n-1)^2 questions. I can't actually say if 2^(n-1)^2 questions would be better than log₂(X) questions, I'm not really adept at manipulating up arrow notation. But my intuition is that it'd be astronomically slower to grow with up arrow notation rather than exponential notation.

All of this assume we're looking for a single point. If we blindly search of X and Y separately, it would take at most 2log₂(X) questions, assuming X>=Y. We could ask which is larger, then we can shave off some questions finding the larger one by finding the smaller one first; we start with a lower bound when finding the larger one. There might even be a way to get fancy and include some boolean logic by asking about X and Y in the same question to speed things up, though I can't think of one.

We could also just map the plane to a line: someone suggested using a square spiral to map the plane to a line and then just ask where the point gets mapped to on the line. I think this severely slows things down, but there might be other mapping techniques that could speed things up.

Radius search

---

Someone suggested growing a circle of radius R until we've encapsulated the point in question. I'd suggest growing the radius using the exp. growth and then binary search method, but we have a problem: most points on the plane don't fall on a rational radius. They only fall on a rational radius if X and Y are part of a Pythagorean triple (r = sqrt(X^2 + Y^2), and the sqrt of a whole number is only rational if it's whole). Take the point <1,1> for instance: you'll never narrow in on the exact radius. Now, you don't actually need to: if 2>r>1, then there's exactly 4 points that could possibly work, and you can just work through them exhaustively in 2 questions. But what about if 1323>r>1322? How many points fit in there? Are there any points in there? No idea.

Prime Factors

---

This one is really neat to me, but presents a few problems. The biggest problem is that we don't know all the primes. We have no way of reliably generating all the primes through anything else besides brute force. If we're willing to grant that we somehow have a list of all primes, or are willing to accept an answer like "the product of the primes with indices (3^^^^3) and (3^^^^3 + 1)" as an answer, than cool, we can continue.

The other issue is if there are any repeating prime factors. We can't just ask if X is divisible by 2: we also have to ask if it's divisible by 4, 8, 16, etc. And then again for 3, 5, 7. Doing this exhaustively would be incredibly slow.

So: first question to ask is if X is prime. If it is, we just find the index using whatever method you want. Prime density grows at X/ln(X), so this search would take log₂(X) - log₂(ln(X)) using the growth + binary search method.

If it isn't, my next question would probably be "how many prime factors does X have" (e.g. 12 in this case would have 3 prime factors, since 12 is 2x2x3). The most prime factors X could possibly have is log₂(X), which means this would take log₂(log₂(X)) to calculate. We'll call this number K, where K = log₂(X) at most.

Knowing K, I would then propose the following scheme: expand through the index of primes exponentially, at each index asking "are all prime factors below this index." The largest prime factor a number could possible have would be X/2^K-1 so in the worst case this will take log₂(X/2^K-1/ln(X/2^K-1)). Note that K being small here is actually worse.

Having found this point, do a binary search through the range asking "are there more prime factors at or above this index than below it" to narrow in on all the prime factors. I'm not quite sure how to implement this search or how fast it would be, but I don't think it'd be much slower than searching for an individual prime factor, since you're recording information about where all the other factors are as you search.

One you hit a prime factor, you can start asking how many times that factor is a prime factor, which we've also gathered information on. Take this example: we know all the prime factors are smaller than the 100th prime, and there's 12 factors. We ask if there's more primes above or below index 50. There's fewer above. Of those above index 50, we ask if there's more prime factors above or below 75. There's fewer below. At this stage we know there are at most 5 factors above index 50, and at most 2 of those are between index 50 and 75. Even if we just stopped here and searched prime factors of index 50 to 75 exhaustively, we only need ask if they appear in the prime factorization once or twice. From 75 to 100, we need only ask if they appear in the prime factorization of X once, twice, or thrice. Say prime 65 appears twice, and primes 97, 98, and 99 each appear once: there's 7 primes remaining, and we can continue the process for all primes with index less than 50.

Now at this point we're well beyond my ability to quantify exactly how fast this process is. but I'm reasonably certain it's competitive with simple exponential growth coupled with binary search. It might even be faster.

---

I was going to add more, but this is getting long and I have work to do, so I'll take a proper stab at the others later.

No, they're just restricted to being specified by things other than "the number this oracle is thinking of". The ability to compute an arbitrary amount of digits for this one specific number does not help in finding the value of the 20th Busy Beaver number.

It does if there's one oracle for every real number, or for that matter if we can tell the oracle what number to think of. If we could tell it "think of Chaitin's constant" then it doesn't matter what the oracle is thinking of now, only that it could be thinking of Chaitin's constant.

(I'm not sure telling the oracle what number to think of would eliminate all uncomputable numbers, but it would eliminate all the ones we know about and can describe).

Ergo, omniscient oracles can't exist...?

I feel like you're arguing with JCarter426 but this is exactly the conclusion they've reached up thread.

[jayem]

The problem with this method, and all the other methods, is that most of the numbers are between the biggest number we can think of and infinity. All the numbers we can think of are much less than 0.001% of the numbers.

I think we if we have a given method where we can say how many steps it needs for a given number, and it scales passably, then we can kind of argue the toss.
Linearly I think is not really ok. I can easily write the number of atoms in the universe in full, I can't do that many operations.
Logrithmically I think is better, in N questions we can only separate 2^N sets (so it is literally the best we can do), doing anything accurately with the number requires a similar number of steps.
It's a bit sophistic (as you say, there are a lot of numbers out there. But on the other hand if it really was 'just' much less than (((0.001)^100)^100^100)% of the numbers we'd only need to add a mere 10 million more questions, which would be a very sad lifetime but in theory doable.) For any number once we (by whatever magical means) have the resources to identify it and a non trivial proportion of the number line up to that point we also have the resources to identify it by binomial chop.

I do like the sound of the primes method, but I don't think it can gain too much in general. If n is a prime we use n/log(n) steps (prime number theorum) which is clearly worse (and I don't think that can be improved on). We do of course gain elsewhere, in 100 simple steps we can identify the number 229⁵⁰ which would take us 400 steps by binomial chop (and Knaights variation could take us up much further).

Going back to the sophistry, the above was a bit tautological (both statements more or less boil down to we can write down the digits). There are of course many numbers we can express in other ways which grow quicker than our efforts to express them, e.g. Graham's number and which we can still do some stuff with (we can of course use binary chop on the ascii of the 'program' that computes it).
So something that very quickly gave an 'appropriate' ranged box (the range being almost 'identical' to the number, so effectively no progress towards an exact representation) would be interesting.

[Caerulea]

[cool maths]

Well done.

Jayem, I can't really tell what you are trying to say. Are you saying that for large numbers, actually running the algorithm is hard? I don't think anyone disputes it, but if we can ask countably infinitely many questions we probably have an infinite amount of time.

—Caerulea

[crayzz]

Not a real suggestion, but: assuming we could generate arbitrary algorithms, we could always just go through a list of them and ask if that one is the fastest, then implement it.

Though I'd be hard pressed to think of a slower method of doing things.

[Peelee]

Well done.

Jayem, I can't really tell what you are trying to say. Are you saying that for large numbers, actually running the algorithm is hard? I don't think anyone disputes it, but if we can ask countably infinitely many questions we probably have an infinite amount of time.

—Caerulea

The real question is how many monkeys do we have?

[Caerulea]

The real question is how many monkeys do we have?

Too many.

—Caerulea

[jayem]

Jayem, I can't really tell what you are trying to say. Are you saying that for large numbers, actually running the algorithm is hard? I don't think anyone disputes it, but if we can ask countably infinitely many questions we probably have an infinite amount of time.

—Caerulea

Trying to convince myself (and halfeye) that it is 'reasonably' hard.

There's enough 1-1 correspondences already that messing about with them to exploit infinity is something that if I avoid I'd be happier. If it works on the infinity is just a big number level that strikes me as being for the good.

We could for instance just use the "Q-1: Is it 1", "Q-2: Is it 2"... approach.

The logrithmic timescale is of course the best we can do (for the finite case at least). And that kind of passes that subjective test in a "Log(infinity) is clearly much less than infinity." way [but it's also easy to see that we can always make it take much longer than any given amount of time, which shows how dodgy that statement is]

[warty goblin]

Or just add "is it composite" after "is it prime."

Of course, "yes" to the first reduces the remainder to ∞ possibilities, "yes" to the second similarly leaves with you only ∞ possibilities, and the odds of it being 1 or 0 are 1 in ∞. But hey, if both those trigger a "no," go you!

Strangely enough, one can't really talk about the probability of picking the correct number, or expected number of steps to convergence or anything like that, because there is no uniform probability distribution over the whole numbers (or any other countably infinite set). If the person generating the variable is doing so randomly, they're using a non-uniform distribution.

[Radar]

Strangely enough, one can't really talk about the probability of picking the correct number, or expected number of steps to convergence or anything like that, because there is no uniform probability distribution over the whole numbers (or any other countably infinite set). If the person generating the variable is doing so randomly, they're using a non-uniform distribution.

As weird as it sounds at first, it pretty much has to be true. One thing we should most likely assume, that it is a distribution with a heavy tail, so the mean is infinite. Still, if one really insist on having a nonzero probability density everywhere, then it puts a specific condition on the disctribution f, which is that the integral over the whole distribution needs to be equal to 1 (here for 1D):

Integral^infinity_(-infinity) dx f(x) = 1

For it to be true it has to be finite first, so

limit_(x->infinity) x*f(x) = 0

Interestingly, for more dimensions it will constrain the distribution even more. If we assume maximum randomness (so no angle dependencies), then

Integral^infinity_(-infinity) dx dy f(x,y) = Integral_0^(infinity) dr f(r,phi)*r Integral_0^(2 Pi) dphi = 2 Pi*Integral_0^(infinity) dr f(r,phi)*r

So we have an extra r under the integral. This gives us the condition as

limit_(r->infinity) r^2*f(r) = 0

While you can have well defined distributions, which converge slower then that, but it can only happen in a well defined direction in the r->infinity limit. A simple example would be to take a 1D distribution in each direction and multiply them:

f(x,y)=f_1(x)f_2(y)

Along the axes the convergence will be as slow as in the 1D case, but this will happen only if we take the limit in a direction parallel to the X or Y axis. In any other direction the convergence is much faster and fits the asymptotic criterion.

In the same manner for n dimensions it will be

limit_(r->infinity) r^n*f(r) = 0


Still such distributions can easily have infinite mean value.

[JCarter426]

An omniscient oracle who knows all things can indeed lead to the calculation any given uncomputable number.

Ergo, omniscient oracles can't exist...?

I feel like you're arguing with JCarter426 but this is exactly the conclusion they've reached up thread.

Yes.

I mean, it's not incredibly profound, as we said before, but that's the paradox of it. If the question is whether the process is true for all reals, on the surface the answer should be no, because we know there are uncomputable numbers, so we shouldn't be able to find a process that works for them. But we can also demonstrate a process that does work if we have an oracle to confirm the answer. The conclusion, of course, is that they can't actually be thinking of an uncomputable number and can only know some finite approximation of it. But that goes against the premise of the question.

[Douglas]

Yes.

I mean, it's not incredibly profound, as we said before, but that's the paradox of it. If the question is whether the process is true for all reals, on the surface the answer should be no, because we know there are uncomputable numbers, so we shouldn't be able to find a process that works for them. But we can also demonstrate a process that does work if we have an oracle to confirm the answer. The conclusion, of course, is that they can't actually be thinking of an uncomputable number and can only know some finite approximation of it. But that goes against the premise of the question.

I think you're misinterpreting what it means for a number to be uncomputable. It does not mean that the number is impossible to represent. It means that the number is impossible to identify the value of from its definition.

For example, consider the two thousandth Busy Beaver number. It's a finite integer by the nature of its definition, so if someone actually knew its value and had enough time, space, and materials it would obviously be possible to write it down. At the same time, it has been proven to be uncomputable. This is not a contradiction, because it just means that no one will ever know which integer is "the two thousandth Busy Beaver number".

[crayzz]

I think you're misinterpreting what it means for a number to be uncomputable. It does not mean that the number is impossible to represent. It means that the number is impossible to identify the value of from its definition.

For example, consider the two thousandth Busy Beaver number. It's a finite integer by the nature of its definition, so if someone actually knew its value and had enough time, space, and materials it would obviously be possible to write it down. At the same time, it has been proven to be uncomputable. This is not a contradiction, because it just means that no one will ever know which integer is "the two thousandth Busy Beaver number".

All integers are computable. There exists an algorithm for computing every integer. A question like "what is BB(2000)" is undecidable, but BB(2000) itself is perfectly computable.