DEPARTMENT
OF COMPUTER SCIENCE AND ENGINEERING
Third
Year Computer Science and Engineering, 6th Semester
Subject Code & Name : THEORY OF COMPUTATION
UNIT-I CHURCH-TURING THESIS
1.
What is aTuring Machine?
Turing machine is a simple mathematical model of a
computer. TM has unlimited an unrestricted memory and is a much more accurate
model of a general purpose computer. The turing machine is a FA with a R/W
Head. It has an infinite tape divided into cells ,each cell holding one symbol.
2. What are the difference between finite automata and Turing Machines?
Turing machine can change symbols on its tape,
whereas the FA cannot change symbols on tape. Also TM has a tape head that
moves both left and right side ,whereas the FA doesn’t have such a tape head.
3. Define Turing Machine?
A turing machine
is a 7-tuple (Q, S, Γ, δ, q0, qaccept,
qreject) where
Q: finite set of states
S: input alphabet (cannot
include blank symbol, _)
Γ: tape alphabet, includes S and _
δ: transition function: Q ´ Γ ® Q ´ Γ ´ {L,
R}
q0: start state, q0
Î
Q
qaccept: accepting state, qaccept
Î
Q
qreject: rejecting state, qreject
Î
Q
4. What is configuration?
Turing machine
computes, changes occur in the current state, the current tape contents and the
current head location.a setting of these three items is called a configuration.
5. What is a
recursively enumerable language?
The
languages that is accepted by TM is said to be recursively enumerable (r. e )
languages. Enumerable means that the strings in the language can be enumerated
by the TM. The class of r. e languages include CFL’s.
6. Define variants of Turing Machine?
Variants are
Non
deterministic turing machine.
Mutlitape turing machine.
. Enumerators
7. What is a multitape TM?
A multi-tape
Turing machine consists of a finite control with k-tape heads and ktapes each tape is infinite in both
directions. On a single move depending on the state of finite control and
symbol scanned by each of tape heads ,the machine can change state print a new
symbol on each cells scanned by tape head, move each of its tape head
independently one cell to the left or right or remain stationary.
8. Define nondeterministic TM?
•
Arbitrarily chooses move when more than one possibility
exists
•
Accepts if there is at least one computation that
terminates in an accepting state
9. What is an algorithm?
An algorithm is a collection of
simple instruction for carrying out some task. It is sometimes called procedures or recipes.
10 What is a polynomial?
It is a sum of terms where each
term is a product of certain variables and
a constant called a
co-efficient.
Eg.6
x*x*x*y*z*z=6x3yz2
11. Define Church-Turing thesis?
In 1936 Alonzo
church used a notational system called λ-calculus to define algorithms and Alan Turing did it with his
“machines”. These two definitions were shown to be equivalent .This connection
between the informal notion and precise definition has come to be called
Church-Turing thesis
12. List the types of
description.
Formal description.
Implementation description.
High-level description.
13. What is halting
problem?
A {M,w | TM M is a TM
and M accepts w }
TM A is undecidable but TM A is
Turing – recognizable hence TM A is sometimes called the halting
problem.
14. Mention the
relationship between classes of languages.
15. Define universal Turing machine.
A universal Turing machine (UTM) is a
TM which is capable of simulating any other Turing machine from the description
of the machine.
16. What is a Diagonalization language Ld?
The
diagonalization language consists of all strings w such that the TM whose code is w does not accept when w is given as
input.
17.
Why some languages are not decidable or even Turing – recognizable?
The
reason that there are uncountable many languages yet only countably many Turing
machines. Because each Turing machine can recognize a single language and there
are more languages than Turing machines, some languages are not recognizable by
any Turing machine.
18. What do you mean by co-Turing-recognizable?
A language is called co-Turing-recognizable
if it is the complement of a Turing-recognizable language
19. Define Countable and Uncountable?
•
A set is countable if it is finite or has the
same size as N (the set of natural numbers {1, 2, 3, …})
–
Examples: N (natural numbers), Z (integers), Q
(rational numbers), E (even numbers), etc.
•
A set is uncountable if it has more elements
than N .
–
Examples: R (real numbers) É [0,1] É
Cantor set
–
20. What is a correspondence?
A function that is both one-to-one and onto
is called correspond.
BIG
QUESTIONS
1.
Explain the various techniques for
Turing machine construction.
2.
Briefly explain the different types of
Turing machines.
3.
Design a TM to accept the language L={0n1n
| n>=1}
4.
Explain how a TM can be used to
determine the given number is prime or not?
5. Prove
that if L is recognized by a TM with a two way infinite tape if it is
recognized by a TM with a one way
infinite tape
6. Prove
that Halting problem is undecidable.
7.
Design a Turing machine that accepts the
language L={an bn cn /n>1}
8.
What are the various models of Turing
Machine?
9.
With an example explain the universal Turing
machine
10.
Show that halting problem of Turing
machine is undecidable
11.
Show that a language is decidable if it
is Turing-recognizable and co- recognizable.
UNIT-II REDUCIBILITY
1.What is reduction?
A
reduction is a way of converting one problem into another in such a way
that a solution to the second problem
can be used to solve the first problem.
2. What is reducibility?
The primary
method of proving some problems are computationally unsolvable. It is called reducibility.Reducibility
always involves two problems which we call A and B. If A reduces to B, we can
use a solution to B to solve A.
3. What is linear bounded automation?
A linear
bounded automation is restricted type of Turing machine where in the tape head
isn’t permitted to move off the portion of the tape containing the input. It
has a limited amount of memory.
4. What is a
accepting computation history?
An accepting
computation history is defined as , Let M be a Turing machine and w be a input
string, for M on w is a sequence of
configuration c1,c2,…cl, Where c1 is the start configuration of M on w . cl is
the accepting configuration of M and each ci legally follows from ci-1
according to the rules of M.
5. What is a
rejecting computation history?
Let M be a
Turing machine and w be a input string , for M on w is a sequence of
configuration c1, c2 , … cl Where cl is a rejecting configuration of M on W .
6. Write down the
algorithm that decides ALBA?
The
algorithm that decides ALBA is as follows:
- L=” on input {M,w} Where M is an LBA and w is a string .
1.1 Simulate M
on w for qng^n steps until it halts
1.2 If M has
halted accept if it has accepted and reject if it has rejected . If it has not
halted , reject”.
7. Write about the
three conditions of computational
history?
Suppose
consider the input B and it has possible input C1,C2……. Cl. If B ants to check
whether the Ci satisfy the three conditions of computational history
1. C1
is a start configuration for M on w
2. Each
Ci+1 legally follows from Cp
3. Cl
is an accepting configuration for M
8. What is called
PCP?
The
phenomenon of undecidability is not confined to problems concerning automata.
An undecidable problem concerning on simple manipulation of strings is called
the post correspondence problem or PCP.
An instance
of the pcp is the collection P of dominos:
P =
{[t1/b1]}, [t2/b2],……….. [tk/bk]}
and a match is a sequence i1,i2,i3….il.. Where ti1,ti2….til
= bi1, bi2…..bil
PCP={<P>/P is an instance of the post correspondence problem with
a match}
9. How can we
construct P so that a match is an accepting computation history for M on w?
The task is to make a list of the dominos;
so that the string we get by reading off the symbols on the top is same as the
string of symbols on the bottom.This list is called a match. For example: [a/ab][b/ca][ca/a][a/ab][abc/c].Reading off
the top strings we get abcaaabc , which is same as reading off the bottom.
10. What is MPCP?
MPCP à Modified Post
Correspondence Problem, in that the match is required to start with the first
domino in the list.
MPCP =
{<P>/P is an instance of the post correspondence with a match that starts
with the first domino}.
11. What is called
mapping reducibility?
Language
“A” is mapping reducible to language B, written A<=B; if there is a
computational function f: €*à€*
, Where for every w, w € a↔ f(w) € B.
12. Define computable
function?
A turning
machine computes a function by starting with the input to the function on the
tape and halting with the output of the function on the tape a function f: €*à€*
is a computable function , if some turning machine M, on every input w, halts
with just f(w) on its tape.
Eg: All arithmetic
operations on integers.
13. What is recursion
theorem?
Let T
be a Turing machine that computes a function t: €* x €*à€*. There is a Turing
machine R that computes a function r: €*à€*, Where for every w :
r(w)=T(<R>,w).
The recursion theorem is a mathematical result
that plays an important role in advanced work in the theory of computability.
14. What is self
reference?
The
Turing machine that ignores its input and prints out a copy of its own
description, we call this as SELF.
There is a
computable function q: €*à€*, where for any string w, q(w) is the description
of a Turing machine Pw that prints out w and then halt.
15. What is computer
virus?
A computer virus is a computer program that
is designed to spread itself among computers.
Computer
virus are inactive when standing alone as
piece of code, but when placed appropriately in a host computer, thereby
infecting it and they can become activated and transmit copies of themselves to
other accessible machines.Various media can transmit viruses , including
internet and transferable disks.
16. Applications of
recursion theorem?
1. ATM
is undecidble.
2. MINTM
is not Turing recognisable
3. Fixed
point theorem.
17. What is a fixed
point?
A fixed point of a function is a value that
isn’t changed by application of the function.
18. Define formula.
A
formula is a well formed string over this alphabet.
19. What are the
Boolean operations and Quantifiers?
The form of the alphabet of this
language :
{^,v,¬,(,),for all, x , there exists,R1,….Rk}.The symbols
^,v, ¬ are called Boolean operations.The
symbols of “for all” and ”there exists” are called Quantifiers. The symbol x
denotes the variable R1,R2,..Rk ,called the relations.
20. What is atomic
formula?
A string of the form Ri (x1,x2,x3,..xj) is an atomic
formula. The value ‘j’ is the arity of the relation symbol Ri.
21. What is called
Sentence/Statement and Free variable?
A variable that isn’t bound
within the scope of a quantifier is called a Free variable. A formula with no
free variable is called a Sentence or Statement.
22. What is model?
A
universe together with an assignment of relations to relation symbol is called
a model .
A model
M is a tuple (U, P1,P2..Pk), where U is the universe and P1 through Pk are the
relations assigned to symbols R1 through Rk.
23. What is language
of a model?
Language of a model is the collection of
formulae that use only the relational symbols the model assign and that use
each relation symbol with the correct arity.
If Ǿ is a
sentence in a language of a model , Ǿ is
either true or false in that model.
24. What is decidable
theory?
Let (N,+) be the model, except without
x relation. Its theory is Th(N,+).
For example: the
formula[x+x=y] is true therefore a
member of Th(N,+).
25. What is
undecidable theory?
Let (N, + ,X) be a model
whose universe is the Natural numbers with the usual +,X relations.
Church
showed that Th(N,+,X) the theory of this model; is undecidable.
26. What is called
Turing Reducibility?
Language A is Turing
reducible to language B, written A<=TB, if A is decidable relative to B.
Turing
reducibility is a generalization of mapping reducibility.
27. What is called
Oracle Turing machine?
An
Oracle for a language B is an external device that is capable of reporting
whether any string w is a member of B.
An Oracle
Turing machine is a modified Turing machine that has the additional capability
of quering an Oracle.
28. What is an
information?
Definition of information depends upon the application.
For example: A= 0101010101010101
B= 11101110111000111
Sequence
A contain little information because it is merely a repetition of pattern
01 twenty times. In contrast sequence B
appears to contain more information.
29. What is minimal
Description?
Minimal Description of x,
written d(x), is the shortest string (M, w), where TM,M on input w halts with x on its tape.
30. What is
Descriptive complexity?
The
Descriptive complexity of x,
written k(x) is k(x) = |d(x)|
where k(x) – length
of the minimal description of x.
The
definition of k(x) is intended to capture the amount of information in the
string x.
31. When an x is a
C-compressible?
Let x be a string, say that x is
C-compressible if k(x) <= |x| - C.
BIG
QUESTIONS
1. Explain
how Post correspondence problem is undecidable?
2. Prove
that HALTTM is undecidable.
3. Prove
that ETM is undecidable.
4. Prove
that REGULAR TM is undecidable.
5. Prove
that EQ TM is undecidable.
6. Prove
that A LBA is decidable.
7. Prove
that E LBA is
undecidable.
8. Prove
that ALL CFG is undecidable.
9. State
and prove PCP is undecidable.
10. Prove
that EQ TM is neither Turing-recognizable nor
co-Turing-recognizable.
11. State
and prove recursion therorem
12. Explain
self-reference in detail.
13. Explain
decidability of logical theories?
14. Write
a brief note on a decidable theory?
15. Write
a brief note on an undecidable theory?
16. Explain
Turing reducibility?
UNIT-III
TIME COMPLEXITY
1.Define complexity
•
Complexity Theory = study of what is computationally
feasible (or tractable) with limited
resources:
–
running time
–
storage space
–
number of random bits
–
degree of parallelism
–
rounds of interaction
others…
2. Define time complexity
The time complexity of a TM M is a function f:N → N, where
f(n) is the maximum number of steps M uses on any input of length n.
3. Define Asymptotic Notation
Running time of an algorithm as a function of input
size n for large n. Expressed using only the highest-order term in the
expression for the exact running time
4. What do you mean by polynomial and
exponential bounds?
Bounds of the form nc for c greater than 0 .such a
bound are called polynomial bounds.Bounds of the form 2(n∂ )
. s.uch a bound are called exponential
bounds when ∂ is a real number greater
than 0
5. What is Hamiltonian path?
A Hamiltonian path
in a directed graph G is a directed path that goes through each
node exactly once. We consider a special case of this problem where the
start node
and target node are fixed.
6. List the types of Asymptotic Notation.
•
Big Oh (O) notation provides an upper
bound for the function f
•
Omega (Ω) notation provides a lower-bound
•
Theta (Q) notation is used when an algorithm can
be bounded both from above and below by the same function
•
Little oh (o) defines a loose upper
bound.
7. What is Hamiltonian path?
A Hamiltonian
path in a directed graph G is a directed path that goes through
each
node exactly once. We consider a special case of this
problem where the start node
and target node are fixed.
8. Defines brute –force search
Exponential time algorithms typically arise
when we solve by searching through a spsce of
solutions called brute –force search
9. Define running time.
The running time of N is the
function N®N,
wheref(n) is the maximum of steps that N
uses on any branch of its computation on any of length n.
10. Define class P
The class of
all sets L that can be recognized in polynomial time by deterministic TM.
The class of all decision problems
that can be decided in polynomial time.
11. Define class NP.
Problems
that can be solved in polynomial time by
a nondeterministic TM. Includes all problems in P and some problems possibly outside P.
12. Define verifier.
A verifier for a
language A is an algorithm V, where
A = {w | V
accepts <w,c> for some string c}.
We measure
the time of a verifier only in terms of the length of w, so a polynomial
time verifier runs in
polynomial time in the length of w.
A
language A is polynomially verifiable if it has a
polynomial time verifier. The above string c, used as additional
information to verify that wÎA, is called a certificate,
or proof, of membership in
A.
13. What do you mean by NP-completeness?
If a
polynomial time algorithm exists for any of the NP-complete problems, all
problems in NP would be
polynomial time solvable. These problems are called by NP-completeness
14. Define polynomial time computable
functions.
A function f:£ ®£* is a polynomial
time computable functions if some polynomial time turing machine exists that halts with just
f(w) on its tape. when started on any input w.
15. Define polynomial time mapping reducible.
We say that A is polynomial
time mapping reducible, or simply polynomial time reducible,
to B, written A£PB,
if a polynomial time computable function f: S* ® S* exists s.t. for every string wÎS*, wÎA iff f(w)ÎB.
Such a function f is called a polynomial time reduction of
A to B.
16. Define
literal.
A literal is a Boolean
variable x or a negated Boolean variable x.
17. Define clause.
A clause s several literals connected with Ús,
as in (x Ú
y Ú
z Ú
t).
18 .Define conjunctive normal form.
A
Boolean formula is in conjunctive normal form, called a cnf-formula,
if it comprises several clauses
connected with Ùs,
as in
(x Ú
y Ú
z Ú
t) Ù (x Ú
z) Ù (x Ú yÚ t)
•
A cnf-formula is
a 3cnf-formula if all the clauses have 3 literals, as in
(x Ú y
Ú
z) Ù (x Ú z Ú
t) Ù (x Ú y Ú t)
Ù
(z Ú
BIG QUESTIONS
1.
Show that every CFL is a member of class
P problem
2.
Show that a language is in NP if it is
decided by some non deterministic polynomial time Turing machine.
3.
Explain the cook-Levin theorem
4.
Explain about the vertex cover problem.
5.
Explain about Hamiltonian path problem.
6.
Briefly discuss about the subset sum
problem?
7.
With an example explain BIG-O and
SMALL-O notation.
8.
Explain about Analyzing algorithms in
detail?
9.
Explain CLASS P in briefly with an
example?
10.
State and prove PATH €
P.
11.
State and prove RELPRIME €
P.
12.
Prove that every context-free language
is a member of P.
13.
Explain with an example CLASS-NP?
UNIT –V Advanced Topics in Complexity
Theory
- Define Approximation algorithm?
An
Approximation
algorithm is designed to find approximately optimal solution. An
approximation algorithm for a minimization problem is K-Optimal if it always
find a solution that is not more than K times optimal.
- What is MAX-CUT, Cut, and Cut edge?
An
Approximation Algorithm for the maximization problem called MAX-CUT . A Cut is
an undirected graph is a separation of vertices V in to two disjoint subsets S
and T.
- What is Cut edge and Uncut edge?
A Cut edge is an
edge that goes between a node in S and a node in
T. An uncut edge
is an edge that is not a cut edge.
- What is Probabilistic Algorithm?
A Probabilistic
Algorithm is an algorithm designed to use the outcome
of
a random process .
- What is a Probabilistic Turing Machine?
A Probabilistic
Turing Machine is a type of non deterministic Turing
Machine .it is
defined as
Pr[b] = 2-k
Where K be the
number coin flip steps occur on branch B.
- What is the Class BPP?
BPP is the class
of languages that are recognized by probabilistic
Polynomial time
Turing Machine with an error probability of 1/3.
- What is Small Probability of an error?
Error Probability bounds that depends on input length n. if Probability €=2-n
indicates an exponentially small probability of an error.
- What is a Prime, Composite?
A Prime
Number is an integer greater than
1 that is not divisible by
positive numbers
other than 1 and itself. A non prime number greater than 1 is
Called Composite.
- Define Chinese remainder theorem/ Fermat’s little theorem?
The Chinese
remainder theorem says that a one-to one correspondence exists between £pq
and £p x £q if p and q are relatively prime. Each number r є £pq Correspond to the pair (a,b), where a є £p and b є £q. such that
r ≡ a (mod p)
r ≡ b (mod q),
- what is Fermat’s Test?
A type of “test”
for primality called a fermat test.
- What is RP?
RP
is the class of languages that are recognized by probabilistic polynomial time
Turing machine s where inputs in language are accepted with a probability of
atleast ½ and inputs not in a language are rejected with a probability of 1.
- What is called a Branching Program?
A Branching
Program is a model of computation used in complexity
theory and in
certain practical areas such as computer aided design. This
model represents a decision process that
queries the values of input variables and basis decisions about the way to proceed on the answers to
those queries.
- What are query nodes?
A
Branching Program is a directed acyclic graph where all nodes are labeled by
variables, except for two output nodes labeled nodes 0 0r 1. The nodes that are
labeled by variables are called Query nodes.
- What is a Read-Once branching program?
A
Read-Once
branching program is one that can query each variable at most one time
on every directed path from the start node to an output node.
EQROBP = {(B1,B2)| B1 and B2 are
equivalent read-once branching program}
- What is Alternation?
Alternation is a
generalization of non determinism that has proven to
be useful in
elucidating relationships among complexity classes and in classifying specific
problems according to their complexity.
- What is an Alternating Turing Machine?
An Alternating
Turing Machine is a Non deterministic Turing
machine with an
additional feature. It states, except for qaccept and qreject are divided into
universal states and existential states
- What is an Alternating Time and Space?
An Alternating
Time and Space complexity classes are defined as
ATIME (t(n) ) = {L|L is a language decided by an O(t(n))
time
Alternating
Turing Machine}
ASPACE (f(n)) = {L|L is a language
decided by O(f(n) space
Alternating
Turing Machine}
- Define Tautology?
A tautology
is a Boolean formula that evaluates to 1 on every assignment to its variables.
Let TAUT = ((ф) |ф is a
tautology)
- Give the algorithm to show that TAUT is in AP?
The
following algorithm shows that TAUT is in AP:
“On input (ф):
1.
Universally select all assignments to the variables of
ф.
2.
for the particular assignment, evaluate ф
3.
If ф evaluates to 1 , accept, otherwise Reject
- Define Minimal Formula?
A minimal
formula is one that has no shorter equivalent. Let Minimal
Formula
is denoted by:
MIN-FORMULA
= {(ф) |ф is a minimal Boolean formula}
- Give the algorithm to show that MIN-FORMULA is in AP?
The
following algorithm shows that TAUT is in AP:
“On input (ф):
1.
Universally select all formulas Ψ that are shorter than
ф
2.
Existentially select an assignment to the variables of
ф
3.
Accept if the formulas evaluate to different values. Reject
if they evaluate to the same values
- What is Σi – alternating Turing Machine and πi –Turing Machine?
Σi – alternating Turing Machine is an alternating
Turing Machine that
contain at most i runs of universal
or existential steps , starting with existential
steps
πi –Turing Machine is similar except that it starts
with universal steps.
- What is Interactive Proof Systems?
Interactive Proof Systems provide a way to define a
probabilistic
analog
of the class NP, much as probabilistic polynomial time algorithm provides a
probabilistic analog to P. The development of interactive proof system has
profoundly affected complexity theory and has led to important advances in the
field of cryptography and approximation algorithm.
- Define Verifier
We define a verifier to be a function V that computes its next transmission
.the function v has three inputs:
1.Input String
2.Random Input
3.Partial message History
- Define Prover
Prover is a party with unlimited computational ability We
define it to be
function P with two inputs:
1.
Input string
2.
Partial Message History.
- Define Parallel Computation
A Parallel Computer is one that can perform multiple operations
simultaneously. Parallel computers may solve certain problems must faster than
sequential computers, which can do a single operation at time.
- What is PRAM?
Parallel Random Access Machine: In the PRAM model idealized
processors with a simple instruction set patterned on actual computers interact
through the shared memory
- What are the factors to be consider to achieve a particular parallel time complexity?
We have to consider the simultaneous size and depth of the single circuit
family in order to achieve a particular parallel time.
- When language B is stated to be P-Complete?
1. B Є P and
2. Every A in P is log space reducible to B
- Why we should maintain a secret key?
The
Secret
Key is a piece of information that is used by encrypting and decrypting
algorithm. Maintain the secrecy of the key is crucial to the security of the
code because any person with access to the key can encrypt and decrypt
messages
- What is called one time pad?
A key that is as long as the combined message length is called a one
time pad. Every bit of a one-time pad key is used to encrypt a bit of
the message and then that bit of the key is discarded.
- Define One Way Permutation
A One Way Permutation is a length –preserving permutation f with the following two properties
1.
It is computable in polynomial time
2.
For every probabilistic polynomial time Turing Machine
M, every K, and sufficiently large n, if we pick a random w of length n and run
M on input w,
PrM,w[M(f(w))=w] ≤ n-k
Here PrM,w means that the probability is taken over the random
choices made by M and random selection of w
- Define One Way function
A one way function is a length –preserving function f with the
following two properties
1.
It is computable in polynomial time
2.
For every probabilistic polynomial time Turing Machine
M, every K, and sufficiently large n, if we pick a random w of length n and run
M on input w,
Pr[M(f(w))=y where f(y)=f(w)] ≤ n-k
- Define Trapdoor?
A trapdoor function is a length –Preserving indexing function
f: ∑*×∑*→∑*
with an auxiliary probabilistic
polynomial time TM G and an auxiliary function h: ∑*×∑*→∑*.
No comments:
Post a Comment