### Schnorr triviality is equivalent to being a basis for tt-Schnorr randomness

Miyabe, K *(Kyoto University)*

Monday 02 July 2012, 15:00-15:30

Seminar Room 1, Newton Institute

#### Abstract

We present some new characterizations of Schnorr triviality. Schnorr
triviality is defined using complexity via a computable measure machine,
with which Schnorr randomness has a characterization. Since we have a
characterization of Schnorr randomness via decidable prefix-free machine,
we also have a characterization of Schnorr triviality using complexity
via a decidable prefix-free machine. It should be noted that numerous
characterizations of Schnorr triviality have the following form: for any
computable object, there exists another computable object such that the
real is in some object. By defining a basis for Schnorr randomness in a
similar manner, we can show the equivalence to Schnorr triviality while
Franklin and Stephan (2010) showed that there exists a Schnorr trivial
set that is not truth-table reducible to any Schnorr random set.

#### Presentation

#### Video

**The video for this talk should appear here if JavaScript is enabled.**

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.

## Comments

Start the discussion!