MS Computer Science Virtual University of Pakistan

CS-701 Theory of Computation Viva Preparation

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.

  1. Q is the set of
  2. Σ is the input alphabet not containing the special blank symbol
  3. Г is the tape or work Σ Г and □    Г
  4. q0 is the start
  5. qa is the accept
  6. qr is the reject
  7. : 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


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.