Pricing
Quantum Computation and Quantum Information: Introduction to computer science
This chapter outlines the modern theory of algorithms developed by computer science, and focuses on the fundamental model for algorithms, the Turing machine, which is an idealized computer, rather like a modern personal computer, but with a simpler set of basic instructions, and an idealization unbounded memory.
Abstract
In natural science, Nature has given us a world and we're just to discover its laws. In computers, we can stuff laws into it and create a world. – Alan Kay Our field is still in its embryonic stage. It's great that we haven't been around for 2000 years. We are still at a stage where very, very important results occur in front of our eyes. – Michael Rabin, on computer science Algorithms are the key concept of computer science. An algorithm is a precise recipe for performing some task, such as the elementary algorithm for adding two numbers which we all learn as children. This chapter outlines the modern theory of algorithms developed by computer science. Our fundamental model for algorithms will be the Turing machine . This is an idealized computer, rather like a modern personal computer, but with a simpler set of basic instructions, and an idealized unbounded memory. The apparent simplicity of Turing machines is misleading; they are very powerful devices. We will see that they can be used to execute any algorithm whatsoever, even one running on an apparently much more powerful computer. The fundamental question we are trying to address in the study of algorithms is: what resources are required to perform a given computational task? This question splits up naturally into two parts. First, we'd like to understand what computational tasks are possible, preferably by giving explicit algorithms for solving specific problems.