12 Oct
2000
12 Oct
'00
4:29 p.m.
On Wed, 11 Oct 2000, Trei, Peter wrote:
by a computer are the killers. Any problem which one computer can create, and solve, can also be solved by another.
Not true. One example from the theory of computation: given a finite set of 3x3 matrices, determine whether some finite matrix product of them equals zero (i.e. repetition and reordering is allowed). This is a noncomputable problem, even when we know that all such series can be computer generated and a given solution can be easily verified. Sort of cracked me when I first found it. Naturally this particular problem isn't suitable for human consumption, like the original mail required. Sampo Syreeni <decoy@iki.fi>, aka decoy, student/math/Helsinki university