The complex behavior of simple machines

Abstract

This paper interprets work on understanding the actions of Turing machines operating on an initially blank tape. While this is impossible for arbitrary machines, complete characterizations of behavior are possible if the number of states is sufficiently constrained. The approach combines normalization to drastically reduce the number of machines considered, human-generated classification schemes, and computer-generated proofs of behavior. This approach can be applied to other computational systems, giving complete characterizations in sufficiently small domains. This is of interest in the area of emergent systems since the properties of such systems are often difficult to determine. By using computers to eliminate multitudes of machines with well understood behavior, some unanticipated exotic machines with complex behavior were discovered. These exotic machines show that it is quite difficult to estimate the number of states needed to produce a given behavior, and hence subjective estimates of complexity may be poor approximations of the true complexity.