Turing Machines Study Notes for GATE and Computer Science Exams
By BYJU'S Exam Prep
Updated on: September 25th, 2023
A simple trick to crack GATE CS is by understanding the concept of all the subjects and by preparing GATE CSE study notes. Turing of machines is a very important topic from the Theory of Computation subject for all the computer science exams such as GATE CSE, PSU’s & NEILIT exams. These exams aim to test your understanding of a particular subject in deep level computer science and engineering.
In this article, we have provided to you the free study material for turning of machines that is crucial for any GATE CS aspirant. The study notes on Turing of machines topic will further be of great help for GATE & ESE CSE as well. You can further download the Turning of Machines notes PDF for GATE and other Computer Science exams from the links provided below.
Every year one mark two mark question is always asked from Turing of Machines topic and the topic-wise study notes are also useful for the preparation of various upcoming exams like GATE CSE/ BARC / NIELIT and other important upcoming competitive exams.
Table of content
A simple trick to crack GATE CS is by understanding the concept of all the subjects and by preparing GATE CSE study notes. Turing of machines is a very important topic from the Theory of Computation subject for all the computer science exams such as GATE CSE, PSU’s & NEILIT exams. These exams aim to test your understanding of a particular subject in deep level computer science and engineering.
In this article, we have provided to you the free study material for turning of machines that is crucial for any GATE CS aspirant. The study notes on turing of machines topic will further be of great help for GATE & ESE CSE as well. You can further download the turning of machines notes PDF of GATE CSE from the links provided below.
Turing Machine
The languages accepted by the Turing machine is said to be recursively enumerable. A Turing Machine (TM) is a device with a finite amount of read-only hard memory (states) and an unbounded amount of read/write tape memory.
- Recursive languages are closed under complementation, union, intersection, concatenation and Kleene closure.
- A Turing machine is said to partially decide a problem if the following two conditions are satisfied.
- The problem is a decision problem.
- The Turing machine accepts as given input if and only if the problem has an answer ‘yes’ for the input that is the Turing machine accepts the language L.
- A Turing machine is said to decide a problem if it partially decides the problem and all its computations are halting computations.
A language L is Turing-recognisable if there is a Turing machine M such that L=L(M).
A language L is Turing-decidable if there is a Turing machine M such that M decides L.
Turing-decidable language is also Turing-recognisable, but Turing-recognisable may not be Turing-decidable.
A language is recursively enumerable iff it is Turing-enumerable.
Universal Turing Machine (UTM)
- A UTM is a specified Turing machine that can simulate the behaviour of any TM.
- A UTM is capable of running any algorithm.
For simulating even a simple behaviour, a Universal Turing Machine must have a large number of states. If we modify our basic model by increasing the number of read/write heads, the number of dimensions of input tape and adding a special purpose memory, then we can design a Universal Turing Machine.
Definition of Turing Machine: What is Turing Machine?
A Turing Machine (TM) is defined as 7-tuples.
TM = (Q, Σ, Γ, δ, q0, b, F),
where, Q is a finite non-empty set of states, Σ is a non-empty set of input symbols (alphabets) which is a subset of Γ and b ∈ Σ, Γ is a finite non-empty set of tape symbols, δ is the transition function which maps (Q × Γ) to (Q × Γ × {L, R}), q0 is the initial state and q0 ∈ Q, b is the blank and b ∈ Γ, F is the set of final states and F ⊆ Q.
Transition Function of a Turing Machine
The transition function Q × Γ → Q × Γ × {L, R} states that if a Turing machine is in some state (from set Q), by taking a tape symbol (from set Γ), it goes to some next state (from set ï) by overwriting (replacing) the current symbol by another or same symbol and the read/write head moves one cell either left (L) or right (R) along the tape.
3. Construct a TM that accepts the language A = {0(2^n) | n>=0}
Behaviour of Turing Machine
Depending upon the number of moves in transition, a TM may be deterministic or non-deterministic. If TM has at most one move in a transition, then it is called Deterministic TM (DTM), if one or more than one move, then Non-deterministic TM (NTM or NDTM).
- A non-deterministic TM is equivalent to a deterministic TM.
- Some single tape TM simulates every 2 PDA (a PDA with two stacks).
- The read only TM may be considered as a Finite Automata (FA) with additional property of being able to move its head in both directions (left and right).
Language Recognition by Turing Machine
TM can be used as a language recogniser. TM recognises all languages, regular language, CFL, CSL, Type-0.
There are several ways an input string might fail to be accepted by a Turing machine
- It can lead to some non-halting configuration from which the Turing machine cannot move.
- At some point in the processing of the string, the tape head in scanning the first cell and the next move specifies moving the head left off the end of the tape.
- In either of these cases, we say that the Turing machine crashes
Variation of TM with other Automata
- Multitape Turing Machine A Turing machine with several tapes is said to be a multitape Turning machine. In a multitape Turing machine, each tape is controlled by its own independent read/write head.
- Turing machine with multiple tape is no more powerful that one tape Turing machine.
- Multi-dimensional Turing Machine A Turing machine is said to be multi-dimensional Turing machine, if its tape can be viewed as extending infinitely in more than one dimension.
- Multihead Turing Machine A multihead Turing machine can be viewed as a Turing machine with a single tape and a single finite state control but with multiple independent read/write heads.
- In one move, the read/write heads may take move independently left, right or remain stationary
- Offline Turing Machine An offline Turing machine is a multitape Turing machine whose input tape is read only (writing is not allowed). An offline Turing machine can simulate any Turing machine A by using one more tape than Turing machine A. The reason of using an extra tape is that the offline Turing machine makes a copy of its own input into the extra tape and it then simulate Turing machine A as if the extra tape were A’s input.
Halting Problem of Turing Machine: A class of problems with two output (true/false) is called solvable (or decidable) problem, if there exists some definite algorithm which always halts (also called terminates), else the class of problem is called unsolvable (or undecidable.
Recursive and Recursively Enumerable Languages
A language L is said to be recursively enumerable, if there exists a Turing machine that accepts it.
A language is recursive if and only if there exists a membership algorithm for it. Therefore, a language L on Σ is said to be recursive, if there exists a Turing machine that accepts the language L and ‘it halts on every ω∈Σ+.
Recursively enumerable languages are closed under union, intersection, concatenation and Kleene closure and these languages are not closed under complementation.
- The complement of a recursive language is recursive.
- The union of two recursive languages is recursive.
- The union of two recursive enumerable languages is recursive enumerable.
- The intersection of two recursive languages is recursive.
- There are some recursively enumerable languages which are not recursive.
- If L is recursive then, L’ is also recursive and consequently both languages are recursively enumerable.
- A language is recursive iff both it and its complement are recursively enumerable.
- A language L is lexicographically Turing-enumerable iff there is a Turing machine that lexicographically enumerates it.
- A language is recursive iff it is lexicographically Turing-enumerable.
- Every context-sensitive language is recursive.
- The family of recursively enumerable languages is closed under union.
- If a language is not recursively enumerable, then its complements cannot be recursive.
- If a language L is recursive, then it is recursively enumerable language but vice-versa is not true.
An infinite set is countable if and only if there is a one-to-one correspondence between its elements and the natural numbers. Otherwise, it is said to be uncountable.
- If Σ is a finite set then Σ ∗ is countable.
- For every alphabet Σ there is a language L ⊆ Σ ∗ that is not recursively enumerable.
- There exists a language L that is recursively enumerable but not decidable.
- The halting problem is the problem of deciding whether a given Turing machine halts when presented with a given input. The halting problem is not decidable.
GATE CS Previous Year Question Paper 2020, 2019, 2018, 2017: Download PDF
| GATE Exam | Question Paper PDF | Solution PDF |
| GATE CSE 2020 | GATE CSE 2020 Question Paper | GATE CSE 2020 Paper Solution |
| GATE CSE 2019 | GATE CSE 2019 Question Paper | GATE CSE 2019 Paper Solutions |
| GATE CSE 2018 | Download GATE CS Question Paper with Answer Key | |
| GATE CSE 2017 Set 1 | Download GATE CSE Question Paper | |
Download GATE CS Previous Year Question Papers
Thanks
The Most Comprehensive Exam Prep App!
