Why do we need to dummy code categorical variables? I am not sure why we need to dummy code categorical variables. For instance, if I have a categorical variable with the four possible values 0, 1, 2, 3, I can replace it by two dimensions: if the variable had value 0, it would have 0, 0 in the two dimensions; if it had 3, it would have 1, 1 in the two dimensions; and so on.
I am not sure why we need to do this?
 A: Suppose your four categories are  eye colors (code): brown (1), blue (2), green (3), hazel (4)—ignoring heterochromia, violet, red, gray, etc. for the moment.
In no way (that I can currently imagine) would we mean that green $ = 3\times $ brown, or that hazel $=2\times$ blue as our codes imply, even though $3=3\times1$ and $4 = 2 \times 2$.
Therefore (unless we for some reason do want such meaning to slip into our analyses), we need to use some sort of coding. Dummy coding is one example, which eliminates such relationships from the statistical stories we want to tell about eye color. Effect coding and Heckman coding are other examples.
Update: your example of two variables for four categories does not match my understanding use of the term "dummy code" which typically entails replacing $k$ categories (say 4) with $k-1$ dummy variables (sorting observations by category):
id  category  dummy1 dummy2 dummy3
 1         1       1      0      0
 2         1       1      0      0
 3         2       0      1      0
 4         2       0      1      0
 5         3       0      0      1
 6         3       0      0      1
 7         4       0      0      0
 8         4       0      0      0

Here category 4 is the reference category, assuming that there is a constant in your model, such as:
$$y = \beta_{0} + \beta_{1}d1 + \beta_{2}d2 + \beta_{3}d3 + \varepsilon$$
where $\beta_{0}$ is the mean value of $y$ when category = 4, and the $\beta$ terms associated with each dummy indicate by what amount $y$ changes from $\beta_{0}$ for that category.
If you do not have a constant ($\beta_{0}$) term in the model, then you need one more "dummy" predictor (perhaps less often termed "indicator variables"), in effect the dummies then each behave as the model constant for each category:
$$y = \beta_{1}d1 + \beta_{2}d2 + \beta_{3}d3 + \beta_{4}d4 + \varepsilon$$
So this would get one around the issue of creating nonsensical quantitative relationships between category codes I mention at first, but why not use user12331-coding as you suggest? user12331-coding candidate A:
id  category   code1  code2
 1         1       0      ?
 2         1       0      ?
 3         2       1      ?
 4         2       1      ?
 5         3       ?      0
 6         3       ?      0
 7         4       ?      1
 8         4       ?      1

you are quite right to point out that one can represent 4 values using 2 binary variables (i.e. two-bits). Unfortunately, one approach to this (code1 for categories 1 and 2, and code2 for categories 3 and 4) leaves the ambiguity indicated by the question marks: what values would go there?!
Well, what about a second approach, call it user12331-coding candidate B:
id  category   code1  code2
 1         1       0      0
 2         1       0      0
 3         2       0      1
 4         2       0      1
 5         3       1      0
 6         3       1      0
 7         4       1      1
 8         4       1      1

There! No ambiguity, right? Right! Unfortunately, all this coding does is represent the numerical quantities 1–4 (or 0–3) in binary notation, which leaves intact the problem of giving those undesired quantitative relationships to the categories.
Hence, the need for another coding scheme.
I will close with the caveat that the various coding schemes are more or less a matter or style (i.e. what does one want a specific $\beta$ to mean) unless one also includes interaction terms with the categories in the model. Then dummy coding will induce an artificial heteroscedasticity and bias the standard errors, so you would want to stick with effect coding in such a case (there may be other coding systems that keep one safe in that circumstance, but I am unfamiliar with them).
A: My take on this question is, that coding the four possible states with just two variables is less expressive with some machine learning algorithms than using 4 variables. 
For example, imagine that you want to do linear regression and your true mapping maps the values 0,1 and 2 to 0 and the value 3 to 1. You can quickly check that there is no way of learning this mapping with linear regression when coding your categorial variable with just two binary ones (just try to fit the corresponding plane in your head). On the other hand, when you use a 1-Of-K coding, this would not be a problem. 
A: If you are to encode your example as:




Colour
Category
Binary1
Binary2




Hazel
0
0
0


Blue
1
0
1


Green
2
1
0


Brown
3
1
1




If your question is why do we use Encoding, lets consider the above example if you have 4 categories of colour of eyes according to what @Alexis suggested, we need to convert these categories into numbers because computers work better with numbers. So essentially we transform these four colour categories into respective integers categories, as shown above. Now if you are to give these integers as it is to the computer then depending on the integer values the computer will take out a relation as thus:
Brown colour has been given a value 3, so it must be greater than the hazel colour denoted by 0 in terms of importance to colour with respect to the label you have to predict. This is wrong because the aim to provide an integer to text was just to make the calculation and evaluation easy for the computer. So to prevent learning wrong relations between features and output we need encoding
What encoding essentially means is to create new dummy features corresponding to each colour ie if we have 'm' labels we can have maybe 'm' feature columns or 'm-1' feature columns depending on the encoding algorithm used. So if we were to represent the above table in terms of encoded values it would be:




Colour
Category
Hazel
Blue
Green
Brown




Hazel
0
1
0
0
0


Blue
1
0
1
0
0


Green
2
0
0
1
0


Brown
3
0
0
0
1




In the above table what we did was to represent the categories by new columns called dummy features and corresponding to the colour its respective dummy column recieved a value 1 and rest were set to 0. While training, we do not need the category and colour columns because we have encoded them as dummy features.
Note: If you perform transformation and encoding on training set, then transformation and encoding must be performed on the test set also.
Returning back to the question. If it were to be framed as, if we can represent the category of integers by their binary couterparts then the answer would be no because essentially what you are doing is replacing the integers by their binary numbers. This does not validate or show the relation between the respective categories and the output of training would be the same as that with the integer values or maybe even worse.
Refer the link below for more info:
Feature Engineering on Categorical data
A: Your alternative is also a dummy code. You choose the dummy code that best expresses the relationship to your dependent variable. Eg colour could be expressed as 1 of n, or you could turn into numeric rgb components, or you could categorise: girly/muddy/...1 of n basically means each instance is learnt separately which is good if there is no relationship. .. but where there is a relationship you are wasting your data..you have to separately estimate the coefficient for each instance of the category...consider job as a categorical variable. You might re categorise as market sector and seniority.
