Monday, September 20, 2010

Algorithms and Truth

Fixing a broken lamp
In an earlier post, I introduced the concept of algorithms as a way of solving problems using a step-by-step process.  Most of us understand algorithmic thinking when it is applied to everyday tasks.  Fixing a broken lamp is a good example of an algorithm, because it involves taking different paths, depending on the outcome of several questions.  A recipe is a simple form of an algorithm:
Sausage and Peppers
1 package of Italian sausage (mild or hot, your choice)
2 bell peppers (red, orange, yellow, green, your choice), sliced
1 sweet onion, sliced
1 Tbsp minced garlic
fresh basil (or dried)
2 Tbsp olive oil
1 28 oz can whole tomatoes
1 package angel hair or penne pasta

1. Cook the sausage whole, on medium heat, until browned, using 1 Tbsp of olive oil. Alternatively, broil the sausage in the oven.  Slice into pieces and reserve
2. In the same pan, cook the bell peppers, onion over medium heat using 1 Tbsp of olive oil, until onion is lightly browned.
3. Add the garlic to the pan and simmer until slightly browned.
4. Add the sausage back to the pan.
5. Puree the tomatoes by pulsing, so that there are still small chunks.
6. Add the tomatoes to the pan, along with the basil.
7. Simmer the sauce on medium-low until reduced and thickened, about 10 or 15 minutes.
8. Serve over angel hair or penne pasta, cooked to package instructions for al dente.

Algorithms are used in computer science to devise a method for a computer to solve a problem.  One of the classic problems that has been solved in many different ways is the task of sorting a set of numbers.  One solution is the quicksort algorithm, which looks like this:
function quicksort(array)
     var list less, greater
     if length(array) ≤ 1
         return array
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))
Quicksort Algorithm in action (Wikipedia)
The basic idea is this: (1) start with a list of numbers, (2) choose one number to be the pivot, (3) separate the remaining numbers into two lists, one with all the numbers smaller than the pivot, and one with all the numbers larger than the pivot, (4) repeat the quicksort algorithm on the list of smaller numbers, then on the list of larger numbers, (5) combine the results into a new list, with the sorted numbers less than the pivot, followed by the pivot, and then by the sorted numbers greater than the pivot.  This is illustrated at right.

One way of understanding Francis Bacon's Novum Organum is to view it as the development of a new algorithm for advancing scientific knowledge.  An illustration of Bacon's algorithm is found in the second part of Novum Organum, where he conducts an investigation into the form of heat.  He first lists the all the instances in which heat occurs, then lists all the instances in which heat does not occur, and finally lists the instances in which heat varies by degree.  Inductive reasoning can then be used to discover a law, based on direct observation of nature.

One of the advantages of algorithms is that they are easily compared.  Which recipe produces the best pizza?  Which sorting algorithm works fastest?  Which scientific method does the best job of discovering truth, and in which circumstances -- Aristotle's deductive reasoning, Bacon's inductive reasoning, or something else entirely?  What metrics do we use to even begin to answer this question?


Mike Lemon said...

Thank you for this post. I kept hearing algorithms and started to freak out. I had no idea what an algorithm was, but now that I know the concept, the word doesn't intimidate. Sorry I can't add to the conversation, but thanks anyways.

jakydigiciv said...

The word "algorithm" used to freak me out too. Then someone explained to me properly what I meant and I thought, "Oh. That's all it is? Well, that's a pretty easy concept. I've spent years thinking I was insufficiently smart and that's totally not worth it."

In any case, I'm a big fan of algorithms. Once a useful one has been discovered (for any situation), lots of opportunities open up to use it. Computers can do that, though. The tricky thing is coming up with a new algorithm, which as far as I'm aware, computers don't really have the capability to do at this point. That's why humans are still important to solving problems. Additionally, people who subconsciously (or, I suppose there are people who do this consciously too) develop algorithms for human relationships, but algorithms for people are frequently too complex for algorithm-oriented people to discover and/or apply properly to develop healthy inter-human relationships. It's an interesting concept.

Kevin said...

It's interesting that we use so many Algorithms in the world around us. Even our assignments can be thought of as performing Algorithms in a way. And for Thursday, our assignment is to read some from Diderot's encyclopedia, which can also be thought of as running an Algorithm to find information.

Daniel Zappala said...

I'm still waiting for someone to tell me whether they like my recipe!

Jake C said...

I like the idea that algorithms can be improved upon. for example the first computer that they built was massive an could only accomplish a very simple task. but as time goes on those algorithms build on one another and a computer can do more and more. the same goes for the algorithm of obtaining knowledge. just look at the renaissance and enlightenment. all these people building on one another. and since this open source software thing seems to be the hottest topic in this class the improvements of computer algorithms and the pursuit of knowledge would scarce be possible without many many eyes to look at them. i am seeing the advantages of "openness" more and more everyday. still not totally sold yet though.

Post a Comment