THE BUSY BEAVER GAME

RADO, TIBOR.

On Non-Computable Functions (Contained in The Bell System Technical Journal, volume 41, number 3, pp.877-884).

N.Y., 1962.

Entire issue in wrappers.

First publication of Rado's highly influential paper, in which he describes the Busy Beaver Game. The present paper - one of the most important results within theoretical computer science - deals with the existence of non computable functions.

"The busy beaver game, originally posed by Rado in 1962, is a problem in which the challenge is to construct a Touring machine on a given number of states and symbols that prints a maximal number of ones, or alternatively executes a maximal number left/right shifts, and subsequently halts. Although the problem is simple to state and its solutions are finite and well-defined, determination of actual values are readily shown to be non-computable." (Teuscher, Proceedings of the 2005 Workshop on Unconventional Computing, p. 89.)

Order-nr.: 26104