Non-Deterministic Turing Machine

Introduction

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

                                                                          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

Definition

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.