Abstract model for an algorithm solving a problem, Theory of Computation

These assumptions hold for addition, for instance. Every instance of addition has a unique solution. Each instance is a pair of numbers and the possible solutions include any third number. We can systematically list all instances along with all possible solutions by systematically listing all triples of numbers. This is not completely trivial-we can't, for instance, list all triples starting with 0 and then all triples starting with 1, etc. Since there are in?nitely many triples starting with zero, we would never get around to listing any starting with one. Suppose, though, that we are only concerned with the Natural Numbers, {0, 1, . . .}. If we ?rst list all triples that sum to zero (i.e., just the triple h0, 0, 0i) and then all triples that sum to one (i.e., h1, 0, 0i, h0, 1, 0i, h0, 0, 1i), etc., we are guaranteed that we will eventually list any given triple.

With the exception of the assumption that the solution is unique (which can be fudged in a variety of ways) these assumptions are pretty nearly minimal. We can't even consider solving a problem algorithmically unless every instance has a solution. An algorithm must produce some answer for every instance. If there is no answer for some instance, then whatever answer it produces will necessarily be wrong. (Note that if we modify the problem to require that we return "No Solution" in the case that none exists, we will have converted it into a problem that has a solution for every instance-albeit one that sometimes has the solution "No Solution".) The third assumption is true of every reasonable problem. In fact, it takes a fairamount of the theory of computation to even get to the point where we can argue that problems that don't satisfy the assumption might exist. Under these assumptions we can reduce our model to a machine for checking the correctness of solutions:

1809_Abstract model for an algorithm solving a problem.png

Posted Date: 3/20/2013 5:56:13 AM | Location : United States







Related Discussions:- Abstract model for an algorithm solving a problem, Assignment Help, Ask Question on Abstract model for an algorithm solving a problem, Get Answer, Expert's Help, Abstract model for an algorithm solving a problem Discussions

Write discussion on Abstract model for an algorithm solving a problem
Your posts are moderated
Related Questions
The objective of the remainder of this assignment is to get you thinking about the problem of recognizing strings given various restrictions to your model of computation. We will w

The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automa

We can then specify any language in the class of languages by specifying a particular automaton in the class of automata. We do that by specifying values for the parameters of the


You are required to design a system that controls the speed of a fan's rotation. The speed at which the fan rotates is determined by the ambient temperature, i.e. as the temperatur

S-->AAA|B A-->aA|B B-->epsilon

Different types of applications and numerous programming languages have been developed to make easy the task of writing programs. The assortment of programming languages shows, dif

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

what are the advantages and disadvantages of wearable computers?

1. Simulate a TM with infinite tape on both ends using a two-track TM with finite storage 2. Prove the following language is non-Turing recognizable using the diagnolization