Turing machine and Halting Introduction

INDEX:
What is a Turing Machine?
Decidability and Undecidability
What is Halting?

1. TOC Presentation Turing Machine and Halting Amartya Yandrapu - 19070122017 Sree Varsha Chanumolu - 19070122044

2. What is a Turing Machine? A Turing Machine is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected.

3. A Turing Machine can be defined as a set of 7 tuples (Q, E, F, 8, qo, b, F) Q→ Non empty set of States ℷ → Non empty set of Symbols ⟌ → Non empty set of Tape Symbols δ →Transition function defined as: QxE → ⟌ x (R/L) x Q q०→ Initial State b→ Blank Symbol F→ Set of Final states (Accept state & Reject State) The Production rule of Turing Machine will be written as δ (qo, a) → (q1,Y,R)

4. Decidability and Undecidability Recursive Language: A language L is said to be recursive if there exists a Turing machine which will accept all the strings in ‘L’ and reject all the strings not in ‘L’. It will halt every time and give an answer (accepted or rejected for each and every string input). Recursively Enumerable Language: A language L is said to be a recursively enumerable language if there exists a Turing machine which will accept (and therefore halt) for all input strings in L. But may or may not halt for all input strings which are not in ‘L’. Decidable Language: A language ‘L’ is decidable if it is a recursive language. All decidable languages are recursive languages are vice-versa. Partially decidable Language: A language L is partially decidable, if L is a recursively enumerable language. Undecidable Language: A language is undecidable if it is not decidable. It may be partially decidable but not decidable. If a language is not even partially decidable, then there exists no Turing machine for that language.

5. What is Halting? Halting means that the program on certain input will accept it and halt / reject it and halt and it would never go into an infinite loop. Basically halting means terminating. Given a Turing Machine, will it halt when run on some particular given input string? Given some program written in some language (Java,C,C++) will it ever get into on infinite loop or will it always terminate? Answer: In general, we can’t always know. The best we can do is run the program and see whether it halts. For many programs, we can see that it will always halt or sometimes loop. But, for programs in general, the question is undecidable. Example: A machine can be designed which can accept all valid Java codes. It is a compiler. But, a machine can’t be designed which can accept all Java codes and never goes into infinite loop.

6. Hypothesis and Testing Can we design a machine, which if given a program can find out or decide if that program will always halt or not halt on a particular input? H(P,I) Halt Not Halt

7. Hence, we can conclude from proof by contradiction that we cannot predict in general if a program will halt or not on a particular input. Let us assume that we can: This allows us to write another program: C(X) If (H(X,X)==Halt) Loop Forever; Else Return; If we run ‘C’ on itself, H(C,C)==Halt H(C,C)==Not Halt Not Halt Halt

8. Thank You!