Abstract model of computation, Theory of Computation

Assignment Help:

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.


Related Discussions:- Abstract model of computation

Non - sl languages, The key thing about the Suffx Substitution Closure prop...

The key thing about the Suffx Substitution Closure property is that it does not make any explicit reference to the automaton that recognizes the language. While the argument tha

Non - sl languages, Application of the general suffix substitution closure ...

Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had

Kleenes theorem, All that distinguishes the de?nition of the class of Regul...

All that distinguishes the de?nition of the class of Regular languages from that of the class of Star-Free languages is that the former is closed under Kleene closure while the lat

Path function of a nfa, The path function δ : Q × Σ* → P(Q) is the extensio...

The path function δ : Q × Σ* → P(Q) is the extension of δ to strings: This just says that the path labeled ε from any given state q goes only to q itself (or rather never l

Finite automata, design an automata for strings having exactly four 1''s

design an automata for strings having exactly four 1''s

Myhill-nerode theorem, The Myhill-Nerode Theorem provided us with an algori...

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

Binary form and chomsky normal form, Normal forms are important because the...

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

Class of recognizable languages, Proof (sketch): Suppose L 1 and L 2 are ...

Proof (sketch): Suppose L 1 and L 2 are recognizable. Then there are DFAs A 1 = (Q,Σ, T 1 , q 0 , F 1 ) and A 2 = (P,Σ, T 2 , p 0 , F 2 ) such that L 1 = L(A 1 ) and L 2 = L(

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