Psy 416:
Reasoning and Problem Solving
Chapter 6: Information processing and computer simulation
E. Segal
1. Information
Information is probably best defined as a pattern that "rides" on matter
or energy. It is In information sciences patterns and structures are the
primary focus of study. N. Wiener argued that the concept of information
changed the view of causality in science. One entity can cause a change
in another with only an infinitesimal transference of energy. The causer
or controller does it with a signal rather than a push.
Information is a key to understanding much of the modern world including
communication and computation. Modern technological devices from telephones,
radios and computers have developed in great part because of informational
analysis.
The cognitive and informational sciences owe their very existence to the
study of information storage, transmission, and transduction. You have
heard of flow charts. In psychology, communication and computer science,
flow charts chart the flow of information.
2. Information processing
systems: Simon and Newell
An analysis follows what happens from the beginning of a task, such as
being given a problem to solve to the end with the problem solved. The
basic theory is that much of the sequence of events can be thought of as
the movement, storage and transformation of information.
Major components
receptors--senses
processors--transform,
interpret, integrate, select--attention, set, automatic and controlled
processes.
memories--long term,
short term, working, STSS.
effectors--muscles,
glands
Information enters the system via the receptors and
then is transformed and operated on by the processors, some intervening
outputs are temporarily stored and others are more permanently stored in
memory, outputs are generated which lead to behavior and interaction with
the environment. Historically, information processing psychologists have
used flow charts to identify the path of the information through the cognitive
processing system.
3. Computation theory
The concept of 'effective procedure' is one of the more
important concepts in the symbolic sciences, and one which is needed at
least on an informal basis in order to work within any cognitive science.
"An effective procedure is a finite,
unambiguous description of a finite set of operations. The operations must
be effective in the sense that there is a strictly mechanical procedure
for completing them"
Algorithm: An effective
procedure which is guaranteed to solve a problem.
Universal Turing Machine:
An particular abstract information processing system consisting of a linear
tape, a read head, and a finite set of states. It can read the tape for
either of two symbols, it can write either of the two symbols, it can move
one unit to either the left or right, and it can switch from one state
to another. That is all. Correctly programmed a Turing machine can solve
any problem for which one can specify an algorithm. There are, however,
unsolvable problems (Godel proved that)
There are other systems of effective
procedures, Church's Lambda calculus, and Emil Post's production
systems to name two, which using a different architecture, can solve
any solvable problem.
Two critical ideas that are necessary
to have computational systems serve as the basis of complex problem solving
are rules of choice and recursive rules.
Rules of choice are
rules in which the data are evaluated to decide what to do next.
Recursion rules are
rules in which the output of the rule may be used as an input to the same
rule either immediately or after other operations have occurred.
Church-Turing Thesis:
Any system which can solve arithmetic problems is logically equivalent
to any other system which can solve such problems.
4. Physical Symbol Systems
Newell and Simon's thesis: All intelligent systems
are Information Processing Systems whose implementations are Physical
Symbol Systems.
Humans and computers solve problems
in basically the same way. These are identified by Newell and Simon as
real systems that can do intelligent things such as reasoning, problem
solving, text comprehension, planning, etc. Newell (1981) identifies a
hierarchy of at least five descriptive levels within all PSSs: (a) the
device level, (b) the circuit level, (c) the logic level (d) the program
level, and (e) the PMS (Processor, Memory, Switch) level. Each of the levels
has its own principles and characteristics which are only partially constrained
at the other levels.
(a) The device level identifies the set of physical
units which must be duplicated and interconnected for a PSS. In a computer
this used to be tubes and wires, now it tends to consist of semiconductive
impurities on silicon chips. In organisms it consists primarily of neurons
and synapses.
(b) The circuit level consists of the flow of
matter or energy with particular voltages and resistances, or potentials
and neurotransmitters. In a PSS something has to move through the system.
(c) The logic level refers to structural and functional
patterns. Registers being on or off, the passing of bits
according to patterns of their combination, for example some units may
turn on only if all connecting units are on (AND gate), or a unit may turn
on only if only one of several connecting units is on (XOR (exclusive or)
gate).
(d) The program level contains data structures,
symbols, addresses and programs. Symbols (structured patterns) are stored
in accessible locations, and there are programs to retrieve information
(identify and possibly duplicate subpatterns) and operate on it according
to some principle. The result of that operation may be the addition of
new data to the data structure or some external output, or both.
(e) The PMS level is the functional level at which
intentions, plans, and purposes are realized. "Here there is simply a medium,
called data or information, which flows along channels called links and
switches and is held and processed by units called memories, processors,
controls, and transducers."
5. Analysis of problem solving
from an Information Processing perspective:
Newell and Simon's analysis
1) Identifying the problem space. The first stage
of an analysis of a problem is to identify the initial and goal states
(Newell & Simon, 1972). These two states define the boundary of the
problem space. The larger the "distance" between the two states the larger
the problem space.
2) Identifying some of the intermediate states
between the initial and goal state. Only for trivial problems can the solver
go directly from the initial state to the goal state. There are usually
going to be relatively stable describable intermediate states which need
to be reached. Both the problem solver and the analyst may need to know
of these.
3) Identifying what needs to be done; the "moves,"
which enable the problem solver to get from one state to another. In order
for a problem to be solved there has to be some procedure by which the
situation is transformed from one state to another.
4) Identifying the resources, e.g., knowledge,
skills, materiel, personnel and time, needed to execute each of the moves.
What is needed in order to reach each of the states from the immediately
previous state?
David Marr's approach: There are three stages of analysis.
1) Computation. The problem solver must analyze
the task that needs to be done rather carefully. This requires an analysis
of the specific parts. What are the inputs to the problem? What are the
relations between the parts?
2) Algorithm (and representation). The second
task for the problem solver is to specify an effective procedure that one
can carry out in order to achieve the goal of the task. This requires a
specific characterization of the sequence of operations that operate on
a given data base; if the sequence is followed, it will lead to a solution
of the problem.
3) Implementation. This requires identifying a
set of physical objects which can carry out the algorithm automatically.
Strategies: Trial and error, Hill climbing, Means-ends
analysis, subgoals, goal stack, forward chaining, structural analysis,
Content: Some people can use logical forms; some evaluate
with the content, probably trying to understand the picture from a realistic
model; the beliefs of a reader and her emotions often interfere with logical
analyses. Models often have dynamic and causal relations as well as structural
or logical ones. The pragmatics of the situation often interferes with
the analysis. The topics of the premises and the feelings about the terms
used, e.g. large and small, better and worse, are treated differently.
Attempts to transform the presented information to one that is easier for
the person to deal with may not be done correctly. We act rational to the
extent that we do things that seem to have worked before; we use our knowledge
base and expectancies.
References
Marr, D. (1982). Vision. San Francisco: W. H.
Freeman.
Newell, A. and Simon, H. A. (1972). Human Problem
Solving. Englewood Cliffs, NJ: Prentice Hall.
Penrose, R. (1989). The Emperor's New Mind. New
York: Oxford University Press.
Segal, E. M. (1994) Archaeology and Cognitive Science.
In C. Renfrew and E. Zubrow (Eds.) The Ancient Mind: Elements of Cognitive
Archaeology, Cambridge: Cambridge University Press.
Shannon, C. E. and Weaver, W. (1949). The Mathematical
Theory of Communication. Urbana, IL: University of Illinois Press.
Simon, H. A. (1969) The Sciences of the Artificial.
Cambridge MA: MIT Press.
Wiener, N. (1948). Cybernetics. New York: Wiley
Psy 416 Syllabus