Computation and languages, Theory of Computation

Assignment Help:

When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is their sum. Two problems of particular interest in Computer Science, which you have probably encountered previously, are the Traveling Salesperson Problem (TSP) and the Halting Problem. In TSP one is given a list of distances between some number of cities and is asked to ?nd the shortest route that visits each city once and returns to the start. In the Halting Problem, one is given a program and some appropriate input and asked to decide whether the program, when run on that input, loops forever or halts. Note that, in each of the cases the statement of the problem doesn't give us the actual values we need to provide the result for, but rather just tells us what kind of objects they are. A set of actual values for a problem is called an instance of the problem. (So, in this terminology, all the homework problems you did throughout school were not problems but were, rather, instances of problems.)

A problem, then, speci?es what an instance is, i.e., what the input is, and how the solution, or output, must be related to the that input.
There are a number of things one might seek to know about a problem, among them:

• Can it be solved algorithmically; is there a de?nite procedure that solves any instance of the problem in a ?nite amount of time? Inother words, is it computable. Not all problems are computable; the halting problem is the classic example of one that is not.

• How hard is it to solve? What kind of resources are needed and how much of those resources is required? Again, some problems are harder than others. TSP is an example of a frustrating class of problems that have no known e?cient solution, but which have never been proven to be necessarily hard.


Related Discussions:- Computation and languages

Decidability, examples of decidable problems

examples of decidable problems

Give a strictly 2-local automaton, Let L 3 = {a i bc j | i, j ≥ 0}. Give ...

Let L 3 = {a i bc j | i, j ≥ 0}. Give a strictly 2-local automaton that recognizes L 3 . Use the construction of the proof to extend the automaton to one that recognizes L 3 . Gi

Production, How useful is production function in production planning?

How useful is production function in production planning?

Language accepted by a nfa, The language accepted by a NFA A = (Q,Σ, δ, q 0...

The language accepted by a NFA A = (Q,Σ, δ, q 0 , F) is NFAs correspond to a kind of parallelism in the automata. We can think of the same basic model of automaton: an inpu

#turing machine, #can you solve a problem of palindrome using turing machin...

#can you solve a problem of palindrome using turing machine with explanation and diagrams?

Push down automata, Construct a PDA that accepts { x#y | x, y in {a, b}* su...

Construct a PDA that accepts { x#y | x, y in {a, b}* such that x ? y and xi = yi for some i, 1 = i = min(|x|, |y|) }. For your PDA to work correctly it will need to be non-determin

Context free grammar, A context free grammar G = (N, Σ, P, S)  is in binary...

A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi

Sketch an algorithm for recognizing language, Suppose A = (Σ, T) is an SL 2...

Suppose A = (Σ, T) is an SL 2 automaton. Sketch an algorithm for recognizing L(A) by, in essence, implementing the automaton. Your algorithm should work with the particular automa

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd