标题： 通过随机序列的有效名称的算术复杂度 显示英文标题

标题： Arithmetic complexity via effective names for random sequences

摘要： 我们研究允许递归、字典序递增近似或左-递归可枚举集合类的可枚举性性质。 除了明确左-递归可枚举的Martin-Löf、可计算、Schnorr和Kurtz随机集合，弱1-generic及其补集类的复杂性外，我们发现存在仅基于这些概念的算术层次第三和第四层的刻画。 更一般地，存在算术复杂性和左-递归可枚举集合类中具有移位持续元素的编号存在的等价关系。 虽然某些类（如Martin-Löf随机和Kurtz非随机）具有左-递归可枚举编号，但任何左-递归可枚举随机集合类都没有规范的或可接受的左-递归可枚举编号。 最后，我们注意到集合和实数的左-递归可枚举编号之间的一些基本差异。 显示英文摘要

摘要： We investigate enumerability properties for classes of sets which permit recursive, lexicographically increasing approximations, or left-r.e. sets. In addition to pinpointing the complexity of left-r.e. Martin-L\"{o}f, computably, Schnorr, and Kurtz random sets, weakly 1-generics and their complementary classes, we find that there exist characterizations of the third and fourth levels of the arithmetic hierarchy purely in terms of these notions. More generally, there exists an equivalence between arithmetic complexity and existence of numberings for classes of left-r.e. sets with shift-persistent elements. While some classes (such as Martin-L\"{o}f randoms and Kurtz non-randoms) have left-r.e. numberings, there is no canonical, or acceptable, left-r.e. numbering for any class of left-r.e. randoms. Finally, we note some fundamental differences between left-r.e. numberings for sets and reals.