Results 31 to 60 of 79
-
2019-04-11, 10:46 AM (ISO 8601)
- Join Date
- Aug 2011
-
2019-04-11, 12:39 PM (ISO 8601)
- Join Date
- Sep 2014
Re: Finding a point in an infinite space
And then that can in turn be extended with further similar lines to bisect the plane in a new way that narrows your search space from an 8th to a 16th, and so on. It'd probably be easiest to specify where the lines should be using radians, since that system is basically set up to divide circles up nicely, but it could be done with slopes and lines of the form y=mx as well. (All of those would pass through the origin, and you just keep adjusting your m to get the new slopes at the different angles.)
The first few steps of the algorithm would be:
Is the point a solution to x>0? (this answer determines if it's in combined Q1 and Q4, or combined Q2 and Q3)
Is the point a solution to y>0? (this answer determines if it's in combined Q1 and Q2, or combined Q3 and Q4)
At this point, we know which quadrant it's in. Then ask if it's a solution to y>x (if it's determined to be in Q1 or Q3) or y>-x (if it's in Q2 or Q4). You've now narrowed it down to an 8th of the space, or half a quadrant.
Then ask about the similarly appropriate y>mx to bisect your 8th to get a 16th, and so on.
-
2019-04-11, 01:06 PM (ISO 8601)
- Join Date
- Apr 2008
- Location
- Germany
- Gender
Re: Finding a point in an infinite space
I think the 'half your search area' part is pretty easy / obvious, but how do you continue afterwards? How do you find the distance systematically?
(also, depending on how you phrase your questions, you may run into a problem this way, because at some point you want to know if it's on the line or in a sector)
-
2019-04-11, 02:06 PM (ISO 8601)
- Join Date
- Jun 2013
- Location
- Bristol, UK
Re: Finding a point in an infinite space
The end of what Son? The story? There is no end. There's just the point where the storytellers stop talking.
-
2019-04-11, 02:50 PM (ISO 8601)
- Join Date
- Jan 2007
Re: Finding a point in an infinite space
Radius value you can search for in the same manner:
1. Is x^2+y^2<r^2?
If yes, then you have an upper bound and can bisect to get the exact result.
If not, increase r and repeat until yes. Then the last and second to last r gives upper and lower bounds, so you can continue with bisection.
Mix those questions with those concerning asimuth and it will be a fully fuctional algorithm, which for any finite (x,y) will give the sought point with arbitrary precision with finite number of questions. For integer pairs it will find the exact number in finite time, while for real number pairs it will require countable infinity of questions to be exact.
I am not sure, which radius incrementation method would be optimal, but I would guess exponential. Anything faster would leave a much larger area to search through once you have the upper bound while anything slower will take way more questions to reach upper bound.In a war it doesn't matter who's right, only who's left.
-
2019-04-11, 03:25 PM (ISO 8601)
- Join Date
- Aug 2018
- Location
- six feet under
- Gender
Re: Finding a point in an infinite space
Warty Goblin's method also "bisects" the space of possible answers, in the sense that after each question the possible number of solutions is halved. (His method was asking if successive digits in the binary representation of each number are 0 or 1.) I don't believe it works for continuous spaces though. (Maybe one could add a step checking whether the number was less than a particular power of two, and then go to successively more precise digits?)
—CaeruleaLast edited by Caerulea; 2019-04-11 at 03:30 PM.
Non caerulea sum, Caerulea nomen meum est.
Extended Signature.
I'm not not a humanoid. Come not not be one too.
Answer trivial questions in the OOTS trivia thread!
she/her
-
2019-04-11, 03:55 PM (ISO 8601)
- Join Date
- Feb 2012
- Location
- Boston, MA
Re: Finding a point in an infinite space
I don't know if you can have an uncountably infinite number of questions. It seems like the set would inherently be countable because you can say this is the first question, this is the second question, etc... and thus count them. Of course if you need any sort of infinity to answer the question, you're going to have problems answering it in the real world.
If you wanted to generalize the question for all numbers and be able to answer it realistically - i.e. without any sort of infinity - then I think you'd have to rephrase the question. Say, you aren't given an infinite amount of questions, but you also don't have to give all the digits, just enough for whatever degree of precision is specified. Like how we don't know all the digits of π but we can calculate it to whatever precision is required, given enough time.
So the problem instead is to determine x and y to n decimal places, given a finite amount of questions (however many you want, but not infinite). Can that be done for all numbers?
In that case, the answer is most certainly no, you can't do this for all numbers. You could do it for approximately 0% of numbers in existence. That's basically the definition of computable numbers, so of course it wouldn't work for uncomputable numbers, and most numbers are uncomputable.
The set of irrationals is uncountably infinite, but the amount of digits in an irrational number is countably infinite. So you can still brute force the problem by asking questions until each digit is known with only a countable amount of questions.
-
2019-04-11, 04:53 PM (ISO 8601)
- Join Date
- Oct 2010
- Gender
-
2019-04-11, 05:21 PM (ISO 8601)
- Join Date
- Jun 2008
- Location
- New Zealand
- Gender
Re: Finding a point in an infinite space
For continuous spaces you can still reduce to a single number with a space-filling curve, then use a binary search between two whole numbers, but you will need an infinite number of questions to find an irrational number than way.
Edit: finding a rational number is actually the same problem, you're just looking for (x/y) rather than (x, y).
If you know the number is finite, and that is implied by it being a number, you don't need infinite questions. If nothing else you can just ask "is it 0?", "is it 1?" and so on. Number of questions equal to the number, so still finite.Last edited by Excession; 2019-04-11 at 05:27 PM.
-
2019-04-11, 05:22 PM (ISO 8601)
- Join Date
- Dec 2009
- Location
- Birmingham, AL
- Gender
-
2019-04-11, 06:35 PM (ISO 8601)
- Join Date
- Jan 2007
Re: Finding a point in an infinite space
You are actually disproving the point you make in the second paragraph with what you plainly state in the last one. Since one only needs countable infinity of questions to obtain any irrational number exactly, then getting just any finite number of digits will require finite amount of questions.
In other words, if you prescribe a given precision p, you silce the whole plane into p by p squares. Since you have countable infinity of such squares and the problem is simplified to just finding the right square, then with finite amount of questions you will always reach the target.
edit:
Warty Goblin's method does bisect the the plane every time and you can easily extend it, so it would work for continuum simply by asking not just about higher digits but the fracions as well. The only thing it does not do is to give a good approximation until it obtains the highest digit.Last edited by Radar; 2019-04-11 at 06:40 PM.
In a war it doesn't matter who's right, only who's left.
-
2019-04-11, 07:45 PM (ISO 8601)
- Join Date
- May 2007
- Location
- Tail of the Bellcurve
- Gender
Re: Finding a point in an infinite space
Blood-red were his spurs i' the golden noon; wine-red was his velvet coat,
When they shot him down on the highway,
Down like a dog on the highway,And he lay in his blood on the highway, with the bunch of lace at his throat.
Alfred Noyes, The Highwayman, 1906.
-
2019-04-11, 07:48 PM (ISO 8601)
- Join Date
- Feb 2012
- Location
- Boston, MA
Re: Finding a point in an infinite space
Hrm, that depends on whether an answer with a finite amount of digits - a decimal approximation - is counted as a correct answer. Yes, I suppose if you accept a finite amount of digits as a valid response, then we're back in the realm of rational numbers, so of course you only need a finite amount of questions. But a decimal approximation isn't exactly the same number, is it? That's not the case for any irrational numbers, or even many rational ones in base 10. So the issue, I think, is that the person asking the question magically knows all the digits and is able to check them to decide whether our approximation should count... which is all certainly impossible. So my rephrasing of the question is still not a remotely realistic scenario, sorry.
Last edited by JCarter426; 2019-04-11 at 10:49 PM.
-
2019-04-11, 09:46 PM (ISO 8601)
- Join Date
- Aug 2011
Re: Finding a point in an infinite space
I think this is a misunderstanding of infinity. Yeah, we can describe numbers, even irrational and transcendental ones, through countably infinite steps, but you won't actually reach the target. If it takes countably infinity steps, by definition you do not get to reach the target.
Think of it this way: a lot of the methods suggested can only ever produce a rational number; some are worse and can only produce a decimal/binary number. Such a method could never reach an irrational or transcendental number. It could get close, as close as you want. But they necessarily can not reach the target.
EDIT:
We can reach the target in the same sense that we can calculate pi or describe 1/3 in decimal notation, which is to say we can't.
In that case, the answer is most certainly no, you can't do this for all numbers. You could do it for approximately 0% of numbers in existence. That's basically the definition of computable numbers, so of course it wouldn't work for uncomputable numbers, and most numbers are uncomputable.Last edited by crayzz; 2019-04-11 at 09:58 PM.
Originally Posted by crayzzOriginally Posted by jere7my
-
2019-04-11, 10:19 PM (ISO 8601)
- Join Date
- Feb 2012
- Location
- Boston, MA
Re: Finding a point in an infinite space
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.
-
2019-04-11, 10:29 PM (ISO 8601)
- Join Date
- Jun 2008
- Location
- New Zealand
- Gender
Re: Finding a point in an infinite space
I don't agree, because even an arbitrarily precise approximation isn't the actual number. Getting the exact irrational number would require infinite time, which I think doesn't match the definition of "computable".
With the original question though, when it's only whole numbers, all possible numbers can be found. No questions of precision needed.Last edited by Excession; 2019-04-11 at 10:30 PM.
-
2019-04-11, 10:38 PM (ISO 8601)
- Join Date
- Aug 2011
Re: Finding a point in an infinite space
Which is another way of saying this scenario could never exist.
Which, I mean: that's obvious, but it's kinda neat stumbling over an actual proof for it.
I don't agree, because even an arbitrarily precise approximation isn't the actual number. Getting the exact irrational number would require infinite time, which I think doesn't match the definition of "computable".Last edited by crayzz; 2019-04-11 at 10:44 PM.
Originally Posted by crayzzOriginally Posted by jere7my
-
2019-04-11, 10:42 PM (ISO 8601)
- Join Date
- Feb 2012
- Location
- Boston, MA
Re: Finding a point in an infinite space
The definition of computable:
Originally Posted by Wolfram
The issue isn't an infinite amount of digits - not all irrational numbers are uncomputable, and actually all the ones we know are computable. The issue is whether a finite process can determine what those digits are.
A number like π is irrational and transcendental but still computable. We can take the ratio of a circle's circumference to its diameter to determine the value to whatever degree of precision we want. That's a finite amount of steps that can give us the number to whatever decimal place we want. In that sense it is computable.
An uncomputable number is one for which no such process exists. You'd truly need an infinite amount of steps to determine the digits. Which is exactly what an unlimited series of yes/no guesses gives you, provided that somebody magically knows the answer already.
Indeed.Last edited by JCarter426; 2019-04-11 at 10:55 PM.
-
2019-04-11, 10:44 PM (ISO 8601)
- Join Date
- Aug 2018
- Location
- six feet under
- Gender
Re: Finding a point in an infinite space
These methods are not actually less powerful. The method that could determine a binary representation of the number, could determine a binary representation of anything. For instance, the binary encoding of any rational number, assuming there exists a way to uniquely encode rational numbers in binary, which there does.
I think there is a misunderstanding with regards to countable infinity. Just because there are countably infinite steps does not mean that it is impossible, because time doesn't matter in this hypothetical scenario. Each step might be evaluated on a magical device so that it takes no time. Then we would arrive at an answer. The answer would have infinite information, but it would still be an answer. We can represent 1/3 in decimal notation, it is a 0.3 followed by infinite 3s. Just because actually writing it out would be impossible does not mean it doesn't exist, and neither does it not exist because there are infinite digits (side note, 2 has infinite digits in its decimal representation. It just so happens that most of them are 0). Numbers are not a process.
Even if the algorithm did not take 0 seconds, it could still be completed in finite time. What if each successive step was executed twice as fast, and the first took 1 minute. Then the entire process would take 2 minutes.
The point is, with a countably number of steps and an omniscient oracle, you can determine exactly a number so long as the steps take a finite amount of time in sum.
—CaeruleaLast edited by Caerulea; 2019-04-11 at 10:46 PM.
Non caerulea sum, Caerulea nomen meum est.
Extended Signature.
I'm not not a humanoid. Come not not be one too.
Answer trivial questions in the OOTS trivia thread!
she/her
-
2019-04-11, 11:01 PM (ISO 8601)
- Join Date
- Aug 2011
Re: Finding a point in an infinite space
I shouldn't have said we can't describe 1/3 in decimal notation, since we have an actual notation for repeating decimals. But it is true that a algorithm that can only produce decimal numbers will never spit out 1/3.
And that's exactly the point I was trying to argue against! If your algorithm can only produce a certain type of number, you can't get outside that type of number no matter what. Proposing countably infinite steps in finite time sounds nice, but I don't think it actually works. It violates what we know about computation for one thing. A turing machine of a given complexity will either halt or loop forever: you don't get to have it halt after infinite steps.
This, incidentally, brings up a practical concern with actually implementing the algorithm even in the integer case: without knowing how big the number actually is, we can't know that we've chosen a turing machine "large" enough to handle it. But setting that aside, no turing machine could ever compute a transcendental number to exact precision, or an uncomputable number to even arbitary precision.Last edited by crayzz; 2019-04-11 at 11:02 PM.
Originally Posted by crayzzOriginally Posted by jere7my
-
2019-04-12, 12:20 AM (ISO 8601)
- Join Date
- Oct 2014
- Location
- Tulips Cheese & Rock&Roll
- Gender
Re: Finding a point in an infinite space
As elegant as Warty's method is, it seems you need less questions if you use a larger numerical system. That's because for every time you ask "is the next digit 1?" you also have to ask "is there a digit after this?" you're distinguishing between three states for each digit, 1, 0 and not there, lowering efficiency.
If you use for instance hexadecimal notation things get better. A hexadecimal digit represents 4 bits, and you can pin down the value of a hexadecimal digit in 4 questions (1-8, 1-4, 1-2, 1), but you only need a single questin after that to ask about the next digit.
This means it becomes even more efficient when you take things a full byte at a time, or some even larger number. You could also try working with a notation system one short of the round numbers. "In a pentadecimal system, is the next digit between 8 and 15 or non-existent?" (If we start counting question length for efficiency this is going to kill it.)
But I feel like there should be a cleverer way to get rid of those extra questions...The Hindsight Awards, results: See the best movies of 1999!
-
2019-04-12, 12:35 AM (ISO 8601)
- Join Date
- Aug 2008
- Gender
-
2019-04-12, 01:38 AM (ISO 8601)
- Join Date
- Oct 2014
- Location
- Tulips Cheese & Rock&Roll
- Gender
Re: Finding a point in an infinite space
The Hindsight Awards, results: See the best movies of 1999!
-
2019-04-12, 02:08 AM (ISO 8601)
- Join Date
- Sep 2016
Re: Finding a point in an infinite space
In Hex, the 4 questions you need to ask are basically equivalent to 4 "is the next bit" questions (except in reverse in your example). So it's basically the same as only asking every 4 bits. Which does make a lot of sense (I'd make it probabilistic, you only ask after an appropriate number of zeros).
The Penta-decimal system is interesting.
Alternatively once we stop to ask the question, we could also pick up on other short cuts. Finding the number of consecutive 1s and 0s will be quicker in some cases.
*For non-existent read are all digits above this point zero.
Regardless at worst for the integers (if they plan to use the number to full accuracy in any way), we can find it almost as easily as they can use it for size comparisons.
Which I think counts for finding a number on a plane.
-
2019-04-12, 02:19 AM (ISO 8601)
- Join Date
- Apr 2008
- Location
- Germany
- Gender
Re: Finding a point in an infinite space
Hm... Good point. Though 'not there isn't really a state, but you could add as many zeroes as necessary in front, even though it's highly unusual (1010 is as correct as 0001010 in theory, no?)
Since we're limited to whole numbers, how efficient would be asking for divisibility? Is it divisible by 2 / 3/ 4... Skipping obviously wrong questions. (which is mostly just a way to get the binary approach to normal numbers) Is it much worse than other techniques?
-
2019-04-12, 02:23 AM (ISO 8601)
- Join Date
- Jun 2008
- Location
- New Zealand
- Gender
Re: Finding a point in an infinite space
Ah, thanks. I guess it's been I while since I studied this stuff properly.
For the binary digit version on real numbers, you would have to ask if the digits repeated, then narrow down the length of the repeat, and "1.00000..." is just a trivial case of that.Last edited by Excession; 2019-04-12 at 02:27 AM.
-
2019-04-12, 03:59 AM (ISO 8601)
- Join Date
- Jan 2007
Re: Finding a point in an infinite space
Considering that the proposed problem allows infinite amount of questions as a valid solution then we actually do reach the sought number in the limit. Being infinitely close is the same as reaching the target as for example 1=0.9999999... by the very definition of real numbers. It would stop being true if we extended real numbers with infinitesimals, but it is not the case.
Besides, the part you quoted concerns finite precision search, which boils down to searching for a pair of intigers and those can be always found with finite amount of questions, since they are countable.In a war it doesn't matter who's right, only who's left.
-
2019-04-12, 05:19 AM (ISO 8601)
- Join Date
- Aug 2008
Re: Finding a point in an infinite space
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.Last edited by Knaight; 2019-04-12 at 05:22 AM.
I would really like to see a game made by Obryn, Kurald Galain, and Knaight from these forums.
I'm not joking one bit. I would buy the hell out of that. -- ChubbyRain
Current Design Project: Legacy, a game of masters and apprentices for two players and a GM.
-
2019-04-12, 05:22 AM (ISO 8601)
- Join Date
- Aug 2018
- Location
- six feet under
- Gender
Re: Finding a point in an infinite space
I think prime numbers would be best if you are looking at factors. Maybe something like:
- Is the number divisible by prime p?
- If Yes: store p and ask about two again, If no:
- Is the next prime large than the number? If so: break. (There is probably a smaller end condition that could be used).
- 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.
—CaeruleaNon caerulea sum, Caerulea nomen meum est.
Extended Signature.
I'm not not a humanoid. Come not not be one too.
Answer trivial questions in the OOTS trivia thread!
she/her
-
2019-04-12, 05:32 AM (ISO 8601)
- Join Date
- Aug 2008
Re: Finding a point in an infinite space
I would really like to see a game made by Obryn, Kurald Galain, and Knaight from these forums.
I'm not joking one bit. I would buy the hell out of that. -- ChubbyRain
Current Design Project: Legacy, a game of masters and apprentices for two players and a GM.