Class Notes (835,882)
Canada (509,468)
York University (35,286)
Natural Science (2,813)
NATS 1700 (205)


19 Pages
Unlock Document

Natural Science
NATS 1700
Zbigniew Stachniak

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

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
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.

Add your courses

Get notes from the top students in your class.