Algorithm 版 (精华区)

发信人: ssos (存在与虚无·守拙), 信区: Algorithm
标  题: Problems and Projections in CS for the Next 49 Ye
发信站: 哈工大紫丁香 (2003年07月27日11:18:03 星期天), 站内信件

Problems and Projections in CS for the Next 49 Years

JOHN MC CARTHY
Stanford University, Stanford, California


Projection 50 years ahead is difficult, so I have eased my problem by
offering problems and projections for only 49 years. My projections
concern areas in which I have worked---artificial intelligence,
mathematical theory of computation, and computer systems. However, I
am surely not uptodate in any of these areas, so some of what I
project for the future may have already happened. I also talk about
the problems caused by the way computing and computer science are
practiced. We shouldn't exaggerate. The computer has caused big
changes in society, but these probably aren't as great as those caused
by the automobile.

The future is a continuation of the past, so we treat progress in
areas of computers and computer science as a continuation of their
histories.

1. The Personal Computer.

Let's begin by dating some facilities provided by com puters. In each
case the first date is when some people had the facility and the
second date when it was widespread.

1.1 Computer Cost of Writing and Email becomes Marginal.

By the late 1970s for some people and by the 1990s for almost all,
computer power for writing and for email did not have to be rationed.

1.2 Online All the Time at Home or at Work.

For a few (me) this started in 1968. By the 1990s, it was
widespread. The obvious culmination is that via a computer attached to
clothing or even built into the body, one will be online all the
time. It seems to me that the main payoff has already been achieved
with computers at home and in the office. The additional time a person
spends doing something with a computer through having it all the time
will be a small fraction of what he is doing already.

1.3 Email to Worldwide Destinations. 1970 to 1990s

1.4 Point and Click. 1980s.

1.5 Pocket Computer. 1990 to ?.

They aren't good enough for me yet. Surely we'll soon have rollable
pocket displays or head mounted displays good enough so that one can
wear them continuously. Having the computer facilities of one's desk
computer or laptop always at hand will be nice, but it will be a minor
Author's address: John McCarthy, Computer Science Department, Stanford
University, Stanford, CA 94305. email: jmc@cs.stanford.edu. url:
http://wwwformal.stanford.edu/jmc/.  improvement, because the reason
one is away from one's computer is to engage in some noncomputer
activity.

1.6 Online Buying and Selling via the Web. 1990s.

This has a lot further to go.

1.7 Search Engines. 1980s to present.

Google is the first reasonably adequate web search engine. It can't
answer questions but can often find an adequate humanreadable source
of information.

In several important respects, the use of computers is more difficult
than it was in the 1970s and 1980s. The complexity of basic facilities
like editors and operating systems and application programs has grown
now that limitations on RAM and disk have enormously relaxed.

Point and click has made it very difficult, even for programmers, to
customize their environments. It has encouraged the authoritarian
tendencies of people who design systems for other people to
use. Another difficulty arises from the Microsoft and Apple basic
software being proprietary and secret. Linux has made a minor
improvement. Now the ordinary computer user needs the services of
system administrators who do no programming but know how the
facilities are connected together.

Perhaps this situation can be relieved by programs that can understand
the features of system programs and can connect them in order to
achieve goals specified in interaction with the user. Doing this right
involves some AI but much less than humanlevel AI.

Here are some areas with problems to solve and opportunities for
progress

2. Programming Languages.

In some important respects, recently developed languages, for example,
Java, are a step backward from Lisp. For example, while Java does
include automatic garbage collection (which its ancestor C++ did not),
it still doesn't include functions as firstclass objects (like Lisp
lambdaexpressions); these facilitate the creation of programs which
themselves inspect, synthesize, or otherwise manipulate programs [and
this has many important applications]. A Lisp program can look at its
own internal structure and modify itself or create new Lisp program
and interpret it right away. A Java program could modify itself at run
time only by reference to the byte code, not the source code. Lisp
also benefits from its in ternal form being list structure with the
lead word saying what the expression is, for example, an assignment
statement is (setq ...). To recognize an assignment statement, a Java
program must search for =. The Java program can also have used a Java
parser to parse itself into a suitable data structure.

In the next 49 years, programs that extend themselves at run time will
become important.

I see opportunities for improvement in regarding inputoutput as
consisting of speech acts. Thus, computers can make requests or
promises to people or other computer systems. They can also ask
questions and give truthful and responsive answers to the questions.

The proper performance of speech acts gives new specifications for
programs. For example, we can ask whether a program keeps its promises
or at least intends to keep them. The speech acts can be represented
in machines as strings, or as XML, or (better) Lisp Sexpressions, but
they will have an abstract syntax and semantics at a higher level, and
promise (proposition, person) can be a program statement meaning to
promise to person that propostion will be true. See
http://wwwformal.stanford.edu/jmc/elephant.html for some ideas that
are still not at the level of concrete proposals.

3. Mathematical Theory of Computation.

The mathematical relations of computer programs, computable functions
and data structures.

3.1 Computability and Computational Complexity.

This is the one area in which computer science has developed deep
mathematical questions, for example, P = NP. I trust others will
characterize what may be expected from it in the next 49 years.

3.2 Channel Capacity?

Here's a problem whose solution would be as impressive as the
discovery of NPcompleteness: Is there a computational analog of
Shannon's channel capacity theorem for communication? Shannon's
theorem says that it is possible to transmit information over a
communication channel at a rate arbitarily close its channel capacity
with an arbitrarily low probability of error. A corresponding theorem
for computation would say approximately that a computer of speed V
would be able to do a computation of size X in time X/V given enough
memory.

3.3 Proving Correctness of Computer Programs.

In principle, noone should pay money for a computer program until its
specifications are expressed formally and the program is proved to
meet them and the prove is mechanically checked. Considerable progress
was made in the 1960s and 1970s, the outstanding achievement being the
BoyerMoore interactive theorem prover.  While progress continues, it
has been slowed by demands for shortterm payoffs.

Today there is already great emphasis on computer programs that
interact with people or other programs. Therefore, specification and
verification of such programs will become increasingly important. As
early as the 1970s, there was work on specifying text editors and
proving that they met their specifications.

The inputs and outputs of interactive programs are often well regarded
as speech acts as discussed in Austin [1962], Searle [1969], and
McCarthy [1996]. Speech acts include promises, requests, acceptances
and denials of requests, questions, answers to questions, and
pronouncements. Each of these, as discussed in McCarthy [1996], has
conditions for its correct execution, e.g. promises should be kept and
answers to questions should be true and responsive. These aspects of
programs will become increasingly important.

4. Artificial Intelligence.

The long term goal of artificial intelligence research should be
humanlevel AI, that is, computer programs with at least the
intellectual capabilities of humans. There are two main approaches to
seeking this goal.

The biological approach builds agents that imitate features of the
physiology or psychology of humans. Most cognitive science agents
imitate humans at the psychological level; connectionist systems and
their neural net relatives imitate at the physiological level.

For progress, the biological AI researchers need to figure out how to
represent facts independent of their purpose, to make systems capable
of sequential behavi or and to figure out what information to build
into their systems corresponding to the rich information that human
babies are born possessing.

The engineering approaches to AI regard the world as presenting
certain kinds of problems to an agent trying to survive and achieve
goals. It studies directly how to achieve goals. The logical approach
is a variety of the engineering approach. A logical agent represents
what it knows in logical formulas and infers that certain actions or
strategies are appropriate to achieve its goals.

The logical agents of the next 49 years need at least (1) continued
existence over time, (2) improved ability to reason about action and
change, (3) more elaboration tolerant formalisms, (4) the ability to
represent and reason about approximately defined entities, (5) enough
selfawareness and introspection to learn from the successes and
failures of their previous reasoning, (6) domain-dependent control of
theorem provers and problem solvers, and (7) identifying the most
basic commonsense knowledge and getting it into the computer.  This
must include knowledge that people use without being able to formulate
it verbally.

The classical AI problems---the frame problem, the qualification
problem and the ramification problem [Shanahan 1997]---have been
solved for particular for malisms for representing information about
action and change. However, these currently known representation
formalisms are unsatisfactory in various respects.  Improved ways of
representing action and change may present new versions of the frame,
qualification and representation problems.

It's a race to humanlevel AI, and I think the logical approach is
ahead. Why?  The logical approach to AI has faced and partly solved
problems that all approaches will face sooner or later. Mainly they
concern identifying and representing as data and programs information
about how the world works. Humans represent this information
internally, but only some of it is verbally accessible.  The logical
approach also has the advantage that when we achieve human-level AI we
will understand how intelligence works. Some of the evolutionary
approaches might achieve an intelligent machine without anyone
understanding how it works.

What are the problems faced by logical AI? Here are a few.

4.1 Facts about Action and Change.

This has been the major concentration of work in logical AI. Present
formalisms are pretty good for representing facts about discrete
sequences of actions and their consequences. Programs exist for the
automatic translations of planning problems so described into
propositional theories, and the propositional problem solvers are
often adequate to solve the problems. The situation is not so good for
continuous change, concurrent events, and problems involving the
actions of several agents. We can hope for progress in the next 50
years.

4.2 Elaboration Tolerance Including the Frame Problem.

Existing AI systems, including both logical and biological, are
extremely specialized in what in formation they can take into
account. Taking into account new information, even information not
contradicting previous knowledge, often requires rebuild ing the
system from scratch. Logical AI has studied elaboration tolerance, a
special cases of which is the presented by the frame problem and the
qualifi cation problem. The frame problem involves the implicit
specification of what doesn't change when an event occurs, and the
qualification problem involves elaborating the sufficient conditions
for an event to have its normal effect.  [Shanahan 1997] treats
elaboration tolerance and there is also my
http://wwwformal.stanford.edu/jmc/elaboration.html.

4.3 Nonmonotonic Reasoning.

Humans and machines usually reach conclusions on the basis of
incomplete knowledge. These conclusions may change when new knowledge
becomes available. Probability theory is applicable to a part of the
problem, but more general nonmonotonic logics seem to be also
required.

4.4 The Three Dimensional World: Approximate Knowledge.

The knowledge available to a person or robot of its three dimensional
surroundings and of the objects it needs to manipulate is almost
always very approximate, though sometimes precise geometric models
like rectangular parallelepiped approximate real objects well
enough. Logical AI needs a general theory of approximate objects.

4.5 The Relation between Appearance and Reality.

We and any robots we may build live in a world of threedimensional
objects built up from substances that are, in turn, made of
molecules. Our direct information about this world comes directly from
senses like vision and hearing that only carry partial information
about the objects. We, even babies, are built to infer information
about the three dimensional objects from observations and from general
information about what kinds of objects there are.

Machine learning and most AI have treated classifying appearances but
don't go beyond appearance to the reality. I have a puzzle about this
(http://www formal.stanford.edu/jmc/appearance.html). I think the
relation of appearance and reality will be an important topic of AI
research in the next 49 years.

Logical AI has faced the above phenomena. Other approaches haven't
faced them explicitly. Maybe it will turn out that they don't have to,
but I have seen no arguments to that effect.

My views on many of the specific problems are in articles published in
various journals; almost all are to be found on my web page
http://wwwformal. stanford.edu/jmc/. There is no complete summary,
but http://www formal.stanford.edu/jmc/whatisai.html and
http://wwwformal.  stanford.edu/jmc/logicalai.html express the
logical AI point of view.  [Shanahan 1997] covers much of the logical
AI approach.

No approach is close to humanlevel AI and or within development
range. No one can convincingly say that given a billion dollars he
could reach humanlevel.  A critical level of AI will be reached, as
Douglas Lenat pointed out, when an AI system has enough basic common
sense information to be able to get more information by reading books.

Humanlevel intelligence is a difficult scientific problem and
probably needs some new ideas. These are more likely to be invented by
a person of genius than as part of a Government or industry
project. Of course, present ideas and techniques are sufficient for
many useful applications.

Still we can ask for a subjective probability that humanlevel AI will
be reached in the next 49 years. In the past, I have said that
humanlevel AI will take be tween 5 and 500 years. I'll guess 0.5
probability in the next 49 years but a 0.25 probability that 49 years
from now, the problems will be just as confusing as they are today.

4.6 What if We Get HumanLevel AI

in the Next 49 Years? The current speculation about the consequences
of getting humanlevel AI is mostly beside the point, because it
concentrates on the possible personalities of the intelligent agents.
Present ideas about what humanlevel AI will be like seem to come from
sciencefiction. Consequently discussions of policies concerning AI are
presently beside the point.

Because of the speed of computers, qualitatively humanlevel AImeans
quantitatively superhuman AI. Its immediate applications will be to
get advice relevant to decisions of what to do. Even here the
speculation, especially science fiction, is beside the point. In the
typical story, the human asks what to do, the machine answers, and
taking the machine's advice has unexpected and unpleasant
consequences. The proper use of an AI advisor is to ask it the
consequences of many possible courses of action and to give the
reasoning leading to the machine's opinion.

The main danger is of people using AI to take unfair advantage of
other people.  However, we won't know enough to regulate it until we
see what it actually looks like. I would hate to see the American
presidential candidates in 2004 asked for their positions on AI.

5. Quantum Computers.

I believe they will be made to work. There are many physical phenomena
being tried and the discovery of quantum error correction makes
getting a general quantum computer a finite task. On the other hand,
there is still only Shor's factoring algorithm as an example of a
spectacularly useful quantum algorithm. The next 49 years will surely
tell us what quantum comput ers are good for. I'll conjecture that
factoring will turn out to be a paradigmatic example.

6. Economics of Information.

Many costeffective improvements in the way information is handled are
not done, because society is not organized to pay for them
properly. We can hope for improvements in economic organization of in
formation in the next 49 years. Here are some examples.

(1) Since about 1970, it has been economically feasible to put the
world's lit erature, approximately the U.S. Library of Congress, on
line and make it available worldwide. It is now rather cheap, but John
Ockerbloom's library catalog www.digital.library.upenn.edu lists only
about 20,000 freely available books. The situation was made worse by
the extension of copyright from 75 to 95 years. The economic interests
of publishers have dominated those of authors and readers. There is
more money available than ever before to pay authors for their talent
and work. This will get even better if the pub lishers can be
squeezed as the new technologies warrant. Technologically, there is
still a little ways to go before everyone can sit in his bathtub with
a waterproof flat screen and browse the world's literature.

(2) The world would benefit from a lot more manpower going into free
software.  The volunteer efforts associated with the Free Software
Foundation could use ten times the manpower. We need a way of paying
for it out of public funds and for encouraging new volunteer
efforts. Alternatively, the same result might be obtained by some
improvement in the economics of commercial software.

(3) The previous sections of this article have described goals for
computing and computer science for the next 49 years. How fast these
goals are achieved depends significantly on the attitude of the
researchers and the agencies that support research. A large fraction
of computer science research in industry and academia over the last 20
years has been wasted, because the projects have had too short a time
scale. For example, major researchers in program verification have
spent almost all their time on verifying successive parts of
microprocessors and have had little support for research in the
general theory of verification.

One result has been many academic projects and Silicon Valley
companies pursuing essentially identical minor ideas. This is likely
to continue during the next 49 years. Big advances will not come from
a succession of 25 two year projects. The rush to patent has resulted
in patenting trivial improvements.  Among the sciences computer
science has been particularly badly off. One reads all the time about
physics and astronomy projects with ten and twenty year completion
times.

What long term projects are worthwhile in computer science? For one,
there needs to be more longterm projects to develop automatic
interactive theorem provers, better computer algebra systems, a Lisp
better than scheme.  It is important to choose experimental domains
designed to be informative, rather than to emphasize short term
goals. The geneticists have worked with Drosophila since 1910, and yet
the fruit flies of today are no better than the fruit flies of
1910. Couldn't the geneticists at least have bred them for speed so we
could enjoy fruit fly races? The ``practical'' types sneer at ``toy
problems,'' but these are the Drosophilas.

To summarize, here some problems I see.

(1) Humanlevel AI and how to get there;

(2) Getting AI to where programs can learn from books;

(3) Specifying programs that interact with people and other programs;

(4) Making formal proofs that programs meet specifications part of
    contracts.

(5) Giving users full control of their computing environments,
    i.e. devising ways for users to reprogram their environments without
    their having to understand more than necessary.

(6) Giving programming languages primitives for the abstract syntax of
    the language itself.

(7) Proving a computational analog of the Shannon channel capacity
    theorem.

REFERENCES

AUSTIN, J. L. 1962. How to Do Things with Words, Oxford.

MCCARTHY, J. 1996. Elephant 2000
http://wwwformal.stanford.edu/jmc/elephant.html,
Stanford Formal Reasoning Group, available only as
http://wwwformal.stanford.edu/jmc/elephant.html.

SEARLE, J. R. 1969. Speech Acts, Univ. Press, Cambridge, Eng.

SHANAHAN, M. 1997. Solving the Frame Problem, A Mathematical
Investigation of the Common Sense Law of Inertia. M.I.T. Press,
Cambridge, Mass. 
--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]
※ 修改:·ssos 於 07月27日11:18:10 修改本文·[FROM: 202.118.230.220]