**News**

4 Nov, 2019 The slide file was uploaded.

**Title**

Reverse randomness

**Type**

Colloquium talk at Kyoto University on 8 Nov, 2019.

**Download**

kyoto

Skip to content
# Kenshi Miyabe

## Posts

### Reverse randomness

### Computable prediction

### Uniform relativization

### Schnorr triviality via decidable machines

### Muchnik degrees and Medvedev degrees of the randomness notions

宮部賢志（ミヤベケンシ）

**News**

4 Nov, 2019 The slide file was uploaded.

**Title**

Reverse randomness

**Type**

Colloquium talk at Kyoto University on 8 Nov, 2019.

**Download**

kyoto

**News**

July 2019, Proof reading

**Title**

Computable prediction

**Type**

Conference paper

**Publication**

In Artificial General Intelligence. Volume 11654 of the Lecture Notes in Computer Science

**Abstract**

We try to predict the next bit from a given finite binary string

when the sequence is sampled from a computable probability measure on the Cantor space.

There exists the best betting strategy among a class of effective ones up to a multiplicative constant,

the induced prediction from which is called algorithmic probability or universal induction by Solomonoff.

The prediction converges to the true induced measure for sufficiently random sequences.

However, the prediction is not computable.

We propose a framework to study the properties of computable predictions.

We prove that all sufficiently general computable predictions also converge to the true induced measure.

The class of sequences along which the prediction converges is related to computable randomness.

We also discuss the speed of the convergence.

We prove that, even when a computable prediction predicts a computable sequence,

the speed of the convergence cannot be bounded by a computable function monotonically decreasing to $0$.

**News**

19 June 2019, Online

**Title**

Uniform relativization

**Type**

Conference survey paper

**Publication**

In: Manea F., Martin B., Paulusma D., Primiero G. (eds) Computing with Foresight and Industry. CiE 2019. Lecture Notes in Computer Science, vol 11558. Springer, Cham

**Abstract**

This paper is a tutorial on uniform relativization. The usual relativization considers computation using an oracle, and the computation may not work for other oracles, which is similar to Turing reduction. The uniform relativization also considers computation using oracles, however, the computation should work for all oracles, which is similar to truth-table reduction. The distinction between these relativizations is important when we relativize randomness notions in algorithmic randomness, especially Schnorr randomness. For Martin-Löf randomness, its usual relativization and uniform relativization are the same so we do not need to care about this uniform relativization.

We focus on two specific examples of uniform relativization: van Lambalgen’s theorem and lowness. Van Lambalgen’s theorem holds for Schnorr randomness with the uniform relativization, but not with the usual relativization. Schnorr triviality is equivalent to lowness for Schnorr randomness with the uniform relativization, but not with the usual relativization. We also discuss some related known results.

**News**

29 Mar, 2019 The slide file was uploaded.

**Title**

Schnorr triviality via decidable machines

**Type**

Invited talk in CTFM2019

The 9th International Conference on Computability Theory and Foundations of Mathematics

March 21-27, 2019. Wuhan University of Technology, Wuhan, China.

25 Mar, 2019.

**Download**

slide

**News**

18 Mar, 2019 The slide file was uploaded.

**Title**

Muchnik degrees and Medvedev degrees of the randomness notions

**Type**

A talk in AMS

Spring Central and Western Joint Sectional Meeting @ University of Hawaii

Friday March 22, 2019, 3:00 p.m.-4:20 p.m.

Special Session on Computability, Complexity, and Learning, I

**Download**

Summary from AMS

Slide