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.
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(log(N)) memory complexity.
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).
In this post I will define turing machines and demonstrate a simple one in action.