The Church-Turing ThesisComponents of a Turing machine (TM)How a Turing machine worksDefinitionsRecognizing vs decidingDiagrams without the reject stateDesigning TM: Example 1Slide 8Slide 9Slide 10Slide 11Designing TM: Example 2Designing TM: Example 3Designing TM: Example 4Testing whether the head is at the beginning of the tapeImplementing the “go to the beginning of the tape” operationShifting tape contentsA TM for the element distinctness problemTuring machines with the “stay put” optionMultitape Turing machinesMultitape Turing machines: ExampleSimulating multitape TM with ordinary TMNondeterministic Turing machinesTuring machines with an output (not in the textbook!)Computable functionsComputability vs. decidabilityAlgorithmsAlgorithms should deal with stringsEncodingEncoding graphsThe Church-Turing thesisThe three levels of TM descriptionsThe Church-Turing ThesisThe Church-Turing ThesisChapter 3 Giorgi Japaridze Theory of ComputabilityComponents of a Turing machine (TM) 3.1.aGiorgi Japaridze Theory of Computability(Q,,,,start,accept,reject)•Q is the set of states is the input alphabet not containing the blank symbol - is the tape alphabet, where - and  is the transition function of the type Q Q{L,R}•start,accept,reject Q, where rejectaccept; the states accept and reject are called halting states.There are no transitions from the halting states, and they immediately take effect!xy,Rq1 q2 If the current tape symbol is x, replace it with y, move the head right and go to q2. The label xx,R is simply written as xR. If we here have L instead of R, then the head is moved left, unless it was on the first cell, in which case it remains where it was. a a b a b b - - - - - -How a Turing machine works 3.1.bGiorgi Japaridze Theory of Computability0x,Rq2 q3startacceptq4q5reject0 -,R-  Rx  R-  R0R0 x,R-  R-  L0  Lx  LxRxRxR-  R- x 0 0 - - - - - - -Configuration:1. Current state;2. Tape contents;3. Head positionDefinitions 3.1.c1Giorgi Japaridze Theory of Computability A TM accepts an input string iff, on this input, sooner or later it entersthe accept state. Otherwise the string is considered rejected. Thus, the input is rejected in two cases:1) The machine enters the reject state at some point, or 2) The machine never halts (never enters a halting state). A Turing machine is said to be a decider iff it halts on every input.The language recognized by a TM --- the set the strings that TM accepts;If this machine is a decider, then we say that it not only recognizes,but also deci des that language.A language is said to be Turing-recognizable iff some TM recognizes it.A language is said to be Turing-decidable iff some TM decides it.Recognizing vs deciding 3.1.c2Giorgi Japaridze Theory of Computabilityacceptreject0  R -  R-  R0  R-  R0 RWhat language does the above machine recognize?Does it decide that language?acceptreject0  R -  R-  R0  RWhat language does the above machine recognize?Does it decide that language?Diagrams without the reject state 3.1.dGiorgi Japaridze Theory of Computability0x,Rq2 q3startacceptq4q50 -,R-  R0R 0 x,R-  R -  L0  Lx  LxRxRxRThe reject state can be safely removed.It will be understood that all the missing transitions lead to the reject state.Designing TM: Example 1 3.1.e1Giorgi Japaridze Theory of ComputabilityDesign a TM that recognizes (better – decides) {#n =m | n=m}1. Sweep left to right across the tape, testing if the input has the form#*=*; if not, reject; if yes, go back to the beginning of the tapeand go to step 2 (state q3).start q1R# R= R q2- L q9RL = L x L - L q3#  LDesigning TM: Example 1 3.1.e2Giorgi Japaridze Theory of Computability2. Keep going to the right, replace the first  you see before = with x and go to step 3 (state q5); if you reach = without seeing a , go to step 4 (state q6). q3 q4xR# R x,R q5 q6= RDesigning TM: Example 1 3.1.e3Giorgi Japaridze Theory of Computability3. Keep going to the right, pass = and then replace the first  you see with x and go to the beginning of the tape, step 2 (this can be done by going to state q9);if you reach a blank without seeing a , reject. q5 q7R= R x,R q9 xRDesigning TM: Example 1 3.1.e4Giorgi Japaridze Theory of Computability4. Keep going to the right as long as you see x. If you see a  beforereaching a blank, reject; otherwise accept. q6 acceptxR- RDesigning TM: Example 1 3.1.e5Giorgi Japaridze Theory of Computabilitystart q1R# R= R q2- L q9RL = L x L - L q3#  L q4xR# R x,R q5= R q7= R x,R q6 acceptxR- R#     =    - - -R xRDesigning TM: Example 2 3.1.fGiorgi Japaridze Theory of Computabilitystart q1R# R< R q2- L q9RL < L x L q3#  L q4xR# R x,R q5< R q7< R x,R q6 acceptxR RDesign a TM that decides {#n <m | n<m}R xRL < L x L - LDesigning TM: Example 3 3.1.gGiorgi Japaridze Theory of Computabilitystart q1R+ R= R q2- L q9R + LL = L x L - L q3#  L q4xR+R# R x,R q5= R q7= R x,R q6 acceptxR- RR +R xRDesign a TM that decides {#n +m = k | n+m=k} q0# RRDesigning TM: Example 4 3.1.hGiorgi Japaridze Theory of ComputabilityDesign a TM that decides {#n m = k | nm=k}Step 1: Check if the string has the form #* * = * . If not, reject;If yes, go back to the beginning of the tape, step 2.          =# -Step 2: Find the first  between # and , delete it and go to step 3;If no such  was found, go to step 5.Step 3: Find the first  between  and =, delete it and go to step 4;If no such  was found, go to the beginning of the tape, restoring onthe way back all the deleted  between  and =, and go to step 2.Step 4: Find the first  after =, delete it, go back to  , and go to step 3;If no such  was found before seeing a blank, reject.Step 5: Go right past = ; if no  is found there before reaching a blank,accept;