Turing Machine
Turing Machine recognizes the recursive enumerable language. Turing Machine is more powerful than any other automata such as finite automata, PDA and LBA. TM accepts recursive enumerable language by using universal acceptance mechanism Turing Machine enumerates the recursive enumerable language.
Turing Machine computes the partial recursive function. Turing Machine can be modeled as Deterministic Turing Machine (DTM) or Non-deterministic Turing Machine (NTM). By default, a Turing Machine is a DTM. The power of DTM and NTM is the same.
1. Turing Machine Acts as Recognizer or Acceptor: Turing Machine that accepts or recognizes the
strings of a recursive enumerable language (L) over an input alphabet ∑.
2. Turing Machine Acts as enumerator: Turing Machine enumerates the string of recursive enumerable language over the input alphabet ∑.
Specification of Turing Machine
The Turing machine is represented as a seven tuple as follows:
TM = (Q, Σ, Γ, δ, q0, B, F)
where Q = set of finite states, Σ = input alphabet (Σ ⊆ Γ), Γ = tape alphabet, and δ = transition function;
DTM δ : Q × Γ→ Q × Γ × {L, R}
NTM δ : Q × Γ→ 2Q × Γ × {L, R}
B= blank symbol (B ∈ Γ)
F= final states (F ⊆ Q)
- The argument of δ are
As for DTM δ : Q × Γ→ Q × Γ × {L, R}
“The current state of the control unit and the current tape symbol being read (i.e. Q × Γ). The result is a new state of the control unit, a new tape symbol, which replaces the old one and a move symbol, L or R (i.e. Q × Γ × { L, R}). The move symbol indicates whether the read-write head moves left or right one cell after the new symbol has been written on the tape”. - Both non deterministic Turing machine or deterministic Turing machine have same power and they
are interconvertible. - No logical machine can have more power than Turing machine.
Dear Aspirants,
Your preparation for GATE, ESE, PSUs, and AE/JE is now smarter than ever — thanks to the MADE EASY YouTube channel.
This is not just a channel, but a complete strategy for success, where you get toppers strategies, PYQ–GTQ discussions, current affairs updates, and important job-related information, all delivered by the country’s best teachers and industry experts.
If you also want to stay one step ahead in the race to success, subscribe to MADE EASY on YouTube and stay connected with us on social media.
MADE EASY — where preparation happens with confidence.
MADE EASY is a well-organized institute, complete in all aspects, and provides quality guidance for both written and personality tests. MADE EASY has produced top-ranked students in ESE, GATE, and various public sector exams. The publishing team regularly writes exam-related blogs based on conversations with the faculty, helping students prepare effectively for their exams.
