16 - Algorithms

Summary

Basic Object: Graphs and Trees

Basic Goal: Computing the Efficiency of Algorithms

The end of the 1800s and the beginning of the 1900s saw intense debate about the meaning of existence for mathematical objects. To some, a mathematical object could only have meaning if there was a method to compute it. For others, any definition that did not lead to a contradiction would be good enough to guarantee existence (and this is the path that mathematicians have overwhelmingly chosen to take). Think back to the section on the Axiom of Choice in Chapter Ten. Here objects were claimed to exist which were impossible to actually construct. In many ways these debates had quieted down by the 1930s, in part due to Gödel's work, but also in part due to the nature of the algorithms that were eventually being produced. By the late 1800s, the objects that were being supposedly constructed by algorithms were so cumbersome and time-consuming, that no human could ever compute them by hand. To most people, the pragmatic difference between an existence argument versus a computation that would take a human the life of the universe was too small to care about, especially if the existence proof had a clean feel.