In this post I will give a basic example of the necessity (or uselessness – its up to you to choose – pun intended) of the axiom of choice. I will also present a less known proof of the Cantor–Bernstein–Schroeder theorem.

The Cantor–Bernstein–Schroeder Theorem

Let A and B be sets. Let f:A->B and g:B->A be injective functions. Then there exists a bijection h:A->B.

In order to proof the theorem, lets consider the following definition:

A function f:P(A)->P(A) is called monotonic if X is contained in Y => f(X) is contained in f(Y), for all X,Y in P(A).

Lemma 1

Every monotonic function f:P(A)->P(A) has a fixed point, i.e. a set X in P(A) such that f(X) = X. (The proof of this lemma is very simple, if you have the time, try to prove it yourself before reading on).

Proof of Lemma 1 

Let T be the set { X | F(X) is contained in X }. Then T is not empty (as A is in T). Let S be the intersection of all the elements of T (it exists as T is not empty). Then since S is contained in all X in T, F(S) is contained in F(X) for all X in T (by the monotonicity of F). But, by the very definition of T, F(X) is contained in X for all X in T, so F(S) is contained in X for all X in T, so F(S) is contained in the intersection of all the elements of T, so F(S) is contained in S, giving that S is an element of T. Now, by the monotonicity of F, F(F(S)) is contained in F(S) so F(S) is also an element of T. This gives that S in contained in F(S) (as S is the intersection of all the elements of T) and so S = F(S) and S is a fixed point of F.

–

Now we are ready to proof the Cantor–Bernstein–Schroeder theorem.

Proof of the Cantor–Bernstein–Schroeder Theorem

First, note that it is enough to prove that if A1 is contained in B, and B is contained in A, and f is a bijection from A to A1, then there exists a bijection g from A to B (make sure you understand why this claim and the C-B-S theorem are indeed equivalent).

In what follows I shall use the notation A U B to denote the union of A and B.

Define h:P(A)->P(A) as h(X) = {f(x) | x is in X} U (A\B). It is trivial that h is monotonic. By lemma 1, there is a fixed point C of h. Define a function g:A->B as

g(x) = f(x) if x is in C, x otherwise.

Then g is a bijection between A and B. Indeed note that g stabilizes both C and A\C (i.e. g(x) is in C i.f.f. x is in C). Indeed, if x is in C, then g(x) = f(x) which is in f(C), which is contained in f(C) U (A\B) = h(C) = C. So x is in C => g(x) is in C. Otherwise x is not in C, and so g(x) = x, and obviously g(x) is not in C.

Now, if g(x) = g(y), by what was said above, either both x and y are in C, or both are in A\C. Either way, this gives x = y. So g is injective.

To show sujectivity of g, we note that if x is in B and in C, then by the structure of C (= f(C) U (A\B)), x is in f(C). Now g(C) = f(C), so x is in the image of g. Otherwise, if x is in B and not in C, then g(x) = x and again x is in the image of g. We showed that g is surjective. Surjectivity and injectivity imply that g is a bijection, and the C-B-S theorem is proved.

–

Let N denote the set {0, 1, 2, …} of natural numbers. Lets begin by showing that the sets N and NxN (i.e. the set of pairs of natural numbers) are of the same cardinality (i.e. that there exists a bijection f:NxN->N). We call sets of the same cardinality as N countable (note that sets whose cardinality is the same or of lesser than that of N are called at most countable). I will give two proofs of the following theorem (which can be rephrased to: “NxN is a countable set”).

Theorem 1

The sets N and NxN are of the same cardinality.

Proof 1 - Using the C-B-S Theorem

Consider the functions, f:N->NxN and g:NxN->N given by: f(n) = (n,0) and g(n,m) = (2^n)*(3^m). It is obvious that f and g are injective. By the C-B-S theorem N and NxN are of the same cardinality.

Proof 2 - Actual Construction

Lets build such a function f. Let f(m,n) = (2*n+1)*2^m – 1. Now 

f(m,n) = f(u,v)

=> (2*n+1)*2^m – 1 = (2*v+1)*2^u – 1

=> (2*n+1)*2^m = (2*v+1)*2^u

=> (2*n+1)*2^m = (2*v+1)*2^u (mod 2^m)

=> 0 = (2*v+1)*2^u (mod 2^m)

=> 0 = 2^u (mod 2^m)

=> m <= u.

Symmetrically, u <= m, so u = m. Then,

=> (2*n+1) = (2*v+1)

=> n = v

So f is injective. If n is in N \ {0}, then n = s*2^k, where s is odd. Then there exists t, such that s = 2*t + 1. Then f(k,t) = n. If n = 0, then f(0,0) = 1-1 = 0 = n. So f is surjective.

We have shown f to be a bijection between NxN and N and so these sets are of the same cardinality.

The Axiom of Choice

The reason I have gone through all of the above, although I know that to many of you it may seem trivial, is to emphasize the need for the axiom of choice. Lets consider the following theorem:

Theorem 2

A union of countably many disjoint countable sets is countable.

Now, a little reflection may suggest that this is a trivial consequence of what was proved before. We have a countable family of sets A = {A1, A2, …} where each set Ai is countable. So for each i, there is a bijection Fi:N->Ai. So there is a bijection g:NxN->U(Ai) given by g(i,j) = Fi(j). g is indeed a bijection as the Ai’s are disjoint.

Well, surprisingly the above does not constitute a proof of theorem 2!

Not only that, I claim that theorem 2 cannot be proved without employing the axiom of choice. Before going on any further, lets write down this axiom of choice we keep talking about:

The Axiom of Choice

Let S be a family of non-empty sets. Then there exists a function f:S->U(S) such that f(S) is in S.

Note that U(S) denotes the union of all the elements of S.

This may seem trivial. After all, since all the elements of S are non-empty, they each contain at least one member. So there must be a function that maps to each set one of its elements!

Indeed, for the case that S is finite, we can prove the constructability of the function f in the axiom of choice (thus the axiom of choice for the case that S is finite, no longer needs to be an axiom). Say S = {A1, A2, …, An}, where each Ai  is non-empty (1 <= i <= n). Then there exist elements {a1, a2, …, an} such that ai is in Ai. Now define f(Ai) = ai.

As it turns out, for infinite S, that this construction is possible is no longer a consequence of the other axioms of set theory. Say S = {A1, A2, …} and A1, A2, … are non-empty so that ai is a member of Ai. We can define a function f:S->U(S) such that f(Ai) = a1 for all i. We can also define a function f, such that f(A1) = a1, and f(Ai) = a2 for all i not in {1}. We can continue with this process for any finite number of steps, creating a function f:S->U(S) such that f(Ai) = ai for all i < n, and f(Ai) = a1 for i >= n. The point here is that we cannot perform this process for an infinite number of steps.

Some Examples

To put the axiom of choice in very popular terms: we can perform any finite number of arbitrary choices of elements from sets, but we cannot perform an infinite number of arbitrary such choices. 

For example, say that S = {A1, A2, …} and each set Ai={1,i}. Then the following functions f,g:S->U(S) exist without assuming the axiom of choice

f(Ai) = 1, g(Ai) = i.

If it is know that each set Ai is of size 2 containing the element 1, then the following functions can also be shown to exist w/o assuming the axiom of choice:

f(Ai) = 1, g(Ai) = the unique element of Ai\{1}.

Now, if it is known that the sets Ai are disjoint and of each contains exactly two natural numbers, then, again, the functions

f(Ai) = max(Ai), g(Ai) = min(Ai)

can  be shown to exist without assuming the axiom of choice. This principal can be extended to the case where the sets Ai are contained in a set A having an order relation with the property that each non-empty subset of A has a least element (we say that the order relation is a well ordering of A). Then we can define:

f(Ai) = least element of Ai.

If on the other hand all that is known on the sets Ai is that they contain exactly two members, the existence of a function f as in the axiom of choice is not a consequence of any of the other axioms.

The previous two examples suggest an alternative formulation for the axiom of choice, namely that we can define a well ordering on any set. If this were true, we could define a well ordering on the set U(Ai) and define f as above. Indeed it turns out that the axiom of choice is equivalent to the principal that we can define a well ordering on any set (in the sense that using the other axioms of set theory and any one of the above we can prove the other).

On the Existance of Sets

To avoid paradoxes (such as Russell’s paradox), we must constrain ourselves to assuming the existence of only those objects which can be shown to exist from the axioms. For example, let S be the set of all sets (i.e. every set is a member of S). Then by Cantor’s theorem (that P(X) is always of a larger cardinality than X) S cannot exist!

The point to note here is that the mere description of a set does not guaranty its existence.

Now, the same applies to functions (for the purists of you – this is simply a special case of the preceding sentence as all functions are actually sets). The mere description of a function does not guaranty its existence.

As it turns out, the existence of the function f which appears in the axiom of choice, in the case that S is infinite, does not follow from the other axioms of set theory (it can in fact be shown that instead of accepting the axiom of choice, accepting an axiom declaring the in-existence of the function f does not lead to any contradictions with the other axioms of set theory!).

Now, lets consider a valid proof of theorem 2 using the axiom of choice.

Proof of Theorem 2

S = { A1, A2, … } is a countable set of disjoint countable sets. That Ai is countable is equivalent to the statement: Fi = { f | f is a bijection between N and Ai } is a non-empty set. Consider the set T = {F1, F2, …}. T is a set of non-empty sets, so by the axiom of choice there is a function g:T->U(T) such that g(Fi) is in Fi.

Define h:NxN->S as follows:

h(i,j) = g(Fi)(j)

Then obviously h is a bijection.

The reason h does exist, is subtle. It relies on the fact that for each input a clear procedure for calculating the output of the function can be given. I know this is vague, and should you be interested, I will give a full construction of h, demonstrating its existence, in a future post.

Some Thoughts

So, does the above example demonstrate that the axiom of choice really is necessary?

Not really. Consider the following theorem:

Theorem 2b

Let S be a countable family of pairs {(Ai,Fi)} such that the Ai’s are countable and disjoint and Fi is a bijection from N to Ai. Then U(Ai) is countable.

Proof w/o the Axiom of Choice

Define f:NxN->U(Ai) as follows:

f(i,j) = Fi(j).

Obviously f is injective and surjective. Thus we have constructed a bijection from NxN to U(Ai), and by theorem 1, U(Ai) is countable.

Now, in all practical cases (that I can think of – please comment onthis if you have a good counter example) we never use the fact that the set is countable without explicitly having a bijection between the set and N. So, in all practical cases, the weaker version of theorem 2 (namely theorem 2b) can be used.

Final Note 

The acceptance of the axiom of choice seems very logical. Nevertheless, it should be mentioned that it results in some very undesirable consequences, such as unmeasurable sets and the Banach-Tarski paradox (which is very interesting and on which I shall write in a future post).

Finally, I included the axioms of set theory, for your convenience:

Dany Valevsky gave me this very cool riddle.

You are given a vector of size N, the elements of which are numbers in the range 1,…,N-1. I.e. there is at least one repeating element. Give an algorithm that finds a repeating element (it does not matter which one, in case there are several) with O(N) time complexity and O(1) memory complexity.

NOTE - the time and memory complexities are calculated in integers. I.e. the input is of size N, not N*logN.

That’s it!

A ship in the plane has integer coordinates. It also has integer velocity (again in ZxZ). Each turn the ship advances according to its velocity. Here is an example of a ship with velocity (3, 1).

You, as a pirate, want to blow up the ship. You do not know the original position of the ship nor its velocity. You can only shoot one bomb per turn, which blows up exactly one point of the plane. What strategy should you employ in order to be sure you will eventually hit the ship?

It is very recommended to watch to this video while solving the riddle. It provides great inspiration!

Thanks to Nadav Sherman for giving me this riddle.

 In this post I will define turing machines and demonstrate a simple one in action.

Definition of a Turing Machine

A turing machine (TM) description consists of a tuple of 7 objects: a set of states Q, an input alphabet I, a tape alphabet T, a transition function F, a set of accept states Qaccept, a set of reject states Qreject and a start state Qstart.

The following requirements must hold: I is contained in T. ‘ ‘ (the space symbol) is a member of T but not of I. F is a function from QxT->QxTx{1,-1}. Qaccept and Qreject are disjoint subsets of Q. Qstart is a member of Q.

The turing machine itself consists of: its description (as defined above), an infinite tape, a head and a current state.

The tape is an infinite list of symbols from T (it is only infinite to the right, i.e. it has indexes 0, 1, 2, … but no negative indexes). The tape initially contains the input (a string of symbols from I) starting at index 0 followed by infinitely many ’ ‘ (space) symbols. As we required that the ‘ ‘ symbol is not a member of I the TM can detect the end of the input.

The head is simply a pointer to the tape. It initially points to tape position 0.

The current state is a member of Q, and is initialized to Qstart.

Operation

A TM with a description {Q, I, T, F, Qaccept, Qreject, Qstart} is initialized as indicated above. The result of its operation consists of the contents of the tape as well as an additional flag which can be either ACCEPT or REJECT. In the description below, the action accept means setting this flag to the ACCEPT state and halting. The same goes for the reject action.

The TM operates as follows:

1. If current_state is in Qaccept, accept. If it is in Qreject, reject.
2. Read a symbol from the tape at the position indicated by the head. Denote it as current_symbol.
3. Set next_state, next_symbol, next_head_pos to F(current_state, current_symbol).
4. Write next_symbol to the tape at the current head position.
5. If next_head_pos is 1 move the head one position to the right.
6. If next_head_pos is -1 move the head one position to the left. If the head tries to move to the left from position 0, do not move the head.
7. Set current_state to next_state.

And that’s it!

An Example

The following is the description of a TM that multiplies two integers in unary notation. For example, if its input is of the form ’111*11=’ it will accept with an output tape of ’111*11=111111′.

The code of the machine:

TMUnaryMultiply = {
    'description' : """The input must be of the form '11*111='. The output tape will look like '11*111=111111'.""",
    'start_state' : 'mark_start',
#input verification
    'mark_start' :
        {
            '1':['verify_input_1','#',1],
        },
    'verify_input_1' :
        {
            '1':['verify_input_1','1',1],
            '*':['verify_input_*','*',1]
        },
    'verify_input_*' :
        {
            '1':['verify_input_2','1',1]
        },
    'verify_input_2' :
        {
            '1':['verify_input_2','1',1],
            '=':['verify_input_ ','=',1]
        },
    'verify_input_ ' :
        {
            ' ':['move_head_to_left',' ',-1]
        },
    'move_head_to_left':
        {
            '1':['move_head_to_left','1',-1],
            '=':['move_head_to_left','=',-1],
            '*':['move_head_to_left','*',-1],
            '#':['read_ones','1',-1] # this will try to move the head off the tape
        },
# actual multiplication
    'read_ones' :
        {
            '1':['wait_for_*', '#', 1],
            '*':['halt','*', -1],
        },
    'wait_for_*' :
        {
            '1':['wait_for_*', '1', 1],
            '*':['copy_ones', '*', 1]
        },
    'copy_ones' :
        {
            '1':['wait_for_=', '#', 1],
            '=':['move_left2','=', -1],
        },
    'wait_for_=' :
        {
            '1':['wait_for_=','1',1],
            '=':['wait_for_ ','=',1]
        },
    'wait_for_ ' :
        {
            '1':['wait_for_ ','1',1],
            ' ':['move_left','1',-1]
        },
    'move_left':
        {
            '1':['move_left','1',-1],
            '=':['move_left','=',-1],
            '#':['copy_ones','1', 1]
        },
    'move_left2':
        {
            '1':['move_left2','1',-1],
            '*':['move_left2','*',-1],
            '#':['read_ones','1', 1]
        },
    'halt' : {}
}

I think the format of the description is self explanatory (for the python connoisseurs among you, it consists of some nested dictionaries). It can be fed into my Python TM Emulator (the code of which is included at the end of this article). The emulator can also automatically generate a flow graph of the TM. Here is a sample ouput:

Running the emulator (in verbose mode) with the TMUnaryMultiply description above on the input ’111*11=’ results in the following:

Initialing TM [The input must be of the form '11*111='. The output tape will look like '11*111=111111'.]...
Running tm with input [111*11=]...
                          V
<          mark_start>: ['1', '1', '1', '*', '1', '1', '=', ' ']
                               V
<      verify_input_1>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                    V
<      verify_input_1>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                         V
<      verify_input_1>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                              V
<      verify_input_*>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                                   V
<      verify_input_2>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                                        V
<      verify_input_2>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                                             V
<      verify_input_ >: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                                        V
<   move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                                   V
<   move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                              V
<   move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                         V
<   move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                    V
<   move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                               V
<   move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                          V
<   move_head_to_left>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                          V
<           read_ones>: ['1', '1', '1', '*', '1', '1', '=', ' ']
                               V
<          wait_for_*>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                    V
<          wait_for_*>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                         V
<          wait_for_*>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                              V
<           copy_ones>: ['#', '1', '1', '*', '1', '1', '=', ' ']
                                                   V
<          wait_for_=>: ['#', '1', '1', '*', '#', '1', '=', ' ']
                                                        V
<          wait_for_=>: ['#', '1', '1', '*', '#', '1', '=', ' ']
                                                             V
<          wait_for_ >: ['#', '1', '1', '*', '#', '1', '=', ' ']
                                                        V
<           move_left>: ['#', '1', '1', '*', '#', '1', '=', '1']
                                                   V
<           move_left>: ['#', '1', '1', '*', '#', '1', '=', '1']
                                              V
<           move_left>: ['#', '1', '1', '*', '#', '1', '=', '1']
                                                   V
<           copy_ones>: ['#', '1', '1', '*', '1', '1', '=', '1']
                                                        V
<          wait_for_=>: ['#', '1', '1', '*', '1', '#', '=', '1']
                                                             V
<          wait_for_ >: ['#', '1', '1', '*', '1', '#', '=', '1']
                                                                  V
<          wait_for_ >: ['#', '1', '1', '*', '1', '#', '=', '1', ' ']
                                                             V
<           move_left>: ['#', '1', '1', '*', '1', '#', '=', '1', '1']
                                                        V
<           move_left>: ['#', '1', '1', '*', '1', '#', '=', '1', '1']
                                                   V
<           move_left>: ['#', '1', '1', '*', '1', '#', '=', '1', '1']
                                                        V
<           copy_ones>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
                                                   V
<          move_left2>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
                                              V
<          move_left2>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
                                         V
<          move_left2>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
                                    V
<          move_left2>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
                               V
<          move_left2>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
                          V
<          move_left2>: ['#', '1', '1', '*', '1', '1', '=', '1', '1']
                               V
<           read_ones>: ['1', '1', '1', '*', '1', '1', '=', '1', '1']
                                    V
<          wait_for_*>: ['1', '#', '1', '*', '1', '1', '=', '1', '1']
                                         V
<          wait_for_*>: ['1', '#', '1', '*', '1', '1', '=', '1', '1']
                                              V
<           copy_ones>: ['1', '#', '1', '*', '1', '1', '=', '1', '1']
                                                   V
<          wait_for_=>: ['1', '#', '1', '*', '#', '1', '=', '1', '1']
                                                        V
<          wait_for_=>: ['1', '#', '1', '*', '#', '1', '=', '1', '1']
                                                             V
<          wait_for_ >: ['1', '#', '1', '*', '#', '1', '=', '1', '1']
                                                                  V
<          wait_for_ >: ['1', '#', '1', '*', '#', '1', '=', '1', '1']
                                                                       V
<          wait_for_ >: ['1', '#', '1', '*', '#', '1', '=', '1', '1', ' ']
                                                                  V
<           move_left>: ['1', '#', '1', '*', '#', '1', '=', '1', '1', '1']
                                                             V
<           move_left>: ['1', '#', '1', '*', '#', '1', '=', '1', '1', '1']
                                                        V
<           move_left>: ['1', '#', '1', '*', '#', '1', '=', '1', '1', '1']
                                                   V
<           move_left>: ['1', '#', '1', '*', '#', '1', '=', '1', '1', '1']
                                              V
<           move_left>: ['1', '#', '1', '*', '#', '1', '=', '1', '1', '1']
                                                   V
<           copy_ones>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1']
                                                        V
<          wait_for_=>: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1']
                                                             V
<          wait_for_ >: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1']
                                                                  V
<          wait_for_ >: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1']
                                                                       V
<          wait_for_ >: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1']
                                                                            V
<          wait_for_ >: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1', ' ']
                                                                       V
<           move_left>: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1', '1']
                                                                  V
<           move_left>: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1', '1']
                                                             V
<           move_left>: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1', '1']
                                                        V
<           move_left>: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1', '1']
                                                   V
<           move_left>: ['1', '#', '1', '*', '1', '#', '=', '1', '1', '1', '1']
                                                        V
<           copy_ones>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1', '1']
                                                   V
<          move_left2>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1', '1']
                                              V
<          move_left2>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1', '1']
                                         V
<          move_left2>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1', '1']
                                    V
<          move_left2>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1', '1']
                               V
<          move_left2>: ['1', '#', '1', '*', '1', '1', '=', '1', '1', '1', '1']
                                    V
<           read_ones>: ['1', '1', '1', '*', '1', '1', '=', '1', '1', '1', '1']
                                         V
<          wait_for_*>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1']
                                              V
<           copy_ones>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1']
                                                   V
<          wait_for_=>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1']
                                                        V
<          wait_for_=>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1']
                                                             V
<          wait_for_ >: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1']
                                                                  V
<          wait_for_ >: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1']
                                                                       V
<          wait_for_ >: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1']
                                                                            V
<          wait_for_ >: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1']
                                                                                 V
<          wait_for_ >: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', ' ']
                                                                            V
<           move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
                                                                       V
<           move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
                                                                  V
<           move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
                                                             V
<           move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
                                                        V
<           move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
                                                   V
<           move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
                                              V
<           move_left>: ['1', '1', '#', '*', '#', '1', '=', '1', '1', '1', '1', '1']
                                                   V
<           copy_ones>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1', '1']
                                                        V
<          wait_for_=>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1']
                                                             V
<          wait_for_ >: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1']
                                                                  V
<          wait_for_ >: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1']
                                                                       V
<          wait_for_ >: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1']
                                                                            V
<          wait_for_ >: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1']
                                                                                 V
<          wait_for_ >: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1']
                                                                                      V
<          wait_for_ >: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', ' ']
                                                                                 V
<           move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
                                                                            V
<           move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
                                                                       V
<           move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
                                                                  V
<           move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
                                                             V
<           move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
                                                        V
<           move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
                                                   V
<           move_left>: ['1', '1', '#', '*', '1', '#', '=', '1', '1', '1', '1', '1', '1']
                                                        V
<           copy_ones>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1', '1', '1']
                                                   V
<          move_left2>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1', '1', '1']
                                              V
<          move_left2>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1', '1', '1']
                                         V
<          move_left2>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1', '1', '1']
                                    V
<          move_left2>: ['1', '1', '#', '*', '1', '1', '=', '1', '1', '1', '1', '1', '1']
                                         V
<           read_ones>: ['1', '1', '1', '*', '1', '1', '=', '1', '1', '1', '1', '1', '1']
accept

Finally, here is the code of my Python TM Emulator:

class TM:
    def __init__(self, states, accept_states, reject_states):
        print 'Initialing TM [%s]...' % (states['description'])
        self.states = states
        self.accept_states = accept_states
        self.reject_states = reject_states
        self.halt_states = accept_states + reject_states
def run(self, input,verbose=False):
        head_pos = 0
        current = self.states['start_state']
        tape = [x for x in input]+[" "]
        while current not in self.halt_states:
            if verbose:
                print ' '*(22+1+1+1+5*(head_pos)+1)+'V'
                print '<%20s>: %s' % (current, tape)
            try:
                next_state, next_symbol, head_movement = self.states[current][tape[head_pos]]
            except KeyError:
                return "reject"
            tape[head_pos] = next_symbol
            head_pos += head_movement
            if head_pos < 0:
                head_pos = 0
            elif head_pos == len(tape):
                tape.append(" ")
            current = next_state
        print ''.join(tape)
        if current in self.accept_states:
            return 'accept'
        else:
            assert(current in self.reject_states)
            return 'reject'


And that of a simple test method:

def test():
    mul = TM(TMUnaryMultiply, ["halt"], [""])
    inputs = ['bad_input','111*11=','1*1=','*1=','1*=','11111111*1111111=']
    for input in inputs:
        print 'Running tm with input [%s]...' % (input)
        print mul.run(input)

A sample output:


>>> test()
Initialing TM [The input must be of the form '11*111='. The output tape will look like '11*111=111111'.]...
Running tm with input [bad_input]...
reject
Running tm with input [111*11=]...
111*11=111111
accept
Running tm with input [1*1=]...
1*1=1
accept
Running tm with input [*1=]...
reject
Running tm with input [1*=]...
reject
Running tm with input [11111111*1111111=]...
11111111*1111111=11111111111111111111111111111111111111111111111111111111
accept

A second, more interesting TM performs binary addition:


TMBinaryAddReverse = {
    'description' : """The input must be of the form '1010+0010=' (i.e. in reversed binary notation, operands of same size padded with an extra 0). The output will look like '1010+0010=1110'.""",
    'start_state' : 'mark_start_carry_0',
    'halt': {},
    'mark_start_carry_0' :
    {
        '1':['sum_1','#',1],
        '0':['sum_0','#',1],
        '+':['halt','+',1]
    },
    'mark_start_carry_1' :
    {
        '1':['sum_2','#',1],
        '0':['sum_1','#',1],
        '+':['halt','+',1]
    },
    'sum_0' :
    {
        '1':['sum_0','1',1],
        '0':['sum_0','0',1],
        '+':['sum_0_get_next','+',1],
        '=':['write_0','=',1],
    },
    'sum_1' :
    {
        '1':['sum_1','1',1],
        '0':['sum_1','0',1],
        '+':['sum_1_get_next','+',1],
        '=':['write_1','=',1],
    },
    'sum_2' :
    {
        '1':['sum_2','1',1],
        '0':['sum_2','0',1],
        '+':['sum_2_get_next','+',1],
        '=':['write_2','=',1],
    },
    'sum_3' :
    {
        '1':['sum_3','1',1],
        '0':['sum_3','0',1],
        '=':['write_3','=',1],
    },
    'sum_1_get_next':
    {
        '#':['sum_1_get_next','#',1],
        '1':['sum_2','#',1],
        '0':['sum_1','#',1],
    },
    'sum_0_get_next':
    {
        '#':['sum_0_get_next','#',1],
        '1':['sum_1','#',1],
        '0':['sum_0','#',1],
    },
    'sum_2_get_next':
    {
        '#':['sum_2_get_next','#',1],
        '1':['sum_3','#',1],
        '0':['sum_2','#',1],
    },
    'write_0':
    {
        '1':['write_0','1',1],
        '0':['write_0','0',1],
        ' ':['move_left_carry_0','0',-1],
    },
    'write_1':
    {
        '1':['write_1','1',1],
        '0':['write_1','0',1],
        ' ':['move_left_carry_0','1',-1],
    },
    'write_2':
    {
        '1':['write_2','1',1],
        '0':['write_2','0',1],
        ' ':['move_left_carry_1','0',-1],
    },
    'write_3':
    {
        '1':['write_3','1',1],
        '0':['write_3','0',1],
        ' ':['move_left_carry_1','1',-1],
    },
    'move_left_carry_0':
    {
        '0':['move_left_carry_0','0',-1],       
        '1':['move_left_carry_0','1',-1],       
        '=':['move_left_carry_0','=',-1],       
        '#':['move_left_carry_0','#',-1],       
        '+':['move_left_carry_0_part_2','+',-1],       
    },
    'move_left_carry_1':
    {
        '0':['move_left_carry_1','0',-1],       
        '1':['move_left_carry_1','1',-1],       
        '=':['move_left_carry_1','=',-1],       
        '#':['move_left_carry_1','#',-1],       
        '+':['move_left_carry_1_part_2','+',-1],       
    },
    'move_left_carry_0_part_2':
    {
        '0':['move_left_carry_0_part_2','0',-1],       
        '1':['move_left_carry_0_part_2','1',-1],
        '#':['mark_start_carry_0','#',1],
    },
    'move_left_carry_1_part_2':
    {
        '0':['move_left_carry_1_part_2','0',-1],       
        '1':['move_left_carry_1_part_2','1',-1],
        '#':['mark_start_carry_1','#',1],
    },
}

Its graph is included here for your convenience (click to enlarge):

And a sample run:


>>> mul = TM(TMBinaryAddReverse, ["halt"], [])
Initialing TM [The input must be of the form '1010+0010=' (i.e. in reversed binary notation, operands of same size padded with an extra 0). The output will look like '1010+0010=1110'.]...
>>> mul.run('1110+1100=',True)
                                  V
<mark_start_carry_0>          : ['1', '1', '1', '0', '+', '1', '1', '0', '0', '=', ' ']
                                       V
<sum_1>                       : ['#', '1', '1', '0', '+', '1', '1', '0', '0', '=', ' ']
                                            V
<sum_1>                       : ['#', '1', '1', '0', '+', '1', '1', '0', '0', '=', ' ']
                                                 V
<sum_1>                       : ['#', '1', '1', '0', '+', '1', '1', '0', '0', '=', ' ']
                                                      V
<sum_1>                       : ['#', '1', '1', '0', '+', '1', '1', '0', '0', '=', ' ']
                                                           V
<sum_1_get_next>              : ['#', '1', '1', '0', '+', '1', '1', '0', '0', '=', ' ']
                                                                V
<sum_2>                       : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', ' ']
                                                                     V
<sum_2>                       : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', ' ']
                                                                          V
<sum_2>                       : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', ' ']
                                                                               V
<sum_2>                       : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', ' ']
                                                                                    V
<write_2>                     : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', ' ']
                                                                               V
<move_left_carry_1>           : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                                                          V
<move_left_carry_1>           : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                                                     V
<move_left_carry_1>           : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                                                V
<move_left_carry_1>           : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                                           V
<move_left_carry_1>           : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                                      V
<move_left_carry_1>           : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                                 V
<move_left_carry_1_part_2>    : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                            V
<move_left_carry_1_part_2>    : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                       V
<move_left_carry_1_part_2>    : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                  V
<move_left_carry_1_part_2>    : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                       V
<mark_start_carry_1>          : ['#', '1', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                            V
<sum_2>                       : ['#', '#', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                                 V
<sum_2>                       : ['#', '#', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                                      V
<sum_2>                       : ['#', '#', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                                           V
<sum_2_get_next>              : ['#', '#', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                                                V
<sum_2_get_next>              : ['#', '#', '1', '0', '+', '#', '1', '0', '0', '=', '0']
                                                                     V
<sum_3>                       : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0']
                                                                          V
<sum_3>                       : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0']
                                                                               V
<sum_3>                       : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0']
                                                                                    V
<write_3>                     : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0']
                                                                                         V
<write_3>                     : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', ' ']
                                                                                    V
<move_left_carry_1>           : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                                               V
<move_left_carry_1>           : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                                          V
<move_left_carry_1>           : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                                     V
<move_left_carry_1>           : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                                V
<move_left_carry_1>           : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                           V
<move_left_carry_1>           : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                      V
<move_left_carry_1>           : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                 V
<move_left_carry_1_part_2>    : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                            V
<move_left_carry_1_part_2>    : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                       V
<move_left_carry_1_part_2>    : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                            V
<mark_start_carry_1>          : ['#', '#', '1', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                 V
<sum_2>                       : ['#', '#', '#', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                      V
<sum_2>                       : ['#', '#', '#', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                           V
<sum_2_get_next>              : ['#', '#', '#', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                                V
<sum_2_get_next>              : ['#', '#', '#', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                                     V
<sum_2_get_next>              : ['#', '#', '#', '0', '+', '#', '#', '0', '0', '=', '0', '1']
                                                                          V
<sum_2>                       : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1']
                                                                               V
<sum_2>                       : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1']
                                                                                    V
<write_2>                     : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1']
                                                                                         V
<write_2>                     : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1']
                                                                                              V
<write_2>                     : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', ' ']
                                                                                         V
<move_left_carry_1>           : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                                                    V
<move_left_carry_1>           : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                                               V
<move_left_carry_1>           : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                                          V
<move_left_carry_1>           : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                                     V
<move_left_carry_1>           : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                                V
<move_left_carry_1>           : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                           V
<move_left_carry_1>           : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                      V
<move_left_carry_1>           : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                 V
<move_left_carry_1_part_2>    : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                            V
<move_left_carry_1_part_2>    : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                 V
<mark_start_carry_1>          : ['#', '#', '#', '0', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                      V
<sum_1>                       : ['#', '#', '#', '#', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                           V
<sum_1_get_next>              : ['#', '#', '#', '#', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                                V
<sum_1_get_next>              : ['#', '#', '#', '#', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                                     V
<sum_1_get_next>              : ['#', '#', '#', '#', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                                          V
<sum_1_get_next>              : ['#', '#', '#', '#', '+', '#', '#', '#', '0', '=', '0', '1', '0']
                                                                               V
<sum_1>                       : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0']
                                                                                    V
<write_1>                     : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0']
                                                                                         V
<write_1>                     : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0']
                                                                                              V
<write_1>                     : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0']
                                                                                                   V
<write_1>                     : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', ' ']
                                                                                              V
<move_left_carry_0>           : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
                                                                                         V
<move_left_carry_0>           : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
                                                                                    V
<move_left_carry_0>           : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
                                                                               V
<move_left_carry_0>           : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
                                                                          V
<move_left_carry_0>           : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
                                                                     V
<move_left_carry_0>           : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
                                                                V
<move_left_carry_0>           : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
                                                           V
<move_left_carry_0>           : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
                                                      V
<move_left_carry_0>           : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
                                                 V
<move_left_carry_0_part_2>    : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
                                                      V
<mark_start_carry_0>          : ['#', '#', '#', '#', '+', '#', '#', '#', '#', '=', '0', '1', '0', '1']
####+####=0101
'accept'


I think this machine can be simplified by writing the carry directly to the tape (i.e. writing a ’0′, a ’1′ or a ’2′ to the result part of the tape, and later converting the ’2′s to ’1′ and ’0′ as appropriate).

If anyone of you manages to generate an equivalent machine with a shorter description (less states) please post it!