Representations → “Data”
Different representation can lead to much different computations and different results
For example, in Roman Numeral, 42 is represented as XLII
How can we represent the distance to moon in Roman Numeral? It would be a hard job to do.
Operations → “Algorithms”
E.g. Multiplication
input (x, y) output (x * y)
one way(algorithm) to implement is to use repeated addition
second way: input (digits of x, digits of y)
for the first digit to the last digit of x (i):
for the first digit to the last digit of y (j):
result += 10^(i+j) $x_i \cdot y_i$
if we have 2 20-digits number, we’d need to do $10^{20}$ calculations if we use the first method. However, if we use the second method, we only need to do 400 calculations
Think about “what can’t we compute” first.
Essentially, this is asking that “can a computer solve a problem P?”