Computation and languages, Theory of Computation

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.

Posted Date: 3/20/2013 5:50:25 AM | Location : United States

Related Discussions:- Computation and languages, Assignment Help, Ask Question on Computation and languages, Get Answer, Expert's Help, Computation and languages Discussions

Write discussion on Computation and languages
Your posts are moderated
Related Questions
A common approach in solving problems is to transform them to different problems, solve the new ones, and derive the solutions for the original problems from those for the new ones

Computation of a DFA or NFA without ε-transitions An ID (q 1 ,w 1 ) computes (qn,wn) in A = (Q,Σ, T, q 0 , F) (in zero or more steps) if there is a sequence of IDs (q 1

The Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes

automata of atm machine

How useful is production function in production planning?

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

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

Automata and Compiler (1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last f

Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG too. Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the sec