=========================================================================== CSC 363H Lecture Summary for Week 1 Summer 2007 =========================================================================== ---------- Motivation ---------- Consider the following problems: - MULTIPLICATION Input: x, y Output: x*y - RELATIVELY-PRIME Input: x, y Output: YES, if x and y are relatively prime (i.e. gcd(x,y)=1) NO, otherwise - PRIME Input: x Output: YES, if x is a prime number NO, otherwise - FACTOR Input: x Output: y, a non-trivial factor of x (i.e. 1 < y < x) if one exists NIL, otherwise - SHORTEST-PATH Input: graph G, vertices u, v Output: the shortest path between u and v in G, if one exists NIL, otherwise - LONG-PATH Input: graph G, vertices u, v, target k Output: YES, if there exists a simple path (i.e. no repeated vertices) in G between u and v of length at least k NO, otherwise - CRASH Input: the code of a C program, code.c Output: YES, if the program crashes NO, otherwise Which of the problems in this list can be solved algorithmically? In class, we agreed that we can write algorithms for all of them except CRASH. We have no intuition on how to solve CRASH. Which of the problems can be solved using "efficient" algorithms? We agreed that MULTIPLICATION, RELATIVELY-PRIME and SHORTEST-PATH can be solved efficiently, even though, at this point, we don't have a precise definition of what "efficient" means. Consider the following algorithm for solving PRIME: PRIME: on input x for i <- 2 to x-1 do if i divides x, output NO end for output YES The following algorithm is clearly correct for testing primality, but is it efficient? Note: a small improvement can be obtained by having the loop run only through sqrt(x) instead of x-1. A simple calculation shows that, given inputs x, y which are 25 decimal digits long, a person can solve MULTIPLICATION by hand in less than 1 hour. A computer would probably do this in less than 1 second. However, if the above algorithm is fed an input x which has 25 decimal digits, there will be 10^12 iterations of the loop (provided we go up to sqrt(x) only). At a reasonable 10^4 iterations per second and a generous 10^6 seconds per day, it would take a fast computer 10^12/(10^4 * 10^6) = 10^2 days to finish executing this algorithm. That's about 3 months, compared to the 1 second it would take to multiply two numbers of this magnitude. Intuitively, we would like to define "efficiency" in such a way that the usual multiplication algorithm is efficient, but the above primality testing algorithm is not efficient. -------------------- Goals of this Course -------------------- 1. Define what an "algorithm" means. 2. Prove that there are problems that cannot be solved by algorithms. It turns out that CRASH above is one such problem. 3. Define when an algorithm is "efficient". 4. Show that certain problems do not have efficient algorithms. Parts 1&2 = Computability, we ignore resources used by algorithms. Parts 3&4 = Complexity, we do care about resources (time, space). --------------------------- Computational Computability --------------------------- Outline (topics and textbook sections): 1. Turing machines: definitions, examples (3.1) 2. Variants, the Church-Turing thesis (3.2, 3.3) 3. Diagonalization, the Halting problem (4.1, 4.2) 4. Decidability and recognizability, examples (4.2, 5.1) 5. Reducibility, examples (5.1, 5.2) 6. Mapping reducibility, examples (5.3) --------------- Turing machines --------------- Motivation: - Goal: define "computation" as abstractly and generally as possible. - Many possible formalizations: start with one, study it, then compare with others. Informal idea: similar to FSA but with no limitation on access to input: - one-way infinite "tape" divided into "squares" (each square holds one symbol); - read-write "head" positioned on one square at a time; - "control" can be in one of a fixed number of states; - initially, tape contains input (one symbol per square) and blanks, and head is on leftmost input symbol; - current state and symbol read determine next state, symbol written, and movement of head (one square left or right). Differences between FSA and Turing machines: - TM can both read and write symbols. - Infinite tape. - Head can move left or right (convention: moving left on leftmost square leaves head where it is). - Special "accept" and "reject" states that stop computation immediately. Example: M that accepts only strings of the form 0^k1^k, for k >= 0. We first informally describe the movement of the head of M as follows: 1. if reading a blank "_", ACCEPT 2. if reading 1, REJECT 3. so we are reading 0, erase it (replace it with _), move R 4. continue moving R past symbols 0&1 until reading _, move L 5. if not reading 1, REJECT 6. so we are reading 1, erase it, move L 7. continue moving left past symbols 0&1 until reading _, move R 8. go to 1 Formal definition: - A Turing machine is a 7-tuple (Q,S,T,d,q_0,q_accept,q_reject), where . Q is a fixed, non-empty, finite set of "states" . S is a fixed, non-empty, finite set of symbols (the "input alphabet", with "blank" symbol _ not in S) . T is a fixed, non-empty, finite set of symbols (the "tape alphabet", with S subset of T and _ in T) . q_0 in Q is the "start state" (or "initial state") . q_accept in Q is the "accepting state" . q_reject in Q is the "rejecting state" (q_reject =/= q_accept) . d : Q-{q_accept,q_reject} x T -> Q x T x {L,R} is the "transition function" Example of a formal description of a Turing Machine: Here is a formal specification for the Turing Machine M described above. Q = { q_0, q_1, q_2, q_3, q_acc, q_rej } S = { 0, 1 } T = { 0, 1, _ } function d: (q_0, _) -> (q_acc, *, *) (we ignore contents of tape after M stops) (q_0, 1) -> (q_rej, *, *) (q_0, 0) -> (q_1, _, R) (q_1, 0) -> (q_1, 0, R) (q_1, 1) -> (q_1, 1, R) (q_1, _) -> (q_2, _, L) (q_2, _) -> (q_rej, *, *) (q_2, 0) -> (q_rej, *, *) (q_2, 1) -> (q_3, _, L) (q_3, 0) -> (q_3, 0, L) (q_3, 1) -> (q_3, 1, L) (q_3, _) -> (q_0, _, R)