CPSC 120, Spring 2002                    Information for the Second Test
------------------------------------------------------------------------
   The second test for this course will be given in class on Wednesday, 
March 20.  The test covers Chapters 4 and 5, plus Sections 1 and 2 of
Chapter 6.   Labs number 6 and 7 and the "Giant Brains" video are also
part of the material for this test.  However, the test will have no
questions about BNF or about Web pages, and I will not ask you to PROVE
that the Halting problem is unsolvable.
   You can expect some definitions and short answer questions, as well
as a few longer essay questions.  There will also be questions on Turing
machines and on programming in xTurtle.  You might be asked to write a
program or to design a Turing machine.  You might be given a Turing
machine or program and asked to explain what it does.
   Here is a list of some of the most important terms and ideas that
you should be familiar with:

         computational universality
         equivalence of different kinds of computers
         simulation of one computer by another
         the Church-Turing thesis
         Turing machines
         tape, cells, states, and symbols of a Turing machine
         how a Turing machine computes
         describing a Turing machine with a table of rules
         code number of a Turing machine (using a T.M. as data for another T.M.)
         unsolvable problems
         the Halting problem
         philosophical implications of all this

         Universal machines       "Human Computers"
         Charles Babbage          Ada Lovelace
         Analytical Engine        Jacquard Loom
         Eckert and Mauchly       Enigma Machine, codes, and code-breaking
         ENIAC                    von Neumann machine
         General-purpose, electronic, stored-program computers

         Operating system         Bus
         Memory-mapped I/O        Device driver
         Interrupts               Configuration of a computer at start-up
         Interrupt handlers

         Information Age          Computer privacy issues
         Cyberspace               Computer databases
         De-skilling

         programming              declaring variables
         syntax                   assignment statement
         semantics                input/output
         variables                control structure
         subroutines              loops and branches
         parameters               turtle graphics
         
         From the xTurtle programming language:
            DECLARE, LOOP, EXIT, and IF statements
            the assignment operator, :=
            expressions such as  x*(x+1)  and  sqrt(distance)
            forward, turn, back, face, moveTo,
            PenUp, PenDown, TellUser, AskUser, rgb