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:

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

Ask an Expert

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

Write your message here..

Related Questions

Alphabets - strings and representation, A finite, nonempty ordered set will... A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

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

Instantaneous description of an fsa, De?nition Instantaneous Description of... De?nition Instantaneous Description of an FSA: An instantaneous description (ID) of a FSA A = (Q,Σ, T, q 0 , F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the p

Finite-state automaton, Paths leading to regions B, C and E are paths which... Paths leading to regions B, C and E are paths which have not yet seen aa. Those leading to region B and E end in a, with those leading to E having seen ba and those leading to B no

Decision problems of regular languages, We'll close our consideration of re... We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

Rubber, Rubber shortnote Rubber shortnote

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

Equivalence problem, The Equivalence Problem is the question of whether two... The Equivalence Problem is the question of whether two languages are equal (in the sense of being the same set of strings). An instance is a pair of ?nite speci?cations of regular

Transition graphs, We represented SLk automata as Myhill graphs, directed g... We represented SLk automata as Myhill graphs, directed graphs in which the nodes were labeled with (k-1)-factors of alphabet symbols (along with a node labeled ‘?' and one labeled

Strictly local languages, While the SL 2 languages include some surprising... While the SL 2 languages include some surprisingly complex languages, the strictly 2-local automata are, nevertheless, quite limited. In a strong sense, they are almost memoryless