constituents Q is a finite set of states \Sigma is the input alphabet, where \square \not \in \Sigma \Gamma is the tape alphabet, where \square \in \Gamma, and \Sigma \subseteq \Gamma (because we can write empty cells) \delta: Q \times \Gamma \to Q \times \Gamma \times \left\{L, R\right\} q_0 \in Q, the start state q_{a} \in Q, the accept state q_{r} \neq q_{a}\in Q, the reject state (because a Turing Machine may not terminate at end of input) requirements additional information why TM is awesome a Turing Machine M = \left(\Gamma, Q, S\right) should be ready for inputs of any length n (in particular, when designing M, we don’t know what n will be) a Turing machine’s computation is “local”—you can’t look at the whole input, and the composition of these many local steps No ambiguity as to runtime: how many times you apply \delta before you get to Qaccept or Qreject Church-Turing thesis as local steps “computation is any process that takes place in a sequence of simple, local steps.” configuration the configuration of a Turing Machine contains its entire state: the content of the tape the current state of the controller the position of the writer we write this by putting the state right before the position of the write head: this means that our write head is at the bit that says 1, at state q7. yield Let C_1 and C_2 be configurations of a TM M; let us call C_1 yields C_2 if M is in configuration C_2 after running M in configuration C_1 for one step. Suppose \delta(q_1, b) = (q_2, c, L); then aa (q_{1}) bb yields a (q_{2}) a c b. accept A TM M accepts w if there are configs C_0, …, C_{k} for which: C_0 = q_0w C_i yields C_{i+1} for i=0 … k-1 and C_{k} contains q_{accept} recognize vs decide recognize L: the TM will accept strings l \in L (a string outside may loop or reject) decide L: the TM will accept strings l \in L, and reject all strings l’ \not \in L recognizable A language L is recognizable (“recursively enumerable”) if some TM recognizes L decidable A language L is recursive if some TM decides L L is decidable IFF L and not L are both recognizable given a M_1 that recognizes L, a M_{2} that recognizes \neg L, we want to build a machine M that decides L. (this is easy; just run both machines at once on two tapes and then just check which one gets recognized first; accept if M_1 accepts and reject if M_2 accepts) if L is decidable, \neg L is also decidable (because we just run L and return the opposite) intuition structure finite state controller (with a write head) infinite, writable tape (whenever the machine goes to the right, we get a new cell, if we go left, we hit a wall and stay put) we lay our input onto the tape capability they can write to and read from the tape the head can move left and right the input doesn’t have to be read entirely: we can bail at any moment, or not stop at all Accept and Reject take immediate effect. Graph-based Turing Machine Representation nodes are the finite control states each edge has a three-tuple: (read, write, move) which is what we are going to read, what we are going to write, and where we move on the tape (left or right) the empty cell is a valid read or write (i.e. we can read nothing, meaning our input has ended, and we can write nothing) notation: read -> write, move examples two of the same string \begin{equation} L = \left{w # w \mid w \in {0,1}^{*}\right} \end{equation} if there is no # on the tape (or more than one, #), reject while you do this, copy the entire string to the right (we do this because otherwise we wouldn’t know if moving to the left actually did something (i.e. the first symbol is duplicated) or we were just hitting the wall and bouncing) while there is a bit to the left of # replace the first bit with X, and check the first bit to the right of the # and x is the same one if not, reject; if so, replace the right bit with an X too if there is a bit to the right of # that’s not X, then reject; otherwise, accept Recognizability decidable predicate A decidable predicate R(x,y) is a proposition about the input strings x, y, such that some Turing machine M will implement R. That is, for all x, y, we have R(x,y) is true means M(x,y) accepts, and R(x,y) is false means M(x,y) rejects. That is: R: \Sigma^{*} \times \Sigma^{*} \to \left\{T,f\right\} predicate recognizability a particular language A is recognizable IFF there is a decidable (note the upgrade in strength) predicate R(x,y) such that A = \left\{x \mid \exists y, R(x,y)\right\}. Proof: \Rightarrow assume A = \left\{x \mid \exists y, R(x,y)\right\}, we want to show that A is recognizable Create a Turing machine which: enumerate all finite-length strings y; if R(x,y) is true, accept it. \Leftarrow if A is recognizable, there is some decidable predicate R(x,y) such that A = \left\{x \mid \exists y, R(x,y)\right\}. By definition A is recognizable, so there’s an M which recognizes A. Define a predicate R(x,y) be TRUE IFF M accepts x in |y| steps. We now want to show that R(x,y) is decidable. If M accepts x; it would have done so in some finite y steps. Hence, R(x,y) = TRUE. If there is some y for which R(x,y) is true, we can see that we can run M on x for y steps and see that by definition M have just accepted the string. This is decidable because we can check for y steps exactly, so we will always terminate. Turing Machine as a universal algorithm why do we focus on a turing machine? its extremely simple to analyze (its possible to formalize and reason about it) Extended Church-Turing Thesis—every “real-world” efficiently computable algorithm can be “compiled to” efficiently computable Turing Machine with only poly-slowdown