FOM: accessibility of "algorithm"

[Sam Buss]

   I basically agree with Joe Shipman's comments on the problems
students have with understanding the notion of algorithm.

   When I teach algorithms/Turing machines/automata to college juniors
who know how to program, the students are very ready to accept
the abstract notion of algorithm.  Once they see a few
programming techniques of Turing machines (e.g., once they
see an example of how to compare two strings on a one-tape
machine), they are happy to believe that a Turing machine
is as powerful as a general computation model.  BUT, the
students have a lot of difficulty understanding Church's
Thesis - mostly because they believe it is "obviously true"
and cannot understand that at one time there was any question
about how to define "algorithm" (and only 60+ years ago!).

   Perhaps this means that Church's thesis is no longer so important
from a foundational point of view.  However, I think this is one
of the important jobs of foundations: namely, to expose the basic assumptions
underlying thought and make them explicit; so in this respect,
Church's thesis exposes the now-"obvious" notion of algorithm.

 --- Sam Buss

P.S. As for high school students, the California schools
are quite backward and programming is not part of the
normal curriculum.  On the other hand, I ran the High School
Honors Contest some years ago and quite successfully used
problems about finite automata on the test.  Students
has to figure out how to read and draw finite state diagrams
in about 25 minutes, and a lot of them could do this.

P.P.S. In reply to:
> The students in that "Introduction to the University" course
> may have had trouble understanding computation with cellular
> automata, but practically all high schools teach computer
> programming nowadays and I can't believe that typical college
> freshmen, even today, don't understand what computer programming
> basically is.  (Even if they have not taken a programming
> course.)  The invariance of the notion of what is programmable
> is surprising and slightly harder to explain, but even this is
> not really essential for understanding a statement like "no
> computer program can identify which equations are solvable in
> integers".  -- Joe Shipman
>