Loading...
Please wait, while we are loading the content...
Similar Documents
What is an algorithm? (2000).
| Content Provider | CiteSeerX |
|---|---|
| Researcher | Moschovakis, Yiannis N. |
| Abstract | Machines and Recursive Definitions 2.1 Abstract Machines The best-known model of mechanical computation is (still) the first, introduced by Turing [18], and after half a century of study, few doubt the truth of the fundamental Church-Turing Thesis : A function f : N # N on the natural numbers (or, more generally, on strings from a finite alphabet) is computable in principle exactly when it can be computed by a Turing Machine. The Church-Turing Thesis grounds proofs of undecidability and it is essential for the most important applications of logic. On the other hand, it cannot be argued seriously that Turing machines model faithfully all algorithms on the natural numbers. If, for example, we code the input n in binary (rather than unary) notation, then the time needed for the computation of f(n) can sometimes be considerably shortened; and if we let the machine use two tapes rather than one, then (in some cases) we may gain a quadratic speedup of the computation, see [8]. This mea... |
| File Format | |
| Publisher Date | 2000-01-01 |
| Access Restriction | Open |
| Subject Keyword | Natural Number Best-known Model Machine Use Abstract Machine Important Application Fundamental Church-turing Thesis Mechanical Computation Quadratic Speedup Church-turing Thesis Finite Alphabet Turing Machine Recursive Definition |
| Content Type | Text |
| Resource Type | Thesis |
