Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Best of 2016 Recommended by Editor Recommended by Reviewer Recommended by Reader
Search
The incomputable : journeys beyond the Turing barrier
Cooper S., Soskova M., Springer International Publishing, New York, NY, 2017. 292 pp. Type: Book (978-3-319436-67-8)
Date Reviewed: Mar 7 2018

Computer science is composed of two major areas. One is strongly related to engineering: the architecture and design of computing systems and the development of tools to employ such systems. The other is more related to scientific inquiry, although to those outside the field it may appear to be theoretical mathematics. This area, of course, is the theory of computation. It investigates what is computable, along with developing ways to express and analyze the performance of algorithms, and classifying the degrees of difficulty, that is, the inherent complexity, for performing different types of computations. The complexity issue becomes important when the input to a calculation grows in size. A classic example of this type of performance analysis is the traveling salesman problem, which seeks to find the shortest distance the salesman can take to visit a number of cities. The computational effort needed to find the optimal route grows exponentially as each city added multiplies the number of routes that must be tested.

One of the founders of this area is Alan Turing, who developed the concept of a simple but universal computing device today called the Turing machine (TM). Turing demonstrated that a TM is conceptually equivalent to any modern digital computer. He further investigated the limits of what a TM, or any comparable device, could compute. A key finding is known as the halting problem. Turing proved that no general algorithm can exist that can analyze any program with an input and decide if the program will halt after processing the input. The halting problem demonstrates a fundamental limit on what can be computed.

Research since Turing’s work has created what is called the complexity zoo, which describes and classifies algorithms into groups based on the degree of hardness, that is, how quickly computational effort rises with the increasing size of the input. More recently, we have the introduction of quantum computing that uses the properties of quantum-level units, called qubits, to perform calculations. Research in this area suggests that a quantum computer could reduce the hardness level of some problems, such as factoring large integers. This, for example, could impact current cryptography by making obsolete current security algorithms that depend on the ease of multiplying large integers and the difficulty in factoring them.

The incomputable explores selected recent research into various aspects of computability. This includes abstract models of computation, how quantum algorithms could in some sense redefine aspects of computability, and how the notion of computability relates to the physical world and physical processes. The book leads with a tribute to the late Ivan Soskov, a Bulgarian computer scientist who dedicated his professional career to studying computability theories, particularly computability over abstract structures.

Other papers extend computability arguments to areas such as “undecidable, uncomputable, and unsolvable problems in economics,” an exploration of classes of cost functions that are “close to computable,” and whether quantum randomness is better in some sense than classical pseudo-randomness. One paper relates the halting problem to the computation of the energy spectrum of a physical system. Two papers are based on Turing’s theory of morphogenesis, which models how cells can differentiate through chemical processes of reaction and diffusion.

Many of the papers contain deep mathematical treatments of computability topics, using highly specialized terminology and notation. These papers assume familiarity with the topics discussed and offer no or at best minimal introductory material. They most likely will be of interest only to other researchers in the particular field, a rather narrow audience. Those dealing with quantum mechanics and physical theory are more approachable, but again will appeal mainly to those working in areas such as quantum physics, quantum computing, or cryptography. Of the papers on morphogenesis, the first is about Turing’s starting point, the chemistry of cellular processes, and the research his one paper on the topic generated. The second paper is about meta-morphogenesis, a broadening of Turing’s original concept into the notion of construction kits, which allow grouping drivers of the evolutionary process into subcategories, some of which build upon others, for further study. Both papers are quite readable, as is Turing’s paper [1] that began this area of inquiry.

Reviewer:  G. R. Mayforth Review #: CR145901 (1806-0277)
1) Turing, A. M. The chemical basis of morphogenesis. Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences 237, 641(1952), 37–72.http://www.jstor.org/stable/92463?seq=1#page_scan_tab_contents.
Bookmark and Share
  Reviewer Selected
Editor Recommended
 
 
Computability Theory (F.1.1 ... )
 
 
Biology And Genetics (J.3 ... )
 
 
Recursive Function Theory (F.4.1 ... )
 
 
Complexity Measures And Classes (F.1.3 )
 
 
Modes Of Computation (F.1.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Computability Theory": Date
Decidability of the purely existential fragment of the theory of term algebras
Venkataraman K. Journal of the ACM 34(2): 492-510, 1987. Type: Article
Jul 1 1988
Computability
Weihrauch K. (ed), Springer-Verlag New York, Inc., New York, NY, 1987. Type: Book (9789780387137216)
Nov 1 1988
Computability and logic: 3rd ed.
Boolos G., Jeffrey R., Cambridge University Press, New York, NY, 1989. Type: Book (9789780521380263)
Jul 1 1990
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy