Complexity Explorer Santa Fe Institute

Your progress is not being saved! Enroll now or log in to track your progress or submit homework.

Introduction to Renormalization

Lead instructor:


5.2 Irreversible Computations, Forgetful Computers and the Krohn-Rhodes Theorem » Quiz Solution

What is a semi-group?

A. a subset of a group's moves (of the things you can do to a normal creature)
B. a creature where some of the moves can not be universally "undone"
C. a creature with a move that takes it invariably to a unique internal state regardless of current state.
D. (B), with (C) as a special case.

Answer (D). A creature of type (C) has a reset move built in; but creatures like (B) are the more general case of systems with irreversible operations. These are called semi-groups. The Krohn-Rhodes theorem tells you that all creatures of type (B) have, in their hierarchical decomposition, a "reset" machine of like (C).