LECTURE 1

	      CSC 527:  Theory of Computing, Spring 2006
			 Victor J. Milenkovic
		       http://www.cs.miami.edu
		       csc527@mail.cs.miami.edu

***************************************************************************
	LOG IN!!!!  READ YOUR EMAIL REGULARLY!!!  READ THE WEB PAGE!!!
***************************************************************************

READ CHAPTER 1

Q: What is the purpose of this course?

To teach you (some of) the limits of computation.
What is impossible to compute?
What is very hard to compute?


Q: Why is this important?

Computer Science is about computation, and you need to know what
computation can and cannot do.

This is as important as knowing that chemistry cannot convert lead
into gold (although physics can).

Conservation of mass/energy.

2nd law of thermodynamics: why I can't run my laptop/car/lightbulb
using the heat in the air.

Maxwell's Daemon:  why it doesn't work.  (Computation!!)

Uncertainty Principle:  Quantum Mechanics.
Now used for cryptography!


Q: What is computation?

Recognizing languages.


Q: What is a language?

A set of strings.


Q: Huh?

A Java program is a string, isn't it?  Of course, javac does a little
more than say yes or no it's a Java program, but that's the essential
computation.

1. We are trying to show what is hard or impossible.  If you can't
   recognize a Java program, you certainly can't do anything else you
   might consider computation with it.

2. Actually, the definition of computation as recognizing languages
   works quite well, if you apply it right.


Q: What is an example of an impossible computation?

Imprecisely--and the purpose of this course is to make this
precise--you can't tell if a piece of software has some kind of
infinite loop.  There is no way in general to tell if it will never
stop or if it will stop if you just let it run a few more minutes.

More generally, you can't tell what a program does except by running
it.

In a sense, we will show that you have free will.  Your brain is a
sophisticated computer running a sophisticated program.  The only way
someone could truly predict your behavior is to create a complete copy
of you and run it on a faster computer.  But that copy would be just
another you, and so they wouldn't really be predicting you after all.


Q: Why does the course have to be so formal?

Other CS courses should you to do things.  If they leave out some
details, you can usually work them out.

This course shows you what is impossible.  Such a statement is
extremely strong.  It says that no matter how ingenious you are, you
cannot compute a particular problem.  The argument has to be
completely airtight and hence very formal and detailed.


Q: What is hard to compute?

A simple example is PARTITION.  Suppose you and a sibling inherit an
estate.  You have every item appraised.  Now you want to divide the
items into two piles with exactly equal value.

A potential element of PARTITION is a list of integers

	123, 44, 88, 6, 32, 9, 45, 87

It is in the language if it can be split up evenly.

This is an example of a problem that can be solved quickly by a
NONDETERMINISTIC computer.  Think of it as a very lucky computer.  A
lucky computer can guess a subdivision

	123 + 88 + 6 = 44 + 32 + 9 + 45 + 87

and then quickly verify that it is true.

It turns out that if you had an algorithm that could recognize
PARTITION quickly, you could use it to build a lucky computer!