|
|
Fri Sep 18 13:58:58 EDT 2009
The Computer Merit Badge: how I'd complete the requirements NOW;
Part 1
--
I have decided to begin a series where I take some of the re-
quirements of the Boy Scout of America's Computer Merit Badge,
and answer them knowing what I know now. Interestingly, I do not
believe I recieved the Computer Merit Badge as a Scout.
Requirement 1: Give a short history of computers. Describe the
major parts of a computer system. Give four different uses of
computers.
Given that this really has 3 parts, I'm going to break this up
into several postings.
A) Give a short history of computers
Instead of giving the same worn history or chronology of the de-
velopment of computer technology, I will take this as an opportu-
nity to provide some perspective on what a computer is and how
long humans have been dancing around the concepts involved.
Before I begin, here is some basics that have come to be known to
Computer Scientists and Applied Mathematicians (i.e., the origi-
nal Computer Scientists).
A "computer" can be view as a device whose "power" depends on if
it has memory and how it accesses this memory. This is important,
so I'll say this again. A computer's power (i.e., in terms of
*what* it can do, not how fast it can do it) is directly related
how it can recall things that it has seen before. It's all about
memory and how this memory can be accessed.
This dependence on memory can be conceptualized in 3 major ways.
1) A device has no memory. All responses to input are predefined
with respect to in what the "state" the system is at the time of
input. These devices are called "finite automata." Each machine
can recognize only certain "strings" of input. Strings are
grouped into languages, and the class of languages accepted by
these devices are called, "Regular."
2) A computing device that has what is referred to as a single
"stack" of (infinite) memory. It can remember things, but how it
can access this memory is constrained. In the theory, these ma-
chines are called "push down automata." The class of of languages
recognized by this machine is called, a "Context Free Grammar."
3) a. A computing device that has RANDOM ACCESS to its (infinite)
memory. In the theory, these machines are called, "Turing Ma-
chines." The class of languages recognized by this machine is
called, a "Universal Language."
3) b. A Turing Machine with a FINITE amount of memory (like your
desktop computer!) is not as powerful as a TM with infinite memo-
ry. Thus your desktop computer is, in the theory, actually a
"linear bounded automata." The class of languages recognized by
this machine is called, a "Context Sensitive Language."
What can these machines do? Well, without going into mind-melt
mode (if I have not done this to you already), here are some ex-
amples:
1) examples of finite state automata: simple elevators, simple
vending machines - basically anything that given some input
(i.e., a button press), the system performs specific action based
on a. it's current state (i.e., on what floor the elevator is)
and b. the input (i.e., to which floor the person wishes to go);
this model has far reaching uses in software and electronics.
2) examples of push down automata are largely found in in soft-
ware; they are used widely for the parsing of programming
lanaguages by compilers (more on these in requirement 2!).
3) examples of Turing Machines do not exist; they are theoreti-
cal, since it is impossible to have something that has an infi-
nite amount of memory.
4) examples of a linear bounded automata include most things
you'd consider a "computer" by modern standards, but more pre-
cisely it is a general purpose device that can execute a set of
instructions (i.e., a program) in a programming language that is
considered to be Context Sensitive (e.g., Assembly, C, Perl, Ja-
va, BASIC, PHP, etc).
Regarding the computation power of these machines, including mod-
ern computers, consider my following statement very carefully.
ELECTRONIC COMPUTERS ARE NO MORE COMPUTATIONALLY POWERFUL THAN
THEIR MECHANICAL ANALOGS. What does that mean!!? It means that a
computer is nothing more than a machine, and that any computer
constructed using electronics and a circuit board can be built
using mechanical parts. Clearly, the electronic computers will be
FASTER, but they are not more POWERFUL in terms of the kinds of
problems they can solve. To demystify the power of computers fur-
ther, there exist no program executable by a computer that can
not be done by a human being with a pencil and paper or by a me-
chanical device. Again, electronic computers are clearly FASTER.
But they are not more powerful.
In my next installment, I will tie together the historical sig-
nificance of what I've said about the power of a computational
device having nothing to do with how it is built - with sticks,
gears, and pullies - or with transistors and wires.
--
Powered by vee
Copyright © 2006-2010
|
|