Construction of a Kurtz random sequence that's not Martin-Löf random

131 Views Asked by At

How can one construct a Kurtz random sequence that's not Martin-Löf random?

I'm also interested in the paper that included the first of such constructions. I suspect it was in Kurtz's dissertation, but it's not very accessible.

I'd be grateful for you help in this matter.

1

There are 1 best solutions below

1
On BEST ANSWER

Check out Nies' Computability and Randomness, section 3.5. There he shows that every weakly 1-generic sequence is Kurtz random (Fact 3.5.4) and that weakly 1-generics fail the law of large numbers (Proposition 3.5.5). Since every Martin-Löf random satisfies the law of large numbers, one need only construct a weakly 1-generic.