Turing MachinesComputing with Turing MachinesRecursively Enumerable and Recursive LanguagesTheoretical ExamplesPartially Recursive FunctionsTuring MachinesRead K & S 4.1.Do Homework 17.Grammars, Recursively Enumerable Languages, and Turing Machines L Unrestricted Grammar Accepts Turing MachinesCan we come up with a new kind of automaton that has two properties:-powerful enough to describe all computable thingsunlike FSMs and PDAs-simple enough that we can reason formally about itlike FSMs and PDAsunlike real computersTuring Machines - a b b a At each step, the machine may:-go to a new state, and Finite State Control-either-write on the current square, or s1, s2, … h1, h2-move left or rightA Formal DefinitionA Turing machine is a quintuple (K, -, -, s, H):K is a finite set of states;- is an alphabet, containing at least and -, but not - or -;s - K is the initial state;H - K is the set of halting states;- is a function from: (K - H) - - to K - (- - {-, -}) non-halting state - input symbol state - action (write or move)such that(a) if the input symbol is -, the action is -, and(b) - can never be written .Lecture Notes 20 Turing Machines 1RecursivelyEnumerableLanguageTuringMachineNotes on the Definition1. The input tape is infinite to the right (and full of ), but has a wall to the left. Some definitions allow infinite tape in bothdirections, but it doesn't matter.2. - is a function, not a relation. So this is a definition for deterministic Turing machines.3. - must be defined for all state, input pairs unless the state is a halt state.4. Turing machines do not necessarily halt (unlike FSM's). Why? To halt, they must enter a halt state. Otherwise they loop.5. Turing machines generate output so they can actually compute functions.A Simple ExampleA Turing Machine Odd Parity Machine: - 0 1 1 0 - = 0, 1, -, s = H = - =Formalizing the Operation- a a b b (1)- a a b b (2)A configuration of a Turing machine M = (K, -, -, s, H) is a member ofK - --* - (-*(- - {})) - - state input up input afterto scanned scanned squaresquareThe input after the scanned square may be empty, but it may not end with a blank. We assume the entire tape to the right of theinput is filled with blanks.(1) (q, -aab, b) = (q, -aabb)(2) (h, -aabb, -) = (h, -aabb) a halting configurationLecture Notes 20 Turing Machines 2Yields(q1, w1a1u1) |-M (q2, w2a2u2), a1 and a2 - -, iff - b - - - {-, -}, -(q1, a1) = (q2, b) and either:(1) b - -, w1 = w2, u1 = u2, and a2 = b (rewrite without moving the head) | w1 | a1 | u1 | - a a b b -aabb | w2 | a2 | u2 |- a a a b -aaabYields, Continued(2) b = -, w1 = w2a2, and either(a) u2 = a1u1, if a1 - or u1 - -, | w1 | a1 | u1 |- a a a b -aaab | w2 | a2 | u2 |- a a a b -aaabor (b) u2 = -, if a1 = and u1 = - | w1 | a1 |u1|- a a a b -aaab | w1 | a1 |u1|- a a a b -aaabIf we scan left off the first square of the blank region, then drop that square from the configuration.Yields, Continued(3) b = -, w2 = w1a1, and either(a) u1 = a2u2 | w1 | a1 | u1 |- a a a b -aaab | w2 | a2 | u2 |- a a a b -aaabor (b) u1 = u2 = - and a2 = | w1 | a1 |u1|- a a a b -aaab | w2 | a2 |u2|- a a a b -aaabIf we scan right onto the first square of the blank region, then a new blank appears in the configuration.Lecture Notes 20 Turing Machines 3Yields, ContinuedFor any Turing machine M, let |-M* be the reflexive, transitive closure of |-M.Configuration C1 yields configuration C2 if C1 |-M* C2.A computation by M is a sequence of configurations C0, C1, …, Cn for some n - 0 such thatC0 |-M C1 |-M C2 |-M … |-M Cn.We say that the computation is of length n or that it has n steps, and we writeC0 |-Mn CnA Context-Free ExampleM takes a tape of a's then b's, possibly with more a's, and adds b's as required to make the number of b's equal the number of a's.- a a a b K = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}- = a, b, -, , 1, 2s = 0 H = {9} - =0 a/1 /- a,1,2/- 1,2/- a/1 1/- b/2 2/-1 2 3 4 5 /2 2/- / 6 /-1/a;2/b7 8-/- /9An Example Computation- a a a b (0, -aaab) |-M (1, -aaab) |-M (2, -1aab) |-M (3, -1aab) |-M (3, -1aab) |-M (3, -1aab) |-M (4, -1aa2) |-M...Lecture Notes 20 Turing Machines 4Notes on ProgrammingThe machine has a strong procedural feel.It's very common to have state pairs, in which the first writes on the tape and the second move. Some definitions allow both actions at once, and those machines will have fewer states.There are common idioms, like scan left until you find a blank.Even a very simple machine is a nuisance to write.A Notation for Turing Machines(1) Define some basic machines-Symbol writing machinesFor each a - - - {-}, define Ma, written just a, = ({s, h}, -, -, s, {h}),for each b - - - {-}, -(s, b) = (h, a) -(s, -) = (s, -)Example:a writes an a-Head moving machinesFor each a - {-, -}, define Ma, written R(-) and L(-):for each b - - - {-}, -(s, b) = (h, a) -(s, -) = (s, -)Examples:R moves one square to the rightaR writes an a and then moves one square to the right.A Notation for Turing Machines, Cont'd(2) The rules for combining machines: as with FSMs >M1 a M2 b M3-Start in the start state of M1.-Compute until M1 reaches a halt state.-Examine the tape and take the appropriate transition.-Start in the start state of the next machine, etc.-Halt if any component reaches a halt state and has no place to go.-If any component fails
View Full Document
Unlocking...