Quotes, citations, and the like are taken from: Newell, Allen, and Simon, Herbert A. Computer Science as Empirical Inquiry, 1975 ACM Turing Award Lecture, reprinted in Mind Design, John Haugeland, ed.:

The knowledge representation schemes we have looked at manipulate symbols in the computer.  These symbols are combined into even more complicated symbol structures.  The symbols are realizable in some physical structure (they exist on computers, and some correspond to physical entities).  Some of the symbols relate to the "outside world" in that they represent things like doors, or with the process of opening a door.  The computer, with these symbol representations and the algorithms for them, exist in a broader context (the world around us).

Some of these symbol structures are instructions for manipulating the set of symbols (i.e., a "program" or an "algorithm"

Much of what these computer programs do (given limited resources) can be viewed as "search"

Recall Turing Machines

Infinite tape

Finite (perhaps very large) set of states.

Set of states does not change over time

What is a Symbol?

Symbols designate objects

Symbols designate processes

Symbols designate expressions of symbols

Every process in the machine is designated by a symbol

Symbols

There are processes for creating, modifying, and deleting expressions

The number of expressions is essentially unbounded

A Turing Machine has a finite number of states

A native speaker can generate an infinite number of sentences.

Physical Symbol Systems

"A Physical Symbol System is a machine that produces through time an evolving collection of symbol structures"

Designation: Some expressions designate objects (system affects the object or "responds in ways depending on the object"

Physical Symbol Systems

Interpretation: Some expressions designate processes, and the PSS can carry out these processes.

Physical Symbol Systems exist in a larger context.

From Dawson, Page 23:

A PSS consists of

Far richer environment than a Turing Machine, but still equivalent.

The Physical Symbol System Hypothesis

Newell and Simon 1975

"A physical symbol system has the necessary and sufficient means for general intelligent action"

Sufficient:

We can in theory build a physical symbol system that exhibits intelligence.

An appropriately programmed computer can exhibit intelligent behavior.

Necessary:

Any system we might consider intelligent (including ourselves) is at root a physical symbol system.

At some level of explanation entities capable of intelligent action can be explained as physical symbol systems.

Evidence

Sufficiency - work in AI

Necessity - work in cognitive psychology (Newell and Simon)

Heuristic Search Hypothesis

"The solution to problems are represented as symbol structures. A physical-symbol system exercises its intelligence in problem-solving by search - that is, by generating and progressively modifying symbol structures until it produces a solution structure" (Newell and Simon)

The Hope:

General Intelligent behavior is a property of a sufficiently complex physical symbol system

A physical symbol system is computable

(Turing-Church) Anything computable is Turing-computable

The Hope

Anything Turing-computable can be implemented on a (sufficiently powerful, with sufficient resources) computer