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

# Help, #Your company has 25 licenses for a computer program, but you disco...

#Your company has 25 licenses for a computer program, but you discover that it has been copied onto 80 computers. You informed your supervisor, but he/she is not willing to take an

#titl, matlab v matlab

matlab v matlab

Emptiness problem, The Emptiness Problem is the problem of deciding if a gi...

The Emptiness Problem is the problem of deciding if a given regular language is empty (= ∅). Theorem 4 (Emptiness) The Emptiness Problem for Regular Languages is decidable. P

Regular languages, LTO was the closure of LT under concatenation and Boolea...

LTO was the closure of LT under concatenation and Boolean operations which turned out to be identical to SF, the closure of the ?nite languages under union, concatenation and compl

Generalization of the interpretation of local automata, The generalization ...

The generalization of the interpretation of strictly local automata as generators is similar, in some respects, to the generalization of Myhill graphs. Again, the set of possible s

Algorithm, What is the Best way to write algorithm and construct flow chart...

What is the Best way to write algorithm and construct flow chart? What is Computer? How to construct web page and Designe it?

Local and recognizable languages, We developed the idea of FSA by generaliz...

We developed the idea of FSA by generalizing LTk transition graphs. Not surprisingly, then, every LTk transition graph is also the transition graph of a FSA (in fact a DFA)-the one

Convert chomsky normal form into binary form, Suppose G = (N, Σ, P, S) is a...

Suppose G = (N, Σ, P, S) is a reduced grammar (we can certainly reduce G if we haven't already). Our algorithm is as follows: 1. Define maxrhs(G) to be the maximum length of the

Mealy machine, Construct a Mealy machine that can output EVEN or ODD Accord...

Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1''s encountered is even or odd.

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