false

Class Notes
(835,882)

Canada
(509,468)

York University
(35,286)

Natural Science
(2,813)

NATS 1700
(205)

Zbigniew Stachniak
(36)

Lecture

Unlock Document

Natural Science

NATS 1700

Zbigniew Stachniak

Summer

Description

Lecture 15. The Limits of Computing and
Articial Intelligence
Informal and unedited notes, not for distribution. (c) Z. Stachniak, 2011-2012.
Note: in cases I were unable to nd the primary source of an image or determine
whether or not an image is copyrighted, I have specied the source as unknown. I
will provide full information about images and/or obtain reproduction rights when
such information is available to me.
Introduction
We are living in digital society, submerged in digital culture. It is dicult to
imagine our lives without computers, without infrastructure that they pro-
vide. If the history (i.e. the recorded past) is any guideand we clearly dont
have anything else as powerful as our past experienceany major technolog-
ical breakthrough or scientic discovery inspires Utopian sentiments. In the
past, the advent of steam power, electricity, electronics, and even the Inter-
net, had inspired ungrounded proclamations of a techno-panacea leading to
ever lasting technology-based higher forms of social organization (and liber-
ation). The world would be better, freer, more fair as long as steam power is
with us we proclaimed a few centuries ago. But we know that steam power
was only a stage in the development of our civilization. It kick-started the
Industrial Revolution, modernized almost every sector of manufacturing and
produced repeated immense waves of economic growth. It made a lot of peo-
ple rich, fast, and left many people poor and desperate. And then it was over.
Will computers be always with us? Will they make us better, freer, more fair?
Are they the ultimate tools that, when they evolve suciently, will be able
to provide us with limitless benets, and guide us to the next and higher step
of social and cultural evolution? Or will they share the fate of steam engines?
Perhaps computers will evolve into some other devices, like calculators which
seemed invincible but, in the end, only paved the way to computers. Perhaps
in 50 years computers might only be seen in technology museums...
1 Fig. 1. The evolution of computing. Source: unknown.
To search for answers to some of these questions one may consult computer
scientists themselves. What do they know about computers and computing?
Will the continuous technological progress result in future computers that
will be able to solve all problems of interest to us? What does computer
science know about the limits of computing?
In this lecture we shall search for scientic answers to just two questions.
The rst deals with the limits of computing. The second with the quest for
computer-based intelligence.
2 Can computers solve every problem?
To answer any question fairly, one has to understand it fully, one has to make
sure that all the terms used in the question are dened with precision. Hence,
if we want to know, for instance, whether or not all problems are solvable
by computational means, we have to know the exact meaning of the terms
problem, computer, and computation. Only then we can attempt an-
swering the question.
The discipline that can provide us with adequate denitions of the terms
in question is Theoretical Computer Science (or TCS). It is one of the ob-
jectives of TCS to make the analysis of these denitions and to draw logical
conclusions about computers from them.
The precise denitions of problem, computer, and computation as
provided by TCS require a lot of background knowledge. Therefore in our
discussion we shall mostly rely on approximate and, hence, imprecise def-
initions: a problem is a question that requires an answer, a solution is a
correct answer to a problem, computing is a problem solving method using
algorithms and computers (of today or any computer that will be built in
the future).
TCS has matured enough to provide us with answers to at least some im-
portant questions about the power and limitations of computing. We know
by now that unless we substantially modify our views on computers, the pic-
ture of computing that emerges is not as optimistic as we might want it to be.
Before I sketch this picture, let us simplify our task to investigate possi-
ble limits (or lack of) to computing by concentrating not on all problems but
just problems concerning integer arithmetic, problems like
is there a value of X which makes the equation X + 1 = 2 true?
This problem is, of course, solvable and the answer (solution) is X = 1.
Question 1: How many problems concerning arithmetic are there?
Before we answer this question, let me explain why it is important. If the
answer is: the number of all problems concerning arithmetic is nite, say one
3 million, then we can just write one million computer programs to solve each
problem individually and no question concerning arithmetic would be left
unanswered.
Unfortunately, the number of problems concerning arithmetic is not nite.
Please take a look at this never ending sequence of problems:
is there a value of X which makes the equation X + 1 = 2 true?
is there a value of X which makes the equation X + 1 = 3 true?
is there a value of X which makes the equation X + 1 = 4 true?
is there a value of X which makes the equation X + 1 = 5 true?
...
Clearly, every equation listed above can be solved in exactly the same way,
following two simple steps:
1. subtract 1 from both sides of the equation (e.g. X + 1 1 = 2 1);
2. simplify both sides of the equation (X +11 = 21 simplies to X = 1).
Therefore a single computer program can handle all problems in this class.
But how about other problems? In other words:
Question 2: Can a single computer program be written to solve all prob-
lems concerning arithmetic?
To answer this question, we have to review Alan Turings work done in the
1930s and discussed in Lecture 5. Using his model of computing dened
in terms of what we now call Turing Machines (and widely accepted as an
adequate and most general) he demonstrated the existence of unsolvable
problems problems that cannot be solved algorithmically.
The negative answer to Question 2 may not be too disappointing if, for
instance, the majority of problems are solvable and only a few are not.
Question 3: Which collection of problems concerning arithmetic is larger:
the collection of solvable problems or unsolvable problems?
To answer this question we must know how to compare collections contain-
ing innitely many items. A mathematical discipline that species how such
4

More
Less
Related notes for NATS 1700

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.