Author: Robert Hyatt
Date: 07:21:06 05/12/01
Go up one level in this thread
On May 12, 2001 at 06:10:01, Graham Laight wrote: >On May 11, 2001 at 15:02:28, Robert Hyatt wrote: > >>On May 10, 2001 at 07:16:32, Graham Laight wrote: > >>>I find myself siding with Jesper here. >>> >>>Given application of the 50 move rule and draws by repetition (which I think is >>>sensible - if not strictly within the theoretical letter of the law), here is a >>>simple reason why eventually chess search stops being exponential. Simply put: >>> >>>Beyond a certain depth of search, the number of extra nodes to be looked at with >>>every additional search level will start to decrease, because an increasingly >>>high proportion of the search tree branches will terminate in ended games. >>> >>>Having said that, with up to 49 moves between each pawn push or piece taken, the >>>search tree is still going to be quite big - so while I agree with Jesper that >>>the tree will eventually start to thin out, it's not actually offering us the >>>prospect of solving chess by crunching out all possible games. >>> >>>-g >> >> >>If you want to use that definition, fine. But then answer the following: >> >>Name one _real_ application that is not O(1) by your definition. IE by "real" >>I mean a task that someone, some day, might want computed. It can't have >>infinite input or it is impossible to compute, for example. If you think you >>have one that has "unbounded but not infinite input" then post it. I'll bet I >>can prove that it is not "unbounded" at all. >> >>waiting.... >> >>Bob > >The "impossible" constraint makes it quite difficult - my 1st thought was for >computing Brownian motion! > >I think that the weather is finite and computable - the problem being that >weather forecasters are very bad at guessing how quickly clouds will move - >presumably because the input isn't good enough - you don't know the exact shape >of the cloud - or how the cloud droplets are going to form to make these shapes. > >Fluid dynamics is an interesting area. Turbulence, flow, droplets etc - all very >difficult. The problem here is that, in your simulation, you break the fluid >into small chunks - but when you simulate movement, you must stretch these >chunks, because you're not allowed to have holes in the fluid. This makes it >difficult for even the most sophisticated simulators to properly emulate even >relatively straightforward flows. > >The reason why IBM are building Deep Gene is because the simulation of emulating >protein folding turns out to be harder that expected. Seems like almost every >molecule in a folding protein can influence almost every other molecule during >the process. Even Deep Gene may not be powerful enough. > >Anyway - I've just constructed a problem which meets most of your criteria - not >100% sure it's 0(1) though. I call it the "Chain Letter" problem. > >Letters in hyphens (-&-) are variables > >A group of -N- people form a social club. > >Every hour, on the hour, the members send each other chain letters by e-mail. > >Each member will send -B- new messages on the hour, where -N- > -B- > 0, and >-B-is a random integer. > >For each message received, each member will forward it to -C- other members, >where -N- > -C- > 0, and -C- is a random integer. > >The process continues for -A- hours. > >Your job, as club "facilitator", is to provide the computer power necessary to >deliver all these messages. > >I think that you can clearly see that as -A- and -N- start to get large, >whatever computers you provide are soon going to be very busy. > >For example, if there are 101 members, each could possibly receive 100 messages >after the 1st hour, 10,100 after the second hour, over a million after the third >hour, etc. > >If even a small number of people formed such a club, it would soon overwhelm the >capacity of the entire internet. > >-g That is not unbounded. There are several bounds. 1. Bandwidth. Which is not infinite. 2. Storage to store the emails as they are sent. Since matter in the universe is finite, so is the storage capability. 3. Since the number of people is _also_ finite (only so many people can exist in the universe since they are composed of matter and matter is limited, this is also bounded. Hence O(1). Which is utter nonsense of course... :)
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.