Scribd
Upload
36 views11 pages

NDTM vs DTM: Key Differences Explained

The document compares Deterministic Turing Machines (DTM) and Non-Deterministic Turing Machines (NDTM), highlighting differences in their transition functions, execution nature, acceptance criteria, speed, real-world applicability, and computational power. It also discusses the Halting Problem, explaining that there is no general algorithm to determine if a given program will halt or enter an infinite loop, making it an undecidable problem. Additionally, it briefly mentions recursive and recursively enumerable languages.

Uploaded by

ujjwalsingh52022
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
36 views11 pages

NDTM vs DTM: Key Differences Explained

The document compares Deterministic Turing Machines (DTM) and Non-Deterministic Turing Machines (NDTM), highlighting differences in their transition functions, execution nature, acceptance criteria, speed, real-world applicability, and computational power. It also discusses the Halting Problem, explaining that there is no general algorithm to determine if a given program will halt or enter an infinite loop, making it an undecidable problem. Additionally, it briefly mentions recursive and recursively enumerable languages.

Uploaded by

ujjwalsingh52022
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Unit -5

Difference Between Deterministic TM and Non-Deterministic TM (NDTM)

Feature Deterministic TM (DTM) Non-Deterministic TM (NDTM)

Transition For every (state, symbol) pair, exactly For a (state, symbol) pair, multiple moves
Function one move is defined. may be possible.

Deterministic – only one path of Non-deterministic – can take many possible


Nature
execution. paths simultaneously.

Works like a step-by-step program: Like a parallel universe machine trying all
Execution
one instruction at a time. options at once.

Accepts if one sequence of moves Accepts if any possible sequence of moves


Acceptance
leads to the accept state. leads to the accept state.

May take longer if many paths exist — Can be faster in theory, since it checks all
Speed
it checks one at a time. paths simultaneously.

Physically realizable (used in theory Theoretical only – used to study complexity


Real-world
and practical models). (e.g. NP problems).

Equivalent in power to NDTM (can Equivalent to DTM in power, but more


Power simulate NDTM with exponential efficient in solving some problems
time). theoretically.
Halting Problem

Given a program/algorithm will ever halt or not?


Halting means that the program on certain input will accept it and halt or reject
it and halt and it would never go into an infinite loop. Basically halting means
terminating. So can we have an algorithm that will tell that the given program
will halt or not. In terms of Turing machine, will it terminate when run on
some machine with some particular given input string. The answer is no we
cannot design a generalized algorithm which can appropriately say that given a
program will ever halt or not?
The only way is to run the program and check whether it halts or not.
We can refrain the halting problem question in such a way also: Given a
program written in some programming language(c/c++/java) will it ever get
into an infinite loop(loop never stops) or will it always terminate(halt)?
This is an undecidable problem because we cannot have an algorithm which
will tell us whether a given program will halt or not in a generalized way i.e by
having specific program/[Link] general we can’t always know that’s
why we can’t have a general [Link] best possible way is to run the
program and see whether it halts or [Link] this way for many programs we can
see that it will sometimes loop and always halt
Recursive and Recursively Enumerable Language

You might also like