tag-system.c

A small (quick, dirty, inefficient) C program to emulate Post tag systems.

See http://en.wikipedia.org/wiki/Tag_system. We use Post's original definition (1943), whose tag systems use no halting symbol, but rather halt only on the empty word, and the tag operation t is defined as follows:

If x denotes the leftmost symbol of a nonempty word S, then t(S) is the operation consisting of first appending the word P(x) to the right end of S, and then deleting the leftmost m symbols of the result - deleting all if there are less than m symbols.

Download

Some Tag System Descriptions

Some Generated Traces


Last modified: 2007-11-23