- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

A Turing machine (TM) can be formally described as seven tuples −

(Q,X,∑,δ,q0,B,F)

Where,

Q is a finite set of states.

X is the tape alphabet.

∑ is the input alphabet.

δ is a transition function:δ𝛿:QxX->QxXx{left shift, right shift}.

q0 is the initial state.

B is the blank symbol.

F is the final state.

A Turing machine T recognises a string x (over ∑) if and only when T starts in the initial position and x is written on the tape,

T halts in a final state.

T is said to recognize a language A, if x is recognised by T and if and only if, x belongs to A.

Be aware that while running a TM, you can also read/write other symbols from/onto a tape, not necessarily only those from the alphabet A.

A Turing machine T does not recognize a string x, if T does not halt in a state that is not final.

There are TMs which for an input don’t halt at all and run forever.

**Example 1**

Implementation-level descriptions of a Turing machine that decides the following language over the alphabet {0, 1}.

{w|w contains an equal number of 0s and 1s }

M = “On input string w −

Scan tape and mark the first 0 which has not been marked. If no unmarked 0 is found, go to stage 4. Otherwise, move the head back to the front of the side of the tape.

Scan tape and mark first 1 which has not been marked. If no unmarked then 1 is found, reject.

Move the head back to front of the tape and go to stage 1.

Move the head back to the front of the tape. Scan the tape to see if any unmarked 1s still remain. If none are found, accept; otherwise, reject.”

**Example 2**

Give a high level description of a TM which accepts the language A, where A consists of all strings that represent undirected graphs are connected.

A = {<G>|G is a connected undirected graph}

A = {<G>|G is a connected undirected graph}

M = “On input string <G> −

Select the first node of G and mark it.

Repeat the following stage until no new nodes are marked −

For each node in G, if it is attached by an edge then, mark to a node that is already marked.

Scan all nodes of G to determine whether they all are marked or not. If they are, accept; otherwise, reject.”

- Related Questions & Answers
- Design Turing machine for multiplication
- Construct Turing machine for subtraction
- Construct Turing machine for addition
- Explain about a non-deterministic Turing Machine?
- Explain the basic properties of the Turing machine?
- What is Turing Machine in TOC?
- Explain the universal Turing machine in TOC
- Distinguish between Finite Automata and Turing Machine
- Explain Turing Machine variant Two Stack PDA?
- Explain Multi tape Turing Machine in TOC?
- What are the Turing machine variations in TOC?
- Draw a Turing machine to find 1’s complement of a binary number
- Draw a Turing machine to find 2’s complement of a binary number
- Construct a Turing Machine for language L = {0n1n2n | n≥1}
- Construct a Turing Machine for language L = {ww | w ∈ {0,1}}

Advertisements