Some Recursion Theoretic Problems

一些递归理论问题

• 批准号: 9971137
• 负责人: Leo Harrington
• 金额: $ 21.44万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-08-01 至 2003-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9971137&HistoricalAwards=false
• 关键词: Some; Recursion; Theoretic; Problems

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

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