This book develops a formal theory of computation which integrates major themes of the classical theory and which applies directly to problems in mathematics, numerical analysis, and scientific computing. Following an extensive introduction are proofs and extensions of relevant theorems. Along the way, the authors consider such fundamental questions as: Is the Mandelbrot set decidable? Is the Hilbert Nullstellensatz intractable? And, What is the real complexity of Newton's method?
This book develops a formal theory of computation which integrates major themes of the classical theory and which applies directly to problems in mathematics, numerical analysis, and scientific computing. Following an extensive introduction are proofs and extensions of relevant theorems. Along the way, the authors consider such fundamental questions as: Is the Mandelbrot set decidable? Is the Hilbert Nullstellensatz intractable? And, What is the real complexity of Newton's method?