News
29 July 2015, the slide file was uploaded
Title
Welcome to mathematical paradoxes
Type
Summer Seminar of Meiji University for high school students
Download
summer-seminar
宮部賢志(ミヤベケンシ)
News
29 July 2015, the slide file was uploaded
Title
Welcome to mathematical paradoxes
Type
Summer Seminar of Meiji University for high school students
Download
summer-seminar
News
19 Jan 2014, submitted
24 Mar 2015, published
Title
Unified Characterizations of Lowness Properties via Kolmogorov Complexity
(with T. Kihara)
Type
Full paper
Journal
Archive for Mathematical Logic: Volume 54, Issue 3 (2015), Page 329-358
DOI: 10.1007/s00153-014-0413-8
Abstract
Consider a randomness notion $\mathcal C$.
A uniform test in the sense of $\mathcal C$ is a total computable procedure that each oracle $X$ produces a test relative to $X$ in the sense of $\mathcal C$.
We say that a binary sequence $Y$ is $\mathcal C$-random uniformly relative to $X$ if $Y$ passes all uniform $\mathcal C$ tests relative to $X$.
Suppose now we have a pair of randomness notions $\mathcal C$ and $\mathcal D$ where $\mathcal{C}\subseteq \mathcal{D}$, for instance Martin-L\”of randomness and Schnorr randomness. Several authors have characterized classes of the form Low($\mathcal C, \mathcal D$) which consist of the oracles $X$ that are so feeble that $\mathcal C \subseteq \mathcal D^X$. Our goal is to do the same when the randomness notion $\mathcal D$ is relativized uniformly: denote by Low$^\star$($\mathcal C, \mathcal D$) the class of oracles $X$ such that every $\mathcal C$-random is uniformly $\mathcal D$-random relative to $X$.
(1) We show that $X\in{\rm Low}^\star({\rm MLR},{\rm SR})$ if and only if $X$ is c.e.~tt-traceable if and only if $X$ is anticomplex if and only if $X$ is Martin-L\”of packing measure zero with respect to all computable dimension functions.
(2) We also show that $X\in{\rm Low}^\star({\rm SR},{\rm WR})$ if and only if $X$ is computably i.o.~tt-traceable if and only if $X$ is not totally complex if and only if $X$ is Schnorr Hausdorff measure zero with respect to all computable dimension functions.
Download
preprint
News
23 Feb 2015, the slide file was uploaded
Title
The randomness hierarchy and reducibilities as its refinements
Type
Joint seminar at TMU (in Japanese)
Download
TMU-slide in Japanese
News
4 Jan 2015, the slide file was uploaded
Title
Total-machine reducibility and randomness notions
Type
Asian Logic Conference 2015
Download
slide