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
First model: Computer has a ?xed number of bits of storage. You will model this by limiting your program to a single ?xed-precision unsigned integer variable, e.g., a single one-by

conversion from nfa to dfa 0 | 1 ___________________ p |{q,s}|{q} *q|{r} |{q,r} r |(s) |{p} *s|null |{p}

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

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

s-> AACD A-> aAb/e C->aC/a D-> aDa/bDb/e

A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi

When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is

i want to do projects for theory of computation subject what topics should be best.

Rubber shortnote

If the first three words are the boys down,what are the last three words??