On Tuesday 06 January 2004 13:12, Michael B Greenwald wrote:
There are problems that are unsolvable in asynchronous systems, but solvable in synchronous systems. If you take the statement "within 24 hours" to mean that the system is broken up into discrete day-long intervals, then this problem becomes synchronous, and the race condition you worry about doesn't exist.
OK, so they must leave at sunup on the following day, also it must be taboo for anyone in any circumstance to mention the color of a dot on anyones head. If someone in the town says, "some of the town folks have blue dots", and all the town folk know who spoke this way and believe it, it is equivalent to a stranger saying it. Thanks for the observation about synchronous systems vs asynchronous. Maybe the physical world is really synchronous not asynchronous. There is some current evidence that time is discrete. Regards Otto otto@olympus.net
Tue, 6 Jan 2004 12:50:28 -0800 Otto Smith <otto@olympus.net>
....If the blue programs are are equally intelligent, then there is an apparent inconsistency since none can reach the conclusion first, yet if they are unequally intelligent, who leaves town first? ... My suspicion is that on carefull analysis this kind of problem might in reality fall into the undecidable class of problems and has no solution. My suspicion is that there really is no group of people (or automatons-programs) that could be built that could with confidence reach a conclusion and vacate the town. The problem of determining when another automaton may solve a problem of this sort, may be similar to deciding when a touring machine will stop when given an arbitrary program.
There are problems that are unsolvable in asynchronous systems, but solvable in synchronous systems. If you take the statement "within 24 hours" to mean that the system is broken up into discrete day-long intervals, then this problem becomes synchronous, and the race condition you worry about doesn't exist.
If there are N blue dots, then each of the blue programs knows that there are either N-1 blue dots and his is not blue, or there are N blue dots and his *is* blue (the truth). If there were N-1 blue dots, then the other blue programs would be trying to determine whether there were N-2 or N-1 dots. Once the "clock starts running" (after the announcement), then the N-1 blues would have left on the N-1st day. Once the N-1st day is complete, and no one has departed, then the N blue programs now know there are N blue dots and that they are blue and they have 24 hours in which to depart. There is no race condition, and it doesn't matter who figures it out first.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun