Chosen topics

Question 1

Rice’s theorem

Answer 1

You can’t declare any non trivial declaration about a programs functionality

Question 2

Proving undecidability using Rice’s theorem

Answer 2

Declare the language as an index group of a group game. Then show that game is non trivial (has at least one function in it and at least one that is not). Generally, if there is reference to how the program is written, than you can’t prove using this.

Question 3

Proving unacceptable using Rice’s theorem

Answer 3

If in addition to rice’s theorem terms, ℎ(𝑥)∈Γ (the empty functions, never stops) then you can prove that it is unacceptable.

Question 4

The game of life (rules)

Answer 4

1. Infinite grid
2. A living cell with less than two living neighbors will die from loneliness.
3. A living cell with more than three living neighbors will die from density.
4. A dead cell with exactly 3 neighbors will be born.

Question 5

The game of life (power)

Answer 5

1. A model equivalent to a Turing machine.
2. Given a state of the world there is no predicting if the population will be extinct or not.
3. The problem is equivalent to the halting problem.

Question 6

Short Hebrew number

Answer 6

A short Hebrew number is any natural number that can be described in under 100 characters.

Question 7

Berry’s paradox

Answer 7

“The smallest number that is not a short Hebrew number”. the paradox is that it is since you can describe it in less than 100 letters.

Question 8

How to describe a binary number (M,w) so that x=M(w)

Answer 8

We double each character in M and than operate M and w using 0: M=11010 ו- w=0101(M,w)=1111001100010101

Question 9

Kolmogorov complexity

Answer 9

The shortest description of a word x: d(x)
The Kolmogorov complexity of a word: k(x) = |d(x)|

Question 10

Kolmogorov complexity rules

Answer 10

∃c∀x[k(x) ≤ |x| + c]

∃c∀x[k(xx) ≤ k(x) + c]

∃c∀x,y[k(xy) ≤ 2k(x) + k(y) + c]

Question 11

Kolmogorov complexity definitions (compressible and un compressible)

Answer 11

1. x is compressible by factor c if k(x) ≤ |x| - c
2. x is incompressible if it isn’t compressible by a factor of 1.

Question 12

For every number n there are strings of length n which are not compressible

Answer 12

there are only 2^n strings of length n. and 2^n - 1shorter strings.

Question 13

x is compressible is acceptable but undecidable (proof)

Answer 13

acceptable: Given a string x we will guess a shorter string y which is a description of (M,w). If the machine stopped and x is on the strip we are done. If not try again.

Question 14

Why is berry’s paradox wrong?

Answer 14

Berry’s paradox assumes that you can decide if a word has a compression or not. Which is not possible.