Computable Structure Theory

9970452骑士该奖项将主要资助数理逻辑专业研究生参加专业会议的旅费，并在较小程度上支持一些外部演讲者参加巴黎圣母院逻辑研讨会的旅费，这也是为学生提供最广泛的逻辑背景的重要因素。最后，一小部分资金(约10%)将使学生能够永久访问某些重要的参考书籍。奈特和她的学生正在研究可计算结构理论的各个方面。一位名叫查尔斯·麦考伊的学生得出了几个将可定义性与复杂性联系起来的结果。他现在正试图用数学方法刻画线性序和布尔代数的特征，即在可计算的副本之间，算术层次中总有一些二级同构。另一名学生安德鲁·阿拉纳开始研究算术和枚举模型。骑士本人将专注于涉及结构的可计算副本的存在的问题。特别是，她希望用可计算的副本推广Khisamiev关于约化Abel p-群的部分结果。她对Shore的一个问题感兴趣，关于什么陈述可以作为一个可计算的非结构化定理。奈特对系统论也有兴趣。可计算结构领域是一个新的、可以说是更有说服力的术语，指的是长期以来被称为递归理论的东西，其根源在于半个多世纪前发现的整数集，对于这些整数集，没有算法来确定某个特定的整数是否为成员。此外，另一个旧的结果(来自1950年的S)确立了存在这种类型的不可比较的集合，即，两个集合都不允许一个以机械的方式构造另一个。作为一个实际问题，人们关心的是算法的速度和效率，而不仅仅是它们的存在。然而，理解算法可能性的内在极限是人类智力的一项重要哲学成就和胜利，在某种程度上，这是自我认识的终极。

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.***