![[home-Z-G-14.jpeg]](home-Z-G-14.jpeg)
|
Here are some interesting pages on Fibonacci numbers: Ron Knott's web site on the Fibonacci numbers, the Golden section and the Golden string, and Jim Loy's Fibonacci web page.
If you're interested in the history of computing, you might want to visit the web page on Alan Turing maintained by Andrew Hodges, the author of Alan Turing: the Enigma [Hodges1983]. Find out what the halting problem has to do with mathematician David Hilbert's Entscheidungsproblem, one of 23 mathematical challenge problems that Hilbert proposed to help direct mathematical research in the 20th century.
In the following lectures, I've drawn on examples from Martin Davis's The Universal Computer [Davis2000] and David Harel's Algorithmics [Harel1987].
Lets start by doing some simple analysis of algorithms. Suppose you need to write a program to determine if a name is in a sorted list of names. This is like looking up a word in a dictionary except that there are no conveniently marked sections containing all words beginning with A, B, C, etc.
You could, of course, start at the beginning and compare each name against the name you're looking for until you either find the sought after name or you reach the end of the list. This is called linear search and in the worst case it will require as many comparisons as there are names in the list.
As an alternative method of searching, you could proceed as follows: jump to the middle of the list; if the name you're looking for is the same as the name in the middle of the list then you're done; if the name you're looking for appears alphabetically earlier in the list than the name in the middle, then recursively apply yourself to the first half of the list; if the name appears later, then apply yourself to the latter half of the list. This is called binary search; simulate this method in searching the following list for "candace":
"albert" "anisa" "aron" "bryant"
"caitlyn" "candace" "charles" "chris"
"christine" "damien" "danielle" "eliot"
"erika" "gloria" "harry" "jen"
"joe" "jonathan" "kalin" "leah"
"luke" "mark" "maryam" "matt"
"michelle" "nick" "paul" "sarah"
"seema" "stacy" "susannah" "tracy"
What is the worst case number of comparisons for binary search? Note that at each iteration you make one comparison and divide the list in half, so that each recursive application works on a list of half the size as the previous application. How many times can you divide 2 into a number and end up with a number greater than 1? The answer of course is the logarithm of the number base 2.
So which algorithm is better, linear search or binary search? The following plot illustrates how the number of comparisons for the two algorithms grow as a function the length of the list:
In[1]:= <<Graphics`MultipleListPlot`
In[2]:= MultipleListPlot[
Table[i, {i, 1, 32}],
Table[Log[2,i], {i, 1, 32}],
PlotJoined -> True] ;
|
|
The case for binary search should be pretty convincing if you're only concerned about the number of comparisons. But what about all the other operations involved in binary search? Let's take a little closer look at the two algorithms implemented in scheme. First, we'll implement an iterative version of linear search using vectors (arrays) instead of lists (as an exercise, write a recursive version):
(define (linear-search vec item equal?) (do ((i 0 (+ i 1)) (found #f)) ((or found (= i (vector-length vec))) found) (if (equal? (vector-ref vec i) item) (set! found #t))))
Create a simple test set:
> (define names (list->vector '("albert" "anisa" "aron" "bryant")))
Try it out:
> (linear-search names "albert" string=?) #t > (linear-search names "alice" string=?) #t
Next implement binary search as a recursive procedure:
(define (binary-search vec item less?) (aux-binary-search vec item 0 (- (vector-length vec) 1) less?)) (define (aux-binary-search vec item start stop less?) (if (< stop start) #f (let* ((midpoint (quotient (+ start stop) 2)) (midvalue (vector-ref vec midpoint))) (cond ((less? item midvalue) (aux-binary-search vec item start (- midpoint 1) less?)) ((less? midvalue item) (aux-binary-search vec item (+ midpoint 1) stop less?)) (else #t)))))
And run some sanity checks on the implementation:
> (binary-search names "alice" string<?) #f > (binary-search names "anisa" string<?) #t
Now take inventory of the operations performed by each of the two algorithms. Which algorithm is better? The answer may not be entirely one sided. It could be that one algorithm will do better in some contexts but not in others; if so, identify the cases in which each algorithm excels.
Here's another example: Suppose that you want to compute the minimum and the maximum of a list. Here's pseudo code for how you might compute the minimum of a list of items:
simple-min items min = first item in items for each item in rest of items if item < min then min = item
Ditto for computing the maximum of a list of items:
simple-max items max = first item in items for each item in rest of items if item > max then max = item
Here's the most obvious way of computing both the minimum and the maximum:
simple-min-max items simple-min items simple-max items
We can be little more clever and only iterate over the list of items once:
combined-min-max min = first item in items max = first item in items for each item in rest of items if item > max then max = item if item < min then min = item
Or we can be downright devious and do a little preprocessing of the list:
tricky-min-max items
mins = ()
maxs = ()
for each consecutive pair of items in items
if first item in pair > second item in pair
then add first item in pair to maxs
add second item in pair to mins
else add first item in pair to mins
add second item in pair to maxs
simple-min mins
simple-max maxs
In this lecture, we consider one particular limitation of computation, namely our ability to predict the behavior of programs. This brief foray into theoretical computer science concerns a problem with a long and interesting history in mathematics. It's called the halting problem and it concerns the question of whether there exists a mechanical procedure (a computer program) that can be used to determine for any program and any input whether or not that program will halt when run on that input.
Consider the following program for any integer input n:
while ( n != 1 ) {
if n is even
then n = n / 2 ;
else n = 3n + 1 ;
}
Or, if you prefer, in Scheme:
(define (steps n) (if (not (= n 1)) (steps (if (even? n) (/ n 2) (+ 1 (* n 3))))))
Nobody knows whether steps terminates on all positive inputs though quite a few mathematicians have tried to prove this. No one has been able to find a counterexample, but then what would it mean to find a counterexample. Lets take a look at a few examples:
In[1]:= Step[n_]:=If[1==n, 1, If[EvenQ[n], n/2, 3n+1]]
In[2]:= ShowSteps[n_, m_] :=
Block[{i = n},
ListPlot[Table[i=Step[i], {m}],
PlotJoined -> True]]
In[3]:= ShowSteps[512,200] ;
512 is a power of two, and so, not surprisingly, steps will terminate very quickly on this input as shown in the following graphic:
![[home-Z-G-15.jpeg]](home-Z-G-15.jpeg)
|
It's trivial to prove that steps will terminate on an integer corresponding to an integer power of two, but what about other inputs? How about 1 plus an integer power of two?
In[4]:= ShowSteps[513,200] ;
It takes several more steps, but it terminates nonetheless:
![[home-Z-G-16.jpeg]](home-Z-G-16.jpeg)
|
We can increment the input one more time:
In[5]:= ShowSteps[514,200] ;
It takes a little longer but again it terminates:
![[home-Z-G-17.jpeg]](home-Z-G-17.jpeg)
|
Even for relative simple programs involving integer inputs it's difficult to predict their behavior. But that doesn't mean it's impossible. How can we show that there is no program that can predict the behavior of an arbitrary program on an arbitrary input? We're going to proceed using proof by contradiction. We'll assume that such a program exists and then we'll show that this assumption leads us to a contradiction.
In the following presentation, P, Q and S are programs and X represents a possible input to a program. Since programs are just strings of symbols they can be used as inputs to programs. By way of proof by contradiction, let's assume that there exists a program Q defined as follows:
Define Q(P,X) as follows: If P(X) halts, then return YES, otherwise return NO.
Now we define another program S that uses Q as a subroutine and that definitely does not halt on some inputs:
Define S(X) as follows: If Q(X,X) = Yes, then loop forever, otherwise terminate.
Suppose that we apply S to itself as in S(S). First, suppose that S(S) terminates; but this can't be since the only way for S(S) to terminate is for Q(S,S) to return NO which indicates that S(S) doesn't terminate. Then suppose that S(S) doesn't terminate; but this can't be either, since if S(S) doesn't terminate that means that Q(S,S) must have returned YES which indicates that S(S) does terminate. Since in either case we arrive at a contradiction, this leads us to reject our initial assumption, namely that there actually is a program that can determine for any program and any input whether the program will halt on that input.
If the recursive, self-referential nature of the above proof bothers you, there are other proofs that avoid this or at least make it less obvious. In any case, the basic result that the halting problem is not decidable is well established mathematically and appears to be a fundamental limiting characteristic of computing. You can use the undecidability of the halting problem to prove the undecidability of other problems using a method called reduction. For example, you can prove that the verification problem (the problem of deciding whether an arbitrary program solves a given algorithmic problem such as the problem of sorting lists) is undecidable, by showing that if you could solve the verification problem then you could solve the halting problem. Reduction is powerful mathematical idea that is used often in theoretical computer science.
The undecidability of the halting problem was first proved by Alan Turing in 1936. To construct his proof, Turing developed a formal model of computation that involved an abstract computing device now called a Turing machine. Here's a graphic depicting a basic Turing machine:
![[home-Z-G-18.jpeg]](home-Z-G-18.jpeg)
|
And here are the main features of a Turing machine:
a finite alphabet of symbols; in this case 0, 1 and #,
a finite set of states that the machine might be in; for example, a machine might have the set of three states: moving forward looking for a #, moving backward looking for a 1, and done,
an infinite tape arranged as a sequence of locations each capable of recording a single symbol,
a read-write head capable of reading the symbol written on the tape at the location under the head or writing a symbol at the location under the head, and
a controller consisting of a finite set of rules each of which can, depending on the current state and the symbol written on the tape under the read-write head, change the current state to be a new state, write a new symbol at the location currently, and move the tape forward or backward under the head.
Analyze the three algorithms, simple-min-max, combined-min-max and tricky-min-max, described in Section and characterize their strengths and weaknesses. If there is no clear winner, provide examples of cases in which each algorithm performs best. Why might you want to test your conclusions by implementing your algorithms and testing them on real data? How would you go about such testing?
See if you can design a set of rules as described in Section implementing a Turing machine that finds each sequence of three consecutive 1s on its tape and replaces the 1s in the sequence with #s. Begin by assuming that you know that there are no such sequences to the left of the starting location on the tape. Then design a controller that will eventually find and replace all such sequences no matter where they appear on the tape. I've provided the Scheme code for a Turing machine simulator if you want to test your machine. I'll talk about the syntax used by the simulator in class.
In Turing's proof of the undecidability of the halting problem, he encoded Turing machines as numbers. Kurt Gödel used a similar technique in his proof of the incompleteness of all formal systems capable capturing arithmetic (see Chapter 12 in Talking With Computers). Devise a mechanical strategy (a program) for transforming any Turing machine into a number and then transforming it back again.
In the description of the more efficient algorithm for computing nth Fibonacci number, there was a bug in the for loop. Here is the buggy version:
for i = 3 step 1 until n do
begin
temporary := penultimate +
penultimate;
penultimate := ultimate;
ultimate := temporary;
end ;
And here is the corrected version:
for i = 3 step 1 until n do
begin
temporary := ultimate +
penultimate;
penultimate := ultimate;
ultimate := temporary;
end ;
Download all the code fragments in this chapter as a file in zip format.