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

Assignment Help:

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


Related Discussions:- Abstract model for an algorithm solving a problem

Turing machine, Can v find the given number is palindrome or not using turi...

Can v find the given number is palindrome or not using turing machine

Decision Theroy, spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8...

spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8%, l= 5% The organization estimates that 75% of all messages it receives are spam messages. If the cost of not blocking a

Universality problem, The Universality Problem is the dual of the emptiness...

The Universality Problem is the dual of the emptiness problem: is L(A) = Σ∗? It can be solved by minor variations of any one of the algorithms for Emptiness or (with a little le

Turing machine, prove following function is turing computable? f(m)={m-2,if...

prove following function is turing computable? f(m)={m-2,if m>2, {1,if

Union, Intuitively, closure of SL 2 under intersection is reasonably easy ...

Intuitively, closure of SL 2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a

Applying the pumping lemma, Applying the pumping lemma is not fundamentally...

Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

Differentiate between dfa and nfa, Differentiate between DFA and NFA. Conve...

Differentiate between DFA and NFA. Convert the following Regular Expression into DFA. (0+1)*(01*+10*)*(0+1)*. Also write a regular grammar for this DFA.

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