Computable Structure Theory

点击翻译按钮获取中文摘要

9970452Knight This award will support mainly the travel of graduate students inmathematical logic to professional meetings and to a lesser extent willsupport travel of some outside speakers to the Notre Dame Logic Seminar,which is also important for providing the broadest background in logicfor the students. Finally, a small portion of the funds (about 10%)will enable the students to have permanent access to certain importantreference books. Knight and her students are working on various aspects ofcomputable structure theory. One student, Charles McCoy, has several resultsconnecting definability with complexity. He is now trying to characterizein a mathematical way the linear orderings and Boolean algebras with thefeature that between computable copies, there is always some isomorphismat level two in the arithmetic hierarchy. Another student, Andrew Arana,is beginning work on models of arithmetic and enumerations. Knight herselfwill concentrate on problems involving existence of computable copies ofstructures. In particular, she hopes to extend the partial results ofKhisamiev on reduced Abelian p-groups with computable copies. She isinterested in a question of Shore, on what statement could serve as acomputable non-structure theorem. Knight has a side interest in systemstheory. The area of computable structure, a new and arguably more suggestiveterm for what has long been known as recursion theory, has its roots in thediscovery more than half a century ago of sets of integers for which noalgorithm exists to decide if a particular integer is a member. Moreover,another old result (from the 1950's) established that there are incomparablesets of this type, i.e., two sets such that neither permits one to constructthe other from it in a mechanical way. As a practical matter, one caresabout the speed and efficiency of algorithms and not their mere existence.Nevertheless, understanding the inherent limits of algorithmic possibilityis an important philosophical accomplishment and triumph of the humanintellect, in a way the ultimate in self-knowledge.***