本文共 4823 字,大约阅读时间需要 16 分钟。
Several different computational models were devised by these early researchers. One model, the , stores characters on an infinitely long tape, with one square at any given time being scanned by a read/write head. Another model, , uses functions and function composition to operate on numbers. The uses a similar approach. Still others, including [] and [], use grammar-like rules to operate on strings. All of these formalisms were shown to be equivalent in computational power -- that is, any computation that can be performed with one can be performed with any of the others. They are also equivalent in power to the familiar electronic computer, if one pretends that electronic computers have infinite memory. Indeed, it is wly believed that all "proper" formalizations of the concept of algorithm will be equivalent in power to Turing machines; this is known as the . In general, questions of what can be computed by various machines are investigated in .
The theory of computation studies these models of general computation, along with the limits of computing: Which problems are (provably) unsolvable by a computer? (See the .) Which problems are solvable by a computer, but require such an enormously long time to compute that the solution is impractical? (See .) Can it be harder to solve a problem than to check a given solution? (See ). In general, questions concerning the time or space requirements of given problems are investigated in .
In addition to the general computational models, some simpler computational models are useful for special, restricted applications. , for example, are used to specify string patterns in style="TEXT-DECORATION: underline" href="http://www.wikipedia.com/wiki/UNIX">UNIX and in some programming languages such as style="TEXT-DECORATION: underline" href="http://www.wikipedia.com/wiki/Perl">Perl. Another formalism mathematically equivalent to regular expressions, are used in circuit design and in some kinds of problem-solving. are used to specify programming language syntax. Nondetenistic are another formalism equivalent to context-free grammars. are a naturally defined subclass of the recursive functions.
Different models of computation have the ability to do different tasks. One way to measure the power of a computational model is to study the class of that the model can generate; this leads to the of languages.
The following table shows some of the classes of problems (or languages, or grammars) that are considered in computability theory (blue) and complexity theory (green). If class X is a strict subset of Y, then X is shown below Y, with a dark line connecting them. If X is a subset, but it is unknown whether they are equal sets, then the line is lighter and is dotted.
This article contains some content from an , originally posted on . This article is .
" rel="nofollow">Upload files
This page has been accessed 1837 times. Other namespaces :
Last edited: Sunday, June 2, 2002, 15:01
来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10748419/viewspace-959371/,如需转载,请注明出处,否则将追究法律责任。
转载于:http://blog.itpub.net/10748419/viewspace-959371/