If this is your first visit, be sure to check out the
FAQ by clicking the link above. You may have to
register or
login before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below.
| 28 MAR 2004 at 1:25am |
| Deleted User | But what about the other way? Consider the function
(h(t)=h(t-1)+0.01)*2
which is an upper bound to g(t). Clearly, this function will always give a greater result than g(t).
Let's iterate on this function, which is more interesting:
h(t)=(h(t-1)+0.01)*2=2h(t-1)+0.02=
=2(2h(t-2)+0.02)+0.02=4h(t-2)+0.04+0.02
And another time...
h(t)=4h(t-2)+0.04+0.02=
=4(2h(t-3)+0.02)+0.04+0.02=8h(t-3)+0.08+0.04+0.02
When this thing reaches h(t)=0, we have the expression
2^t*h(t-t)+0.02+0.04+0.08+0.16+...
the first product becomes 0 because h(0)=0. All that remains is a geometric sum of t components. I've taken the liberty to rewrite it in a form that allows for easy computation of its value:
0.02*(1+2+4+...+2^(t-1))
This is equal to (look in a math book):
0.02*((2^(t-2)-1)/(2-1))=0.02(2^(t-2)-1)=0.02*2^(t-2)-0.02
As you can see, we get a function consisting of a constant times an exponential factor minus a constant.
And with large values for t it does not matter whatsoever how small the multiplying factor and how big the subtracting constant is; the exponential part will always dominate! Hence, we have an exponential function h(t) versus a linear function f(t). Such a worm would ALWAYS get to the end eventually, regardless of how slow it moved by itself or how much the rubber band was extended! Its motion function is asymptotically faster than the rubber band extension function, so it always gets bigger at some point.
But this is no good either. Now we only know that our actual worm moves slower than a worm that would be guaranteed to get to the end.
In other words, faster than guaranteed failure, slower than guaranteed success. It seems we are back on square one. Perhaps, but I though it was an interesting exercise anyway.
It appears, both from intuition and a mathematical standpoint, that the worm moves in a way where two powers cancel each other out. It weighs between success and failure, and the decisive factors are, not surprisingly, the worm's speed (which works in its favor) and the speed of the extention of the rubber band (which works against it). Given the right conditions, the worm could easily make it. But how is it the other way around? Are there bad enough conditions for it to be guaranteed to fail? Are the given parameters enough? And approximately where would the limits be?
|
| 28 MAR 2004 at 3:51am |
GreySorcerer Apprentice
Posts : 251
Joined: 3 SEP 2003
Status : Online | Originally Posted By Petter_Holmberg (27 MAR 2004 11:39pm)
Confused yet?
Anyone know where I can get a trained worm and a really long rubber band?
/\/\&&\/\/
|
| 29 MAR 2004 at 2:37pm |
ElfstoneGuild Master
Posts : 5892
Joined: 4 NOV 2002
Status : Online | Originally Posted By adventuredog (27 MAR 2004 11:48pm)
But I thought that Cantor proved that these two sets share a one-to-one correspondence, so that there is no such thing as larger and smaller infinities. Isn't that the trick with infinity? - intuitively we would think that some infinities are larger than others, but that is not true. Has someone else proved otherwise recently?
Real numbers are not countable.
But rational numbers ARE countable (cause they consist of a ratio of two integers) and infinite at the same time.
I guess you meant those.
Any two sets of real numbers (like [1..2] and [1..100]) are of the same infinite size however as there's a one-to-one correspondence between them.
I believe they share the same cardinality. But cardinality can be different between two infinite sets, which means that one is sort of "larger" than the other one.
Have a look at this
You can find lots of fascinating question in there.
[b]playing[/b]: Destination Treasure Island (done in two sittings, but it's nice), Syberia (ho-hum), Dracula: Last Sanctuary (on hold)&&[b]reading[/b]: even more study papers&&[b]listening to[/b]: [url=http://www.last.fm/user/Brax82/]this and that[/url], plus [url=http://www.musicovery.com/]Musicovery[/url]&&[b]TV favorites[/b]: (currently) Pushing Daisies, Chuck, Journeyman (cancelled! grrr...), Heroes&& all-time) 24, Stargate SG1, X-Files, Lost, House
|
| 29 MAR 2004 at 3:11pm |
ElfstoneGuild Master
Posts : 5892
Joined: 4 NOV 2002
Status : Online | Originally Posted By Petter_Holmberg (28 MAR 2004 1:25am)
0.02*(1+2+4+...+2^(t-1))
This is equal to (look in a math book):
0.02*((2^(t-2)-1)/(2-1))=0.02(2^(t-2)-1)=0.02*2^(t-2)-0.02
Why is it 2^(t-2) in the second line? Shouldn't it be 2^(t-1)? Not that it makes any difference concerning the exponential function.
But is this the correct formula?
I'm only familiar with this one:
0.02*( (2^t) - 1)
The basic formula I used is
1-r^(n+1) / 1-r [r being the base in the series and n being the upper index to count towards]
which represents the sum of the geometric series from 2^0 up to 2^t-1
??
It only marginally changes your result however.
0.02*2^t - 0.02
is still exponential of course.
[b]playing[/b]: Destination Treasure Island (done in two sittings, but it's nice), Syberia (ho-hum), Dracula: Last Sanctuary (on hold)&&[b]reading[/b]: even more study papers&&[b]listening to[/b]: [url=http://www.last.fm/user/Brax82/]this and that[/url], plus [url=http://www.musicovery.com/]Musicovery[/url]&&[b]TV favorites[/b]: (currently) Pushing Daisies, Chuck, Journeyman (cancelled! grrr...), Heroes&& all-time) 24, Stargate SG1, X-Files, Lost, House
|
| 30 MAR 2004 at 2:52pm |
| Deleted User | Hmm... I actually thought there might be some errors in my calculations there, but I didn't double-check it since I figured it didn't matter...
You are right about the geometric series, I accidentally replaced the (n+1) exponent with (n-1) which is of course wrong.
The book I used gives the formula (x^(n+1)-1)/(x-1), which is the other way around to the formula you used, but they are of course the same (multiply both above and below the division line with -1 and you get the other). So yes, it's actually 2^t instead of 2^(t-2) and that looks even nicer.
The reason it doesn't matter in the long run, as Elfstone pointed out, is simply that 2^(t-2) = 2^t/2^2 = 2^t/4, so it's only a quarter the size of the other formula but it still grows exponentially fast, so there always exists a sufficiently large t so that the worm reaches the other end of the rubber band.
|
