Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Frequently Asked Questions
What is meant by regular expression?
Write a regular expression for a set of vowels?
What are Regular Language and Regular Grammar?
Last Updated: Mar 27, 2024

Non-Deterministic Turing Machine

Author Anant Dhakad
0 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM


In this article, we will learn about Non-deterministic Turing machines.

Turing machines: It consists of an infinite length tape on which read and write operations can be performed. There is an endless number of cells on the tape, where each cell contains an input symbol or a special symbol called a blank. A head pointer points to the cell currently being read, moving in both directions.

Read About - Moore Machine

Turing Machine

                                                                          Fig: Turing machine(source)

Let us discuss a variation of the Turing machine, a Non-Deterministic Turing machine.

Non-Deterministic Turing machine: In a Non-Deterministic Turing Machine, the TM can take a set of actions for each state and symbol. As a result, the transitions are not deterministic in this case. A non-deterministic Turing Machine's computation is a tree of configurations achieved from the initial configuration. Input is accepted only if there exists at least one node of the tree, which is an accept state. The non-deterministic Turing Machine is called a Decider if all branches of the computational tree terminate on all inputs. If all branches are rejected for some input, the input is also rejected.\


                                          Fig: Non-Deterministic Turing machine(source)

Also read,  Arden's theorem


We can define a Non-Deterministic Turing machine formally as a 6-tuple M = (Q, X, ∑, δ, q0, B, F) where, 

  • Q is the finite set of states
  • X is the tape alphabet/symbol
  • is the finite set of symbols(the tape alphabet)
  • δ is a transition function;
    δ : Q × X → P(Q × X × {Left_shift, Right_shift}).
  • q0 ∈ Q  is the initial state
  • B ∈ ∑ is the blank symbol
  • F ⊆ Q is the set of accepting states

Also see, Turing Machine in TOC.

Frequently Asked Questions

What is meant by regular expression?

A regular expression can also be defined as a pattern sequence that represents a string. It is most commonly used in pattern matching with strings or string matching. 

Write a regular expression for a set of vowels?

The regular expression for a set of vowels is ( a ∪ e ∪ i ∪ o ∪ u ). 

What are Regular Language and Regular Grammar?

Grammar is considered regular if it has rules of the form A -> a or A -> aB or A -> ɛ where ɛ  is a special symbol known as NULL and a language is considered regular if it can be expressed using regular expressions. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job


Cheers if you reached here!! 

In this article, we learnt about Non-Deterministic Turing machines. We also the formal definition of a Non-Deterministic Turing machine.

Recommended Readings:

You can also consider our Online Coding Courses such as the Machine Learning Course to give your career an edge over others.


Live masterclass