A continuous model of computation

 

 

I. First Reading of paragraphsphs 1-3

1. Read the text quickly and try to understand what it is about and what information is     already known to you.

2. Write down the physical terms, known to you, in Russian.

3. Find in the text the sentence about “real worlds”.

 

II. Scanning Reading

1. Read the texts “Two Models of Computation”, "Turing-machine model –pros and cons”, “Real-number model – pros and cons” and other texts that are the parts of the text “A Continuous Model of Computation”.

2. Pick out an idea or a phrase, which you think is most informative or most interesting from each part of the text.

3. Pick out the physical terms, which you don’t know. Refer to a dictionary, if necessary.

 

A CONTINUOUS MODEL OF COMPUTATION

Abridged

 

Physicist should consider an alternative to the Turning-machine model of computation

                                                                                              Joseph F. Traub

 

1 А central dogma of com­puter science is that the Turing-machine model is the appropriate abstraction of a digital computer. Physicists who've thought about the matter also seem to favor the Turing-machine model. For example, Roger Penrose de­voted some 60 pages of a book to a description of this abstract model of computation and its implications. I argue here that physicists should consider the real-number model of computation as more appropriate and useful for scientific computation.

First, I introduce the four "worlds" that play a role here. Above the horizontal line in the diagram on this page are two real worlds: the world of physical phenomena and the computer world in which simulations are performed. Below them are represented two formal worlds: a mathe­matical model of some physical phenomenon and a model of computation that is an abstraction of a physical computer. We get to choose both the mathematical model and the model of computation. What type of models should we choose?

2 The physicist often chooses a continuous mathemati­cal model for the phenomenon un­der consideration. Continuous mod­els range from the dynamical sys­tems of classical physics to the op­erator equations and path inte­grals of quantum mechanics. These models are based on the real numbers (as distinguished from the subset of rational numbers). The real numbers are, of course, an abstraction.It takes an infinite number of bits to represent a single real number. (A rational number, by contrast, requires only a finite number of bits.) But infinitely many bits are not available in the universe. One uses the continuous domain of the real numbers because it is a powerful and useful construct. Let us accept that continuous models are widely used in mathematical physics, and that they will continue to occupy that role for the foreseeable future. But the computer is a finite-state machine. What should we do when the continuous mathematical model meets the finite-state machine?

3 In the next section I compare and contrast two models of computation: the Turing-machine and real-number models. In the interest of full disclosure, I must tell you that I've always used the real-number model in my work as a computer scientist. But I do my best here to present balanced arguments. Then I show how the real-number model is used in the study of the computational complexity of continuous mathematical models. (Computational complexity is a measure of the minimal computational resources required to solve a mathematically posed problem.) This is the province of a branch of complexity theory called informa­tion-based complexity, and what follows is intended to demonstrate the power of this theory.

 

Two models of computation

4 Although many readers are familiar with the Turing-ma­chine model I start by describing it briefly. Then, after describing the real-number model, I will discuss the pros and cons of these two models.

Alan Turing, one of the intellectual giants of the twentieth century, defined his ma­chine model to es­tablish the unsolvability of David Hilbert's Entscheid-ungsproblem, the problem of finding an algorithm for deciding (entscheiden, in Ger­man) whether any given mathematical proposition is true or false. The Turing machine is a gedankengadget employing a tape of un­bounded length, divided into sequential squares, each of which is either blank or contains a single mark. For any particular input, the resulting calculation and output are finite; that is to say, the tape is blank beyond a certain point. The machine's reading head reads one square at a time and, after making or erasing a mark, moves one square to the left or right. The machine has a finite number of internal states. Given its initial state and the input sequence on the tape, the machine changes its state and the head prints a symbol and moves one square. Finally, the machine decides when to halt.

 

5 The real-number model has a long history. Alexander Ostrowski used it in his work on the computational com­plexity of polynomial evaluation in 1954. In the 1960s, I used the real-number model for research on optimal it­eration theory and Shmuel Winograd and Volker Strassen employed it in their work on algebraic complexity. Henryk Wozniakowski and I used the real-number model in a 1980 -monograph on information-based complexity. The 1989 formalization of the real-number model for continuous combinatorial complexity by Lenore Blum, Michael Shub, and Steven Smale initiated a surge of research on com­putation over the real numbers.

6 Both models are abstractions of real digital comput­ers. Of the Turing-machine model, Penrose wrote, "It is the unlimited nature of the input, calculation space, and output which tells us that we are considering only a mathematical idealization." Which abstraction to use de­pends on how useful that abstraction is for a given pur­pose. What are the pros and cons of these two models of computation?