CS 701 Theory of Computation viva questions

What is halting problem?
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.

Tell the tuples of Turing Machine.
A Turing machine is a 7-tuple (Q, Σ, Γ, δ, q0, qaccept, qreject) such that
1. Q is the set of states.
2. Σ is the input alphabet not containing the special blank symbol _.
3. Г is the tape or work alphabet. Σ  Г and □  Г
4. q0 is the start state.
5. qa is the accept state.
6. qr is the reject state.

7. : Q × Г → Q × Г × {L,R} is the transition function.

What is a Turing machine?
A Turing machine is an idealised computing device consisting of a read/write head (or 'scanner') with a paper tape passing through it. The tape is divided into squares, each square bearing a single symbol--'0' or '1', for example. This tape is the machine's general purpose storage medium, serving both as the vehicle for input and output and as a working memory for storing the results of intermediate steps of the computation.

What do you know about Configuration?

To describe the operation of Turing machine we use configuration. A configuration for a Turing machine is an ordered pair of the current state and the tape contents with the symbol currently under the head marked with underscore.
As a TM computes changes occur in three things:
1. Its state.
2. The tape contents.
3. It head position.

A setting of all these things is called a configuration. Hence a configuration tells us what state the machine is in, what is currently written on the tape and where the tape head exactly is.

What is an Enumerator?
Enumerators are devices that do not take any input and only produce output.
An enumerator is a Turing machine that lists, possibly with repetitions, elements of some set S, which it is said to enumerate. A set enumerated by some enumerator is said to be recursively enumerable.

What is the function of Dovetailing?
 in algorithm design, is a technique that interweaves different computations, performing them essentially simultaneously. Algorithms that use dovetailing are sometimes referred to as dovetailers.
What is Multi Tape Turing machine?
multi-tape Turing machine is like an ordinary Turing machine with several tapes. Each tape has its own head for reading and writing. Initially the input appears on tape 1, and the others start out blank.

What is the difference between Complexity and Computability?
Computability Theory is concerned with identifying one particular class of INTRACTABLE PROBLEMS (Those for which no `effective' algorithm exists) One aim of Computational Complexity Theory is to identify solvable problems that are intractable in the sense that No Efficient Algorithm Exists which solves them.

What is NP Complete?
The abbreviation NP refers to "nondeterministic polynomial time". In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard.
NP completeness
A language is A called NP-hard if every language L Є NP. L p ≤ A
Notice that a NP-hard language in some sense harder than all the languages in NP.
Definition:
A language A is called NP-complete if
1. A is NP-hard.
2. A is in NP.
It is not at all clear that there are NP-complete languages. In fact, if they exist it would be an
amazing fact. These languages will have “all the complexity” of the class NP. They will be extremely important because of the following theorem.


Comments