  Since Cocke and Minsky proved 2-tag systems universal, they have been
extensively used to prove the universality of numerous computational models.
Unfortunately, all known algorithms give universal 2-tag systems that have a
large number of symbols. In this work, tag systems with only 2 symbols (the
minimum possible) are proved universal via an intricate construction showing
that they simulate cyclic tag systems. Our simulation algorithm has a
polynomial time overhead, and thus shows that binary tag systems simulate
Turing machines in polynomial time.
  We immediately find applications of our result. We reduce the halting problem
for binary tag systems to the Post correspondence problem for 4 pairs of words.
This improves on 7 pairs, the previous bound for undecidability in this
problem. Following our result, only the case for 3 pairs of words remains open,
as the problem is known to be decidable for 2 pairs. As a further application,
we find that the matrix mortality problem is undecidable for sets with five
$3\times 3$ matrices and for sets with two $15\times 15$ matrices. The previous
bounds for the undecidability in this problem was seven $3\times 3$ matrices
and two $ 21\times 21$ matrices.
