The paper demonstrates how algorithmic information theory can be elegantly used as a powerful tool for analyzing the dynamics in connectionist systems. It is shown that simple structures of connectionist systems-even if they are very large-are unable significantly to ease the problem of learning complex functions. Also, the development of new learning algorithms would not essentially change this situation. Lower and upper bounds are given for the number of examples needed to learn complex concepts. The bounds are proved with respect to the notion of probably approximately correct learning. It is proposed to use algorithmic information theory for further studies on network dynamics.