Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Algorithms for constructing computably enumerable sets
Supowit K., Springer International Publishing, Cham, Switzerland, 2023. 183 pp. Type: Book (9783031269035)
Date Reviewed: Nov 15 2023

Computational complexity (historically called recursive functions in logic) is a very specific area of computational theory, and even within this domain the book discusses a very specific subfield: the theoretical construction of enumerable sets.

The book is organized as a mathematics or theoretical computer science (CS) textbook. Theorems and lemmas, as well as pseudocode, demonstrate the solutions, and each chapter concludes with exercises. A very useful chapter summary describes the results presented in the chapter through a semiformal explanation. A precise description of the content of the chapters requires accurate mathematical formulations. This specific branch of computational complexity theory deals with sets that can be listed and ordered in infinite series (that is, the elements of the sets can be indexed by natural numbers, one by one).

Naturally we may come across the P versus NP problem; even if the SAT solver can manage the raised problem that is coded in conjunctive normal form, we may face the practical issue of available computing power. Anyway, the theory presented in the book highlights that there is no theoretical barrier to satisfying ordered lists of requirements. Nevertheless, the algorithms in the book do not care about time or other constraints that would be important in an application case.

Although the book succinctly introduces the basics of computability theory, it should only be used after an introductory course in the field. The book may work for graduate-level specializations in the theory of computation due to its focus on a narrow, specific research area.

The first three chapters can be considered a recap of the basics of computational complexity theory, including Turing machines, the halting problem, and the important fact that enumerable sets exist.

After this important grounding in the relevant mathematical theory, the book goes into the specific branch of complexity theory that it deals with. The problem is that there is an infinite series or list of requirements that should be satisfied by computable enumerable sets. Even infinite injuries--not satisfying the requirements--can be handled in some way. The steps and inferences can be represented in an infinite tree.

How does this abstract computability theory benefit current CS and information technology? The infinite series of facts and requirements that are represented by natural numbers can be considered as a raw mapping of requirements from any computational environment. The infinite ordered list of numbers is a mathematical tool to capture the essence of the investigated phenomena, similar to the limits of real numbers in mathematical analysis. We encounter in the most recent applications of CS that a list of requirements should be satisfied; even the list can be dynamically extended.

The theory demonstrates that a true path representing decisions based on witnesses (oracles) in an infinite tree can be found. The issue remains whether the method can be used to categorize the complexity of the various tree algorithms, where the tree represents a problem in some applications. However, the general results presented in this book can be interpreted as a computable and tractable solution that may exist.

Reviewer:  Bálint Molnár Review #: CR147666
Bookmark and Share
  Featured Reviewer  
Algorithms (B.2.4 ... )
Algorithms (I.5.3 ... )
Set Theory (F.4.1 ... )
Algorithms (I.1.2 )
Would you recommend this review?
Other reviews under "Algorithms": Date
Integer summing algorithms on reconfigurable meshes
Nakano K., Wada R. Theoretical Computer Science 197(1-2): 57-77, 1998. Type: Article
Dec 1 1998
Bit-level two’s complement matrix multiplication
Grover R., Shang W., Li Q. Integration, the VLSI Journal 33(1): 3-21, 2002. Type: Article
Oct 2 2003
 New approach to design for reusability of arithmetic cores in systems-on-chip
Margala M., Wang H. Integration, the VLSI Journal 38(2): 185-203, 2004. Type: Article
Aug 17 2005

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