  We discuss the conceptually different definitions used for the
non-Markovianity of classical and quantum processes. The well-established
definition for non-Markovianity of a classical stochastic process represents a
condition on the Kolmogorov hierarchy of the n-point joint probability
distributions. Since this definition cannot be transferred to the quantum
regime, quantum non-Markovianity has recently been defined and quantified in
terms of the underlying quantum dynamical map, using either its divisibility
properties or the behavior of the trace distance between pairs of initial
states. Here, we investigate and compare these definitions and their relations
to the classical notion of non-Markovianity by employing a large class of
non-Markovian processes, known as semi-Markov processes, which admit a natural
extension to the quantum case. A number of specific physical examples is
constructed which allow to study the basic features of the classical and the
quantum definitions and to evaluate explicitly the measures for quantum
non-Markovianity. Our results clearly demonstrate several fundamental
distinctions between the classical and the quantum notion of non-Markovianity,
as well as between the various quantum measures for non-Markovianity.
