decoration decoration
Stories

GROKLAW
When you want to know more...
decoration
For layout only
Home
Archives
Site Map
Search
About Groklaw
Awards
Legal Research
Timelines
ApplevSamsung
ApplevSamsung p.2
ArchiveExplorer
Autozone
Bilski
Cases
Cast: Lawyers
Comes v. MS
Contracts/Documents
Courts
DRM
Gordon v MS
GPL
Grokdoc
HTML How To
IPI v RH
IV v. Google
Legal Docs
Lodsys
MS Litigations
MSvB&N
News Picks
Novell v. MS
Novell-MS Deal
ODF/OOXML
OOXML Appeals
OraclevGoogle
Patents
ProjectMonterey
Psystar
Quote Database
Red Hat v SCO
Salus Book
SCEA v Hotz
SCO Appeals
SCO Bankruptcy
SCO Financials
SCO Overview
SCO v IBM
SCO v Novell
SCO:Soup2Nuts
SCOsource
Sean Daly
Software Patents
Switch to Linux
Transcripts
Unix Books

Gear

Groklaw Gear

Click here to send an email to the editor of this weblog.


You won't find me on Facebook


Donate

Donate Paypal


No Legal Advice

The information on Groklaw is not intended to constitute legal advice. While Mark is a lawyer and he has asked other lawyers and law students to contribute articles, all of these articles are offered to help educate, not to provide specific legal advice. They are not your lawyers.

Here's Groklaw's comments policy.


What's New

STORIES
No new stories

COMMENTS last 48 hrs
No new comments


Sponsors

Hosting:
hosted by ibiblio

On servers donated to ibiblio by AMD.

Webmaster
Still just algorithms | 354 comments | Create New Account
Comments belong to whoever posts them. Please notify us of inappropriate comments.
Still just algorithms
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 | # ]

Groklaw © Copyright 2003-2013 Pamela Jones.
All trademarks and copyrights on this page are owned by their respective owners.
Comments are owned by the individual posters.

PJ's articles are licensed under a Creative Commons License. ( Details )