Abstract model of computation, Theory of Computation

When we say "solved algorithmically" we are not asking about a speci?c programming language, in fact one of the theorems in computability is that essentially all reasonable programming languages are equivalent in their power. Rather, we want to know if there is an algorithm for solving it that can be expressed in any rigorous way at all. Similarly, we are not asking about whether the problem can be solved on any particular computer, but whether it can be solved by any computing mechanism, including a human using a pencil and paper (even a limitless supply of paper).

What we need is an abstract model of computation that we can treat in a rigorous mathematical way. We'll start with the obvious model:

1190_Abstract model of computation.png

Here a computer receives some input (an instance of a problem), has some computing mechanism, and produces some output (the solution of that instance). We will refer to the con?guration of the computing mechanism at a given point in it's processing as its internal state. Note that in this model the computer is not a general purpose device: it solves some speci?c problem. Rather, we consider a general purpose computer and a program to both be part of a single machine. The program, in essence, specializes the computer to solve a particular problem.

Posted Date: 3/20/2013 5:52:57 AM | Location : United States

Related Discussions:- Abstract model of computation, Assignment Help, Ask Question on Abstract model of computation, Get Answer, Expert's Help, Abstract model of computation Discussions

Write discussion on Abstract model of computation
Your posts are moderated
Related Questions
Sketch an algorithm for the universal recognition problem for SL 2 . This takes an automaton and a string and returns TRUE if the string is accepted by the automaton, FALSE otherwi

Prove that Language is non regular TRailing count={aa ba aaaa abaa baaa bbaa aaaaaa aabaaa abaaaa..... 1) Pumping Lemma 2)Myhill nerode

i have some questions in automata, can you please help me in solving in these questions?

#can you solve a problem of palindrome using turing machine with explanation and diagrams?

What are the benefits of using work breakdown structure, Project Management

In general non-determinism, by introducing a degree of parallelism, may increase the accepting power of a model of computation. But if we subject NFAs to the same sort of analysis

Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff ≡L partitions Σ* into ?nitely many Nerode equivalence classes. Proof: For the "only if" direction (that every recogn