A real number is called left-computable if there exists a computable increasing sequence of rational numbers converging to it. In this article, we investigate the binary expansions of two kinds of left-computable numbers. A real number is called strongly left-computable if its binary expansion is a computably enumerable set. A real number is called regular if it can be written as the sum of finitely many strongly left-computable numbers. Finally, a real number x is called reordered computable if there exist a computable function \(f :\mathbb {N} \rightarrow \mathbb {N}\) with \(\sum _{k=0}^{\infty } 2^{-f(k)} = x\) and a bijective function \(\sigma :\mathbb {N} \rightarrow \mathbb {N}\) such that the rearranged series \(\sum _{k=0}^{\infty } 2^{-f(\sigma (k))}\) converges computably. Every strongly left-computable number is regular and every regular number is reordered computable, but none of these implications can be reverted. We clarify the relation between regular numbers, reordered computable numbers, and left-computable numbers that are immune or hyperimmune. In particular, we show that there exists a regular number which is immune and that every left-computable number which is not immune is reordered computable. On the other hand, we show that a regular number cannot be hyperimmune, but that there exists a reordered computable number which is hyperimmune. Finally, we show that there is a reordered computable and immune number that is neither regular nor hyperimmune.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Binary Expansions of Regular Reals and Reordered Computable Numbers

  • Peter Hertling,
  • Philip Janicki

摘要

A real number is called left-computable if there exists a computable increasing sequence of rational numbers converging to it. In this article, we investigate the binary expansions of two kinds of left-computable numbers. A real number is called strongly left-computable if its binary expansion is a computably enumerable set. A real number is called regular if it can be written as the sum of finitely many strongly left-computable numbers. Finally, a real number x is called reordered computable if there exist a computable function \(f :\mathbb {N} \rightarrow \mathbb {N}\) with \(\sum _{k=0}^{\infty } 2^{-f(k)} = x\) and a bijective function \(\sigma :\mathbb {N} \rightarrow \mathbb {N}\) such that the rearranged series \(\sum _{k=0}^{\infty } 2^{-f(\sigma (k))}\) converges computably. Every strongly left-computable number is regular and every regular number is reordered computable, but none of these implications can be reverted. We clarify the relation between regular numbers, reordered computable numbers, and left-computable numbers that are immune or hyperimmune. In particular, we show that there exists a regular number which is immune and that every left-computable number which is not immune is reordered computable. On the other hand, we show that a regular number cannot be hyperimmune, but that there exists a reordered computable number which is hyperimmune. Finally, we show that there is a reordered computable and immune number that is neither regular nor hyperimmune.