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

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.

Mapping reducibility, (c) Can you say that B is decidable? (d) If you someh...

(c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?

Trees and graphs , Trees and Graphs Overview: The problems for this ...

Trees and Graphs Overview: The problems for this assignment should be written up in a Mircosoft Word document. A scanned hand written file for the diagrams is also fine. Be

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

Turing machine , Let ? ={0,1} design a Turing machine that accepts L={0^m ...

Let ? ={0,1} design a Turing machine that accepts L={0^m 1^m 2^m } show using Id that a string from the language is accepted & if not rejected .

Finiteness problem for regular languages, The fact that the Recognition Pro...

The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

Pendulum Swings, how many pendulum swings will it take to walk across the c...

how many pendulum swings will it take to walk across the classroom?

Distinguish between mealy and moore machine, Distinguish between Mealy and ...

Distinguish between Mealy and Moore Machine? 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