A sequence s(n)_(n≥0) is called k-automatic if s(n) is a finite-memory function of the base-k digits of n. This means that some computer with only finitely many possible states can compute s(n) for any n by reading the base-k digits of n one at a time (beginning with the least significant digit) and following a transition rule that specifies the next state of the computer as a function of both the current state and the current digit being read. Each possible state of the computer has an associated output value, and the result of the computation is the output value corresponding to the state of the computer after it has read the final digit. A computer of this kind is called an automaton, hence the name "automatic sequence."
展开▼
