  Given one or more uses of a classical channel, only a certain number of
messages can be transmitted with zero probability of error. The study of this
number and its asymptotic behaviour constitutes the field of classical
zero-error information theory, the quantum generalisation of which has started
to develop recently. We show that, given a single use of certain classical
channels, entangled states of a system shared by the sender and receiver can be
used to increase the number of (classical) messages which can be sent with no
chance of error. In particular, we show how to construct such a channel based
on any proof of the Bell-Kochen-Specker theorem. This is a new example of the
use of quantum effects to improve the performance of a classical task. We
investigate the connection between this phenomenon and that of
``pseudo-telepathy'' games. The use of generalised non-signalling correlations
to assist in this task is also considered. In this case, a particularly elegant
theory results and, remarkably, it is sometimes possible to transmit
information with zero-error using a channel with no unassisted zero-error
capacity.
