Diagonally non-recursive functions and effective Hausdorff dimension

作者：Greenberg Noam^*; Miller Joseph S

来源：Bulletin of the London Mathematical Society, 2011, 43(4): 636-654.

DOI：10.1112/blms/bdr003

We prove that every sufficiently slow-growing diagonally non-recursive (DNR) function computes a real with effective Hausdorff dimension 1. We then show that, for any recursive unbounded and non-decreasing function j, there is a DNR function bounded by j that does not compute a Martin-Lof random real. Hence, there is a real of effective Hausdorff dimension 1 that does not compute a Martin- Lof random real. This answers a question of Reimann and Terwijn.

• 出版日期2011-8