Turing machine

Turing Machine PPT

1. TURING MACHINE BY : HIMANSHU SIROHI

2. CONTENTS 1. INTRODUCTION 2. TM MODEL 3. FORMAL DEFINITION 4. WORKING WITH EXAMPLE 5. PROPERTIES 6. MODIFICATIONS 7. THE HALTING PROBLEM 8. ADVANTAGES 9. POWER OF TM 10. APPLICATION

3. INTRODUCTION Invented by esteemed computer scientist ALAN TURING in 1936 Basically an abstract computational model that performs computations Provide a powerful computational model for solving problems in computer science Capable of simulating common computers

4. What is turing machine ? Consists of an infinite tape (as the memory) A tape head (a pointer to the currently inspected cell of the memory) And a state transition table(to govern the behavior of the machine)

5. FORMAL DEFINITION A TM is a seven-tuple: M = (Q, Σ, Γ, δ, q , B, F) Q A finite set of states Σ A finite input alphabet set Γ A finite tape alphabet B A distinguished blank symbol, which is in Γ q The initial/starting state, q is in Q F A set of final/accepting states, which is a subset of Q δ A next-move function, which is a mapping Q x Γ –> Q x Γ x {L,R} Intuitively, δ(q,s) specifies the next state, symbol to be written, and the direction of tape head movement by M after reading symbol s while in state q.

6. WORKING The machine operates on an infinite memory tape divided into discrete cells. The machine positions its head over a cell and reads the symbol there. Then, as per the symbol and its present place in user specified instructions , the machine Writes a symbol in the cell, then Either moves the tape one cell right or left Either proceeds to a subsequent instruction or halts the computation

7. EXAMPLE : TM that checks for string to be palindrome

8. Properties of tm Recognizability : A language is recognizable if a TM accepts when an input string is in the language, and either rejects or loops forever when an input string is not in the language. Decidability : A language is decidable if a TM accepts strings that are in the language and rejects that are not in the language. That is, TM will halt on all inputs. The Halting Problem is recognizable but undecidable.

9. Modifications in TM Multi– tape TM Multi –track TM Non– deterministic TM TM with semi—infinite tape These all give same performance as the standard TM gives.

10. Multi-tape TM δ: Q × X k → Q × (X × {Left_shift, Right_shift, No_shift }) k where there is  k  number of tapes

11. Multi-track TM Multi-track Turing machines, a specific type of Multi-tape Turing machine, contain multiple tracks but just one tape head reads and writes on all tracks. Here, a single tape head reads n symbols from  n  tracks at one step. δ  is a relation on states and symbols where δ(Q i , [a 1 , a 2 , a 3 ,....]) = (Q j , [b 1 , b 2 , b 3 ,....], Left_shift or Right_shift)

12. Non-deterministic TM In a Non-Deterministic Turing Machine, for every state and symbol, there are a group of actions the TM can have. So, here the transitions are not deterministic.  The computation of a non-deterministic Turing Machine is a tree of configurations that can be reached from the start configuration. An input is accepted if there is at least one node of the tree which is an accept configuration, otherwise it is not accepted.  δ  is a transition function : δ : Q × X → P(Q × X × {Left_shift, Right_shift}).

13. TM with semi-infinite tape A Turing Machine with a semi-infinite tape has a left end but no right end. The left end is limited with an end marker.

14. The Halting Problem Input  − A Turing machine and an input string  w . Problem  − Does the Turing machine finish computing of the string  w  in a finite number of steps? The answer must be either yes or no. Proof  − At first, we will assume that such a Turing machine exists to solve this problem and then we will show it is contradicting itself. We will call this Turing machine as a  Halting machine  that produces a ‘yes’ or ‘no’ in a finite amount of time. If the halting machine finishes in a finite amount of time, the output comes as ‘yes’, otherwise as ‘no’. The following is the block diagram of a Halting machine −

15. The following is the block diagram of such Halting machine −

16. Inverted Halting Machine Now we will design an  inverted halting machine (HM)  as − If  H  returns YES, then loop forever. If  H  returns NO, then halt. Further, a machine  (HM) 2  which input itself is constructed as follows − If (HM) 2  halts on input, loop forever. Else, halt. Here, we have got a contradiction. Hence, the halting problem is  undecidable .

17. The following is the block diagram of an ‘Inverted halting machine’ −

18. ADVANTAGES Turing machines are similar to  finite automata/finite state machines  but have the advantage of unlimited memory. They are capable of simulating common computers; a problem that a common computer can solve (given enough memory) will also be solvable using a Turing machine, and vice versa. Simplicity of proofs As a theoretic model, Turing machines have the charme of being "simple" in the sense that the current machine state has only constant size. All the information you need in order to determine the next machine state is  one  symbol and  one  (control) state number. The change to the machine state is equally small, adding only the movement of the machine head.

19. Advantages If you're designing some kind of programming language (or anything else that is meant to compute things), then you may want to ensure that it is Turing-complete (i.e., capable of computing anything that is computable) by implementing a Turing machine in it. Classify Problem  TM helps to classify decidable problems into classes of Polynomial Hierarchy. Suppose we found that the problem is decidable. Then our target become how efficiently we can solve it. The efficiency been calculated in number of steps, extra space used , length of the code/size of the FSM.

20. TM: INFINITE OR JUST UNLIMITED At this point we could fall to arguing the impossibility of the Turing machine because its tape can’t be infinitely long. The machine doesn't, in fact,  need an infinite tape, just one that isn't limited in length and this is a subtle difference. Imagine if you will that Turing machines are produced with a very long but finite tape and if the machine ever runs out of space you can just order some more tape. This is the difference between the tape actually being infinitely long or just unlimited…

21. TURING MACHINE: feeble or powerful You may think that TM is not really of any importance because it is a very feeble machine but it can’t be dismissed like this because Alan Turing thought up the machine as a model for computation that could be performed by human easily. So ,TM is the simplest implementation of computing and informally we can say that if something can be computed then it can be done using a TM. That is, TM is about what can be computed in principle It actually defines computing, computation and what is Computable Compare this aspect with the RAM model (when not used in its minimalistic form): the next operation may be  any  of several operations, which may access  any  (two) registers. There are also multiple control structures.

22. Application The  Church-Turing thesis  claims that any computable problem can be computed by a Turing machine. This means that a computer more powerful than a Turing machine is not necessary to solve computable problems. The idea of Turing completeness is closely related to this. A system is Turing complete if it can compute every Turing computable function. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete. To prove that something is Turing complete, it is sufficient to show that it can simulate some other Turing complete system. Usually, it is easiest to show that a system can simulate a universal Turing machine . A universal Turing machine is a Turing machine that can simulate  any  other Turing machine.

23. Conclusion You could say that the computer was invented twice – once by Charles Babbage and once by Alan Turing. While Babbage’s machine was a practical thing but Turing’s was just a machine of mind. TM is a model of what is physically computable. TM might take a little longer to work out on a problem than the latest PC , but it will give the same result. If you have a system that can compute something then a TM can compute it as well. What is more so far no system has been found that can goes beyond a TM.

24. THANK YOU