SUPERIOR INFORMATION IS INSUFFICIENT TO WIN IN GAMES BETWEEN FINITE AUTOMATA

A game between two computers is considered: the first computer generat es a binary sequence while the second one tries to predict the next el ement of this sequence using the previous elements. Both computers ope rate with the same pool of strategies, which is the set of all boolean functions of N arguments. Notwithstanding the asymmetry of the game, it turns out that the value of the game is zero. An algorithm for choo sing an optimal superstrategy for the first computer is proposed, and several generalizations of the game are considered.