Computability Theory, Reverse Mathematics and Countable Algebraic Structures

University Of Connecticut, Storrs CT

Investigators

Abstract

In computable algebra, one applies the methods of classical computability theory to study computational properties of algebraic structures. Solomon proposes to study several questions concerning the members of these and other classes of algebraic structures. Do the members of a given class display the most general forms of ineffectiveness found in computable algebra? Are instances of ineffectiveness caused by the coding methods (and hence can be removed by a reasonable coding) or by some inherent property of the underlying algebra (and are therefore unavoidable)? How does adding structure (such as an ordering) to the members of a class effect the computational properties? These questions aim toward a deeper understanding of the connection between computation and algebraic behavior in mathematics. Many theorems in mathematics state that given certain conditions, a particular mathematical object must exist. There are numerous ways to study the effectiveness of such a theorem. One method, called computable or recursive mathematics, uses an idealized model of a computer in which computations are allowed to run for arbitrarily long (but finite) amounts of time and to use arbitrarily large (but finite) amounts of memory. The fundamental question is whether such an idealized computer can construct the desired mathematical object from the theorem. If the answer to this question is no, then the theorem uses a method of construction that cannot be performed on an actual computer no matter how much technology increases computer speed and memory size. Because this question requires that mathematical objects be coded into the binary language of computers, the answer sometimes depends on the type of coding used. Solomon proposes to study a number of algebraic constructions from this point of view and in particular to study when ineffectiveness is caused by a poor choice of coding (and hence can be fixed by a better choice of coding) and when it is caused by inherent conflicts between mathematical structure and computation (and hence cannot be removed by clever coding). Solomon also proposes to use a second method, called reverse mathematics, to study the effectiveness of numerous mathematical theorems. In this approach, one isolates the mathematical axioms required to prove the theorem. Reverse mathematics and computable mathematics are closely related. If only simple axioms are required to prove a theorem, then it is likely that a computer can carry out the construction, while if complicated axioms are required, then a computer probably cannot perform the construction.