Contents

- CS-701 Theory of Computation Viva Preparation
- Question: what is a Turing machine?
- Question: What is an algorithm?
- Question: What is computation?
- Question: What is halting problem?
- Question: Recognizable language
- Question: Recognizer machine
- Question: Decidable Language
- Question: Transition function
- Question: What is PCP?
- Question: What is multi tape Turing machine?
- Question: Multi head Turing machine?

# CS-701 Theory of Computation Viva Preparation

### Question: what is a Turing machine?

**Answer: **This machine performs computations to check if the given in input belongs to some language or not.

Formally a Turing machine M is a 7-tuple, (Q, Σ, Г, , q0, qa, qr ), where Q, Σ, Г are all finite sets.

- Q is the set of
- Σ is the input alphabet not containing the special blank symbol
- Г is the tape or work Σ Г and □ Г
- q0 is the start
- qa is the accept
- qr is the reject
- : Q × Г → Q × Г × {L,R} is the transition

### Question: What is an algorithm?

**Answer: **Set of rules, procedures and formulas to solve specific problem.

### Question: What is computation?

**Answer: **Computation is any type of calculation, by using specific kind of model like Algorithm.

### Question: What is halting problem?

**Answer: **Problems which cannot be solved by any algorithm.

### Question: Recognizable language

**Answer: **A language is recognizable if we can think a machine which can accept that language.

### Question: Recognizer machine

**Answer: **The machine which will accept the given input or loop on it.

### Question: Decidable Language

**Answer: **If a machine halts on the language it is decidable language

OR

If a language got accepted or rejected by the machine.

### Question: Transition function

**Answer: **It describes how the machine will perform its computation.

### Question: What is PCP?

**Answer: **PCP stands for post correspondence problem in which collection of dominos is given with the top and bottom string all you have to do is make the match of the top and bottom strings by arranging the dominos.

**Question: What is multi tape Turing machine? **

**Answer: **Machine consists on more than one tape.

**Question: Multi head Turing machine? **

**Answer: **Machine consist on more than one head.