Formal Methods II

Prob 3:
w is a number
The questions are not about c and h, they are presumed to be given relative to some problem.
The answers are intended to be in when and only when w is in the interval a, b where a and b is specified, of course.
The answer might be never!

Problem 1, part 3.

Problem 4
i.
ii. are too easy
the heart of the 問題 is in iii.

Lecture 10.

Cover and Thomas can be used as a reference to this section of the lectures.

What is randomness? An event is random iff it is produced by an indeterministic process.

But then,
Everything is random
Or nothing is. (there is no such thing as an indetermanism)

We'll leave that to philosophy and physics.

We think about the computer science side of things.

The star is to indicate how long these bit strings might be.

ごく普通の英語で説明してみたらどう？もっと覚えるかもしれない。

You can compress the bit string that represents pi, it's just a program that generates the string (it's got to be smaller than infinity!)

Algorithmic randomness
Computable numbers (at large expansions) are by definition algorithmically non-random!

Cantors Diagonal Argument
Something every CS should know!

You just have to imagine that you have a list of all real and bit string numbers.

Turing - "There are Non computable numbers"
We suppose that all these numbers are computable.
There has to be a program to compute it.
Let's enumerate all possible programs.
We can't enumerate their output, but we can pretend.

We can't actually get a real random number, because they're uncomputable. So we have to put up with almost or good enough randomness that we can compute.

We more random something is, the less information there is.

English and Logic are inefficient because there is more than one way to say the same thing. Which is an indirect way of saying that it can't satisfy shannon information.