Unit 3 Homework:
Information Theory and Computability

Algorithmic Information Dynamics: A Computational Approach to Causality and Living Systems From Networks to Cells

Hector Zenil, Narsis A. Kiani, Alyssa Adams

Course available at the Santa Fe Institute MOOC platform the Complexity Explorer at: https://www.complexityexplorer.org/courses/63-algorithmic-information-dynamics-a-computational-approach-to-causality-and-living-systems-from-networks-to-cells

DateString[]

Classical Information Theory

Question 1

What happens to the entropy of a random string when increasing the number of symbols, e.g. from binary to trinary? Would the entropy increase or decrease?

Answer 1

It increases, because entropy is a function of alphabet (symbol) size. This is because the set of all possible strings grows and thus also the uncertainty if the symbols are uniformly distributed. A numerical experiment confirms it:

Table[RandomChoice[{0,1,2}, 100]//Entropy//N, 100]//Mean

Question 2

What would happen if we used base 2 for our strings made of 0’s and 1’s? What would happen if we used base 3 for our strings made of 0’s, 1’s, and 2’s? Would the entropy increase or decrease?

Answer 2

It would increase because the base acts as some sort of normalization factor making the minimum and maximum entropy to be 0 and 1

Table[Entropy[2,RandomChoice[{0,1}, 100]]//N, 100]//Mean

Table[Entropy[3,RandomChoice[{0,1,2}, 100]]//N, 100]//Mean

If we equal the base to the alphabet size, the entropy of random strings approximates 1.

Question 3

Lets keep e and investigate the behavior of entropy as a function of alphabet base.

Let’s go all the way up to alphabet size 11.

alphabetentropy=Table[Table[RandomChoice[Range[0,i], 100]//Entropy//N, 100]//Mean, {i,1,10}]

ListPlot[alphabetentropy,PlotTheme->"Business",Joined->True,PlotMarkers->Automatic]

Why do you think the curve starts to slow down?

Answer 3

Because we are increasing the number of symbols, but our string length is staying the same. If we did this same plot with longer strings, we’d see something slightly different:

alphabetentropy=Table[Table[RandomChoice[Range[0,i], 10000]//Entropy//N, 100]//Mean, {i,1,100}]

ListPlot[alphabetentropy]

Question 4

Let’s say we tossed a coin 1000 times and we got about 50% heads and 50% tails. If we measured the entropy of the heads and tails outcome, we would expect the entropy to be very close to 1, since it is a random process. However, say we found that the coin was weighted, with the tails side being heavier. How would this change the way we see our result?

Answer 4

We would be very surprised that the heads and tails distribution is close to 50-50. Given that we know the tails side is heavier, we would expect to see more heads than tails.

Question 5

Say you find a mysterious DNA sequence. It has lots of interesting patterns and redundancy. For fun, you look at the first half of the sequence and given what you see, you are able to accurately predict the second half. Good job! Would this sequence have a higher or lower Shannon entropy? Does this mean the sequence is noisy?

Answer 5

This means the sequence has low Shannon entropy and is not very noisy.

Question 6

What would you expect the conditional entropy to be between two randomly-generated strings of the same length (made of 1’s and 0’s)?

Answer 6

Will be 1 because knowing one tells you nothing about the other one, so the uncertainty remains the highest:

string1=RandomChoice[{0,1},100]
string2=RandomChoice[{0,1},100]

Statistics`Library`NConditionalEntropy[string1,string2]

Question 6

What about for the following strings?

string1=Table[1,{100}]
string2=Table[0,{100}]

Answer 6

Is zero, because H (Y | X) = 0 if and only if the value of Y is completely determined by the value of X. There are no surprised with Y just as there are no with X (and viceversa).

Statistics`Library`NConditionalEntropy[string1,string2]

Question 7

What is the Mutual Information between the following strings?

string1={0,1,0,1,0,1,0,1,0,1};

string2={1,0,1,0,1,0,1,0,1,0};

string3=RandomInteger[1,10]

Answer 7

Removed from zero between string1 and string2 because one is the complement of the other and thus knowing about one tells us a lot about the other, but closer to zero between string1 and string3 and thus between string2 and string3 because string3 was ‘randomly’ generated.

N[Entropy[string1]+Entropy[string2]-Statistics`Library`NConditionalEntropy[string1,string2]]

N[Entropy[string1]+Entropy[string3]-Statistics`Library`NConditionalEntropy[string1,string3]]

N[Entropy[string2]+Entropy[string3]-Statistics`Library`NConditionalEntropy[string2,string3]]

Question 8

What about the Mutual Information between string2 and string1?

Answer 8

It would be the same as between string1 and string2 because Mutual Information is symmetric.

N[(Entropy[string2]+Entropy[string1])-Statistics`Library`NConditionalEntropy[string2,string1]]

Computability

Question 1

Is a universal Turing machine with 1 tape computationally more powerful than a universal Turing machine with 3 tapes? What about an infinite number of tapes?

Answer 1

No, once a Turing machine is universal it reaches the maximal computational power. Adding tapes may make it faster but it is not computationally more powerful, even with an infinite number of tapes.

Question 2

Write a transition table of rules for a Turing machine with only 2 states that always halts for any input.

Answer 2

Here is one:
X, S -> H 
where X is any symbol, S is any state, and H is the halting state.

Question 3

Describe what the following Turing machine will do, based on what you can see from its following rule transition table:

symbol, state  ->  new symbol, new state, head movement (1 is right, -1 is left)
0              1           ->  1                  	1              		1
1              1           ->  0                  	1              		1

Answer 3

It will reverse the input. If the input is all 1s, it will change it to all 0s. Also the head always moves to the right.

rules={{1,0}->{1,1,1},{1,1}->{1,0,1}};

RulePlot[TuringMachine[rules],{1,{{},0}},20,Mesh->All]

Question 4

What the above Turing machine would do to the string “1010101”?

Answer 4

It would reverse it:

RulePlot[TuringMachine[rules],{1,{1,0,1,0,1,0,1}},7,Mesh->All,ImageSize->Small]

Question 5

Write the previous Turing machine as a transition diagram.

Answer 5

Question 6

Is the above Turing machine universal?

Answer 6

No, it only runs in one direction, it has only 1 state, and it has no halting state. These are many reasons why it cannot be universal.