**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, Σ, Γ, δ, q

_{0}, q_{accept}, q_{reject}) 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.

## No comments:

## Post a Comment