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
You are required to design a system that controls the speed of a fan's rotation. The speed at which the fan rotates is determined by the ambient temperature, i.e. as the temperatur

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

The project 2 involves completing and modifying the C++ program that evaluates statements of an expression language contained in the Expression Interpreter that interprets fully pa

Suppose A = (Σ, T) is an SL 2 automaton. Sketch an algorithm for recognizing L(A) by, in essence, implementing the automaton. Your algorithm should work with the particular automa

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

The computation of an SL 2 automaton A = ( Σ, T) on a string w is the maximal sequence of IDs in which each sequential pair of IDs is related by |- A and which starts with the in

The class of Strictly Local Languages (in general) is closed under • intersection but is not closed under • union • complement • concatenation • Kleene- and positive

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

s->0A0|1B1|BB A->C B->S|A C->S|null find useless symbol?

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