Authored by: IANALitj on Sunday, November 25 2012 @ 07:53 PM EST |
Not all computer programs represent algorithms. To give just one issue
distinquishing between computer programs and algorithms, consider Fermat's Last
Theorem.
I could write a computer program that tests the values of x-to-the-n, y-to-the-n
and z-to-the-n, for all positive integers x, y, z, and n, with n greater than 2,
to see whether
x-to-the-n + y-to-the-n = z-to-the-n
I would use the four-dimensional analogue of Cantor's short diagonal proof, to
take up all values of x, y, z, and n, using successively greater values for all
four quantities. I would start with the one case where the sum is 6: x=1, y=1,
z=1, n=3. Then I would take all the cases with a sum of 7; there are only 4 of
them. There would be more cases with a sum of 8, but still only finitely many
and easily enumerated. Clearly, I could traverse all the countably infinite
possibilities for x, y, z and n.
According to Knuth (a sufficient authority to satisfy me), "An algorithm
must always terminate after a finite number of steps." Donald E. Knuth,
The Art of Computer Programming, Volume 1, Fundamental Algorithms (1968), page
4.
Until a few years ago it was not known whether my simple brute force method was
an algorithm for finding a counter-example to Fermat's Last Theorem. Now it is
known that my program would never terminate, and thus is not an algorithm.
However, there are still other easily-computed conjectures in the wild that
could be used instead of Fermat's Last Theorem to produce a computer program
that may or may not be an algorithm. Until the conjectures are cracked, nobody
will know the answer.[ Reply to This | Parent | # ]
|
|
|
|