Author: Alberto Rezza
Date: 05:39:35 05/17/01
Go up one level in this thread
On May 16, 2001 at 19:12:23, Dann Corbit wrote: >Chess is finite. TSP is finite. Matrix multiplication is finite. All >algorithms are finite. Otherwise, they AREN'T algorithms. Come on, Dann. Termination of algorithms and finiteness of a game are two totally unrelated matters. Is that so difficult to understand? If chess is too much, try with tic-tac-toe. A few hundred nodes, and you cannot increase the depth anymore: all leaves are won, lost or drawn, there is nothing left to expand. It is finite, so it is O(1) time. And chess is the same, for the same reason. With matrix multiplication, after multiplying two nxn matrixes, you can always find two (n+1)x(n+1) matrixes to try. The algorithm WILL terminate, but it will take longer: for any time duration T, you can find an input large enough that it takes more than T to compute, so it is not O(1). Alberto
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.