Ali Ebnenasir, associate professor in the Department of Computer Science, will present a Computer Science Colloquium on Friday, November 8, 2024, at 3 pm in Rekhi 214. The title of the talk is, “Making Headway on the Simplest Unsolved Math Problem Through the Specification and Generation of Convergence Stairs.”
Talk Abstract: The focus of this talk is on one of the simplest unsolved Math problems that has important applications in Computer Science (e.g., software watermarking) and Control Theory (e.g., stability of non-linear control systems). For the first time in decades, we present an algorithmic method that, given a positive integer j, generates the j-th convergence stair containing all natural numbers from where the Collatz conjecture holds by exactly j applications of the Collatz function. To this end, we devise a novel formulation of the Collatz conjecture as a program, and provide the general case specification of the j-th convergence stair for any j > 0. The proposed specifications provide a layered and linearized orientation of Collatz numbers organized in an infinite set of infinite binary trees. Such a general specification can have significant applications in analyzing and testing the stability of complex non-linear systems. We have implemented this method as a software tool that generates the Collatz numbers of individual stairs. We also show that starting from any value in any convergence stair the conjecture holds. However, to prove the conjecture, one has to show that every natural number will appear in some stair; i.e., the union of all stairs is equal to the set of natural numbers, which remains an open problem.