Computable Structure Theory

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

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