论文标题
复杂性和回避
Complexity and Avoidance
论文作者
论文摘要
在本文中，我们研究了几个层次结构之间的关系，包括复杂性，$ \ mathrm {lua} $（线性通用避免）和移动复杂性层次结构，并着眼于量化其中的增长率。我们表明，对于合适的$ f $和$ p $，有$ q $和$ g $，以便$ \ mathrm {lua}（q）（q）\ leq_ \ mathrm {s} \ mathrm {complect}（f）（f）$ and $ \ mathrm {complect}（g）量化$ Q $和$ g $的增长率。在相反的方向上，我们表明，对于某些子标准的$ f $满足$ \ lim_ {n \ to \ infty} {f（n）/n} = 1 $，有一个$ q $，以至于$ \ m mathrm {complect}（complect}（f） $ g $使得$ \ mathrm {lua}（p）\ leq_ \ mathrm {s} \ mathrm {complect}（g）$，并量化$ q $和$ g $的增长率。 关于偏移的复杂性，对$ \ rm {lua}（q）$的任何成员的增长$ q $的速度必须为$Δ$Δ$ shift复杂序列，给出了明确的界限。在复杂性层次结构的激励下，我们概括了移动复杂性的概念，以考虑$ x $满足$ \ operatatorName {kp}（τ）（τ）\ geq f（|τ|） - o（1）$ for $ x $ f $均为$ x $的所有subStrings $ x $均为$ x $。我们表明，对于足够缓慢增长的$ f $，$ f $ shift复杂序列可以由$ g $ - complex序列统一计算，其中$ g $的增长速度略高于$ f $。 $ \ mathrm {lua} $层次结构的结构是使用灌木树强迫检查的，主要结果是，对于任何订单函数$ p $，都有一个缓慢增长的订单函数$ q $，因此$ \ mathrm {lua}（lua}（p）$ and $ \ \ \ m nathrm {lua}（q）（q）（q）（q）$ ne ne ne ne ne ne ne ne ne ne ne ne ne ne ne ne ne ne ne ne nise nise nise Incom。使用此情况，我们证明了有关深度非空的$π^0_1 $类的弱度的过滤器以及移位复杂度与$ \ Mathrm {lua} $层次结构之间的连接。
In this dissertation we examine the relationships between the several hierarchies, including the complexity, $\mathrm{LUA}$ (Linearly Universal Avoidance), and shift complexity hierarchies, with an eye towards quantitative bounds on growth rates therein. We show that for suitable $f$ and $p$, there are $q$ and $g$ such that $\mathrm{LUA}(q) \leq_\mathrm{s} \mathrm{COMPLEX}(f)$ and $\mathrm{COMPLEX}(g) \leq_\mathrm{s} \mathrm{LUA}(p)$, as well as quantify the growth rates of $q$ and $g$. In the opposite direction, we show that for certain sub-identical $f$ satisfying $\lim_{n \to \infty}{f(n)/n}=1$ there is a $q$ such that $\mathrm{COMPLEX}(f) \leq_\mathrm{w} \mathrm{LUA}(q)$, and for certain fast-growing $p$ there is a $g$ such that $\mathrm{LUA}(p) \leq_\mathrm{s} \mathrm{COMPLEX}(g)$, as well as quantify the growth rates of $q$ and $g$. Concerning shift complexity, explicit bounds are given on how slow-growing $q$ must be for any member of $\rm{LUA}(q)$ to compute $δ$-shift complex sequences. Motivated by the complexity hierarchy, we generalize the notion of shift complexity to consider sequences $X$ satisfying $\operatorname{KP}(τ) \geq f(|τ|) - O(1)$ for all substrings $τ$ of $X$ where $f$ is any order function. We show that for sufficiently slow-growing $f$, $f$-shift complex sequences can be uniformly computed by $g$-complex sequences, where $g$ grows slightly faster than $f$. The structure of the $\mathrm{LUA}$ hierarchy is examined using bushy tree forcing, with the main result being that for any order function $p$, there is a slow-growing order function $q$ such that $\mathrm{LUA}(p)$ and $\mathrm{LUA}(q)$ are weakly incomparable. Using this, we prove new results about the filter of the weak degrees of deep nonempty $Π^0_1$ classes and the connection between the shift complexity and $\mathrm{LUA}$ hierarchies.
