Some Recursion Theoretic Problems

这个项目研究包含下递归可枚举集的结构，重点研究不变集和自同构，以及可定义集及其相应的有限来回对策。在某些类型的自同构的不存在性和某些类型的不变集的存在性之间存在着一种自然的相互作用。本项目将尝试解决一些固有的组合困难，将当前的自同构技术扩展到有限的来回论证。这可能有助于将不变/自同构技术转换为可定义/不可定义技术，从而产生可能有趣的可定义集。递归可枚举集合是这样一种集合，它的成员因为相应的计算停止而获得entry；因此，递归可枚举集合是一种随时间描述的现象的例子（在任何给定的时间，人们只知道计算已经停止的有限成员的集合），但其实际性质是永恒的（一个潜在的成员要么在里面，要么在外面——计算要么最终停止，要么永远停止）。所以递归可数集合为研究某事物的时间表象和同一事物的永恒本质之间的相互作用提供了一个舞台。这里使用的方法是假设，尽管表面上看，两个事物实际上是“相同的”，因为它们可以通过对称（自同构）来识别。要么事实证明是这样，要么试图产生理想对称性的失败可能（而且经常）导致一种永恒的可描述属性将两者分开，并解释为什么它们是真正不同的。本项目还计划将上述内容作为理解前苏格拉底哲学家的范例

9971137Harrington This project deals with the structure of recursively enumerablesets under inclusion, with emphasis on invariant sets andautomorphisms, and on definable sets with their corresponding finiteback-and-forth games. There is a natural interplay between thenon-existence of certain types of automorphisms and the existence ofcertain types of invariant sets. This project will attempt to addresssome of the combinatorial difficulties inherent in extending thecurrent techniques for automorphisms to finite back-and-fortharguments. This might help convert the invariant/automorphismtechnology into a definable/non-definable technology, thus producingpossibly interesting definable sets. A recursively enumerable set is a set whose members gain entrybecause a corresponding computation comes to a halt; thus therecursively enumerable sets are examples of a phenomenon describedover time (at any given time one knows only the finite set of memberswhose computation has already halted) but whose actual nature istimeless (a potential member is either in or out---the computationeither eventually halts or it never halts). So the recursivelyenumerable sets provide an arena for studying the interplay betweenthe appearances in time of some thing and the timeless nature of thatsame thing. The method used here is to presume, despite appearances,that two things are actually `the same' in the sense that they can beidentified via a symmetry (automorphism). This either turns out to bethe case, or the failure of the attempt to produce the desiredsymmetry may (and often does) result in a timeless describable propertyseparating the two things and explaining why they are truly different.This project also plans to use the above as an exemplar towardsunderstanding the pre-Socratic philosophers.***