[Lecture Notes by Prof Yuen and possibly others 2000-2001]


The Capable Computer
--------------------

Computers are everywhere because they are capable of doing things for us.
This section is to give you a general idea of their capability, in
particular to see that the work they do is both simple and complex, both
similar and different.

Let us start with the example of email. Someone in USA, say my son at 
Motorola Corp in Phoenix Arizona, sends me a message at the address
yuenck@comp.nus.edu.sg. His computer takes in a string of letters, and
passes it to my computer - Simple right? Just take some letters on one
side and reproduce it on the other side - but also complicated: how does
his machine over there know what to do with this string of letters? address
comp.nus.edu.sg? what is that? where is that? what action is correct to
deal with it?

Well his machine must ask another machine called the name serverr,
which says (to make a long story short) that any messages with address
...sg should be sent to a machine in Princeton, which has a satellite
line to Singapore. So the sender's machine sends the message to a bridge
computer that is responsible for Motorola's link to outside machines, so
that the message is passed to an AT&T machine in Phoenix and passes a
number of links till it reaches the Princeton machine, which sends it to a
Singapore machine responsible for the other end of the satellite line.
The Singapore machine, seeing the address ...comp.nus.edu.sg, knows that
the message should go to an SOC machine responsible for linking to the
outside, and the SOC machine delivers the message to my machine, which
stores it away in a mail file; when I log on to read mail, the mail
software shows me the list of mails in the file, and shows the new mail
on my computer screen if I select it to read.

So to do all this work, the various machines must all be linked together
with communication lines of some kind; this is done by engineering people,
and their job is to ensure that the same letters received at one end are
reproduced at the other end, quickly. Further, the machines must know what
to do for every individual message, "if x do y" "if a do b" etc. The right
piece of information must be at the right place, and a machine must know
where to find a piece of information and what to do with it. Sure email is
just taking letters in one side and putting them out on the other
side; but to do this correctly for the hundreds of millions of users
sending and receiving tens or hundreds of emails a day, the amount of
information needed to move every message correctly is very large, and that
is where the complexity comes from.

Now let us look at the example of using a bank account: depositing money
is just addition, and withdrawing is subtraction; very simple right? But
at any moment, thousands of customers of the same bank may be depositing
and withdrawing at hundreds of branches. The requests must be checked
against the correct accounts, quickly, and results returned to the
teller/customer. Just like email, messages (like "withdraw $100 from
account X") are moved from one place (teller' terminal or ATM machine)
to another (the computer containing the customer's account file), and
returned ("withdraw successful; your new balance is Y") to allow the
teller/ATM to hand out the $100 with the updated account book/ATM card.

So banking computers do some things that are very similar to email; that
is why lot of the same hardware and software would work for both; this is
one of the factors that make things economical. But there are also parts
that are very different, like teller terminal must be able to read the
magnetic strip on the account book/ATM card, do printing on the book,
count out money, etc, and have particular buttons for the teller/customer
to push. In computer talk, this is called the application or user
interface: the particular problem being solved or the person using it
requires a particular way of interacting with the machine.

Many applications of computers are similar. You are used to registering
for courses, or reserving library books, using a computer. For each
problem, the computer may be the same one, but it presents you with a
different user interface, because each problem requires different
information that has to be collected from you. After getting the
information (your name, matric no., the reference no. for the course/book
you want, etc), it passes the message from you to the machine containing
the relevant information (files showing all the courses and the current
enrolment situation, or the book catelog with the availability situation),
and makes the change you asked for, before sending you a reply message. So
you see again that the problem is similar to yet different from
banking or email, both in the user interfaces and in the information
kept in the machines for dealing with the problem.

Moving a bit further, look at MP3 music playing. Like the banks with files
of customer accounts and library with LINC database, the music companies
keep huge files of music; instead of words and numbers, the files contain
signals describing how to produce the sounds. When you send a request for
a particular music piece, the content of that file is sent into the
machine at that end and passed to the machine at your end like a very long
email. What is different is your machine knows how to read the signals
and produce the sound; in other words, a different user interface. (The
process, called digital to analog conversion, will be discussed later
in the course.)

Moving further still, look at a three dimensional walkthrough, such as 
what you experience in a video game: you are at a particular point in a
house/park/cave/etc, and looking left/right/up/down you see different
things; if you move, what you see changes. Is that still similar to the
other examples we talked about so far? Despite the change, the answer is
yes. The computer has a big file describing every part of the three
dimensional structure, and can mathematically work out a two dimentional
picture containing what a pair of eyes in a particular position within the
structure, looking in a particular direction, should see. The software
receives your position/direction, like the bank computer receiving your
withdrawal request, looks up and calculates the relevant information, and
returns information to the screen telling it what to show, just like the
bank computer returning your account balance, except the returned
message is a very long one in this case. The calculation of the scene 
and telling the screen how to show it are both very complicated, and
require a lot of knowledge of programming and 3-D graphics to understand
and do, but still the problem shares common features with other computer
applications and can run on the same machines.


The Intelligent Computer
------------------------

We learnt that computers can do email, library search, etc., because
(a) it can store a large amount of information (b) find a particular piece
of wanted information (c) move the information to where it is needed, very
quickly. Moreover, it can produce new information from old information
quickly, even when that involves quite complex changes, such as in a 3-D
walkthrough. These complex changes have to be specified exactly every step
by step; this is called an algorithm. The variety of complex algorithms
that we can invent dealing with complex information is where the
versatility of computers come from.

Specifying an algorithm is however a tedious and error prone task, even
for simple problems, and requires professional training and practice - You
might find this a surprising statement, since there are numerous users
of computers doing quite sophisticated work with little training, but this
is because professionals have already done the work to produce easy to
operate user interfaces that hide the complex algorithms beneath. A simple
job like word processing, email or web surfing invokes programs containing
thousands, sometimes more, lines of computer code, most of which written
long ago, carried from company to company, and repackaged into new
programs many times. The near mystical fear of the Y2K bug, which turned
out to be nowhere as serious as first thought, was due to the fact and
most of the old code is all but incomprehensible, and no one can tell
whether they contain parts that would treat 00 as 1900 or not.

To show a simple example, consider the problem of adding 10 integers 1 to
10. When still a primary school student, Gauss found the quick solution:

1+10 =11, 2+9=11, etc; 5 pairs together 55

A computer is however not an original thinker like Gauss. It would do the
sum like this:

        sum = 0
        i = 1
repeat: add i to sum
        add 1 to i
        i > 10 ?
        no -> repeat
        yes -> finish

Why? A computer is a machine with various boxes; one of these is the
memory box that contains all the data, which it can identify by name
(actually by addresses but we wont discuss such details here); the other
is the arithmetic unit which can receive data and produce results of
various operations like +, x, etc., but you first have to pull the data
out of the memory box and send them to the arithmetic box, and send back
the results. 

When you are limited to doing things this way, then you have
no choice but to adopt algorithms like the one above just to solve a
simple problem like adding 1 to 10. Furthermore, the basic machine
interface is very rigid: you have to specify the algorithm using the
particular language designed to describe how the data move back and forth
between the boxes. Learning to program requires both learning a language
and learning how to design algorithms for particular problems, each of
which can be conceptually quite difficult to get used to. 

So how did we manage to solve complicated problems with computers then?
First trick is to generalize: we can change the program to add integers
n to m by changing the program just slightly:

        sum = 0
        i = n
repeat: add i to sum
        add 1 to i
        i > m ?
        no -> repeat
        yes -> finish

We can then change the step size to any positive number x:

        sum = 0
        i = n
repeat: add i to sum
        add x to i 
        i > m ?
        no -> repeat
        yes -> finish

(supposed x is negative, or 0, what happens?) And we can also put in
various other things to make the program more "powerful". Gradually, we
produce a set of program templates, each of which can be set to do a
variety of slightly different things. 

Second, we can combine programs by using later programs to work on results
produced by earlier programs. If we can divide up a problem into many
components, some of which solved at the same time on separate machines,
and then combine the results using another components, we find that even
though each component is simple, the overall problem we have solved is
very complex. 

However, we dont always have working algorithms for all the problems we
want to solve, even some "simple" problems. For example, we humans can
recognize a face easily (babies recognize their parents at a few weeks
old), including photographs of faces which are actually very different
from the faces themselves: the photos are much smaller, flat rather than
3-D, black and white rather than coloured, and show the face at an earlier
time when the person was younger. What exactly are we recognizing that is
the "same"? Since we do not quite know, it has been quite difficult to
computerize such tasks, and the programs that have been put together for
such problems tend to work quite differently from humans.

On the other hand, there are some other "recognition" problems that are
much more solvable with computers, e.g., diagnosing a sickness or machine
failure is similar to yet different from recognizing a face. The difference
lies in it being more "knowledge intensive": it is possible to collect a
set of information from humans doing such work, and use these to work out
a procedure whereby the computer asks a series of questions and gathers a
set of data that can be matched against a known pattern. The knowledge or
expertise in the machine allows it to know "what questions to ask" and
"what to do with the answers". Software of this kind works a bit
differently from the 1 to 10 addition type of program, but the technology
for developing such software is readily available and reasonably
successful.