Complexity Flashcards
How can complexity be measured?
Dawkins Approach
IDEA 1:
How much information is required to describe one thing vs another?
Remember Clippy example - no matter how complicated something might seem, the instructions may be very simple
Dawkins said… we have an intuitive sense that lobsters are more complex than millipedes. Write a book about each one and the lobster one will likely be a longer book.
We could count neurons, but that would only get us so far when we consider that brains are very large, animals may have as many neurons as we do. We could look at the components of genetic code – still problematic.
IDEA 1:
How much information is required to describe one thing vs another?
How can complexity be measured?
Dawkins Approach Critique
IDEA 1:
How much information is required to describe one thing vs another?
Although Dawkins was of thinking is useful, it is flawed.
Looking at 2 sequences of DNA. One is shorter and has a seemingly random pattern of As and Bs, the second is longer, but follows ABAB recurring.
Which is more complex?
Sequence one is more complex, despite being “less information”, as there is no fixed pattern. The sequence cannot be specified by a simple rule. The amount of information, here, doesn’t necessarily have a linear relationship with complexity (more information /= more complexity). The minimal code/program/algorithm needed for sequence 1 is probably as long as the sequence itself (16 symbols), whereas for sequence 2 it would be much shorter.
How can complexity be measured?
Dawkins Approach Critique
IDEA 1:
How much information is required to describe one thing vs another?
Although Dawkins was of thinking is useful, it is flawed.
Looking at 2 sequences of DNA. One is shorter and has a seemingly random pattern of As and Bs, the second is longer, but follows ABAB recurring.
Which is more complex?
Sequence one is more complex, despite being “less information”, as there is no fixed pattern. The sequence cannot be specified by a simple rule. The amount of information, here, doesn’t necessarily have a linear relationship with complexity (more information /= more complexity). The minimal code/program/algorithm needed for sequence 1 is probably as long as the sequence itself (16 symbols), whereas for sequence 2 it would be much shorter.
How can complexity be measured?
IDEA 1:
How much information is required to describe one thing vs another?
Algorithmic complexity
Sequence 1: AAABABBABBBAABBA
- Has greater algorithmic complexity, symbols A and B both have 50% / 50% chance of occurring, so all 16 symbols are important for coding of the sequence.
Sequence 2: ABABABABABABABABABABABABABABABABAB
Requires just 15 symbols ”repeat AB 17 times” or 20, or 30 times, so the length of the code needed for the sequence is/ could be much shorter than the actual sequence itself
The length of the shortest program that can generate S1 is greater than the length of the shortest program that can generate S2
How can complexity be measured?
IDEA 2:
How much logic/ how many operations/ how much computation does a program have to do?
Logical Depth
A problem that requires the same algorithm to run for longer has greater logical depth
Example:
Write all unique combinations of integers that sum to 3’:
1+1+1
1+2
Now…
‘Write all unique combinations of integers that sum to 4’:
1+1+1+1
1+1+2
1+3
2+2
Despite equal algorithmic complexity (the length of the shortest algorithm to generate sequence 1 and 2 is the same), sequence 2 takes more steps to compute, so has greater logical depth.
So… the sentence lengths (algorithms) are the same, but there are more steps to compute for sentence 2
What is an algorithm?
A computational recipe or set of instructions
What is logical depth?
How much logic/ how many operations/ how much computation does a program have to do
What is algorithmic complexity?
The length/ complexity of the shortest program that will generate a sequence
How can complexity be measured?
IDEA 3:
How difficult it is to deduce the simplest program that would generate an observed pattern?
/
How difficult is to work out the simplest program that would generate our observed complexity?
Crypticity
Example – Enigma Machine
Enigma machine was very simple (small machine) – this is what encrypted the messages
The Turing Machine was very complicated (very large machine) – this is what decoded the messages
What is crypticity?
How difficult it is to deduce the simplest program that would generate an observed pattern?
OR
How difficult is to work out the simplest program that would generate our observed complexity?
