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?
A 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
Post a Comment
any suggestion on my side