出典:Wikipedia
出典:『Wikipedia』 (2011/06/29 18:40 UTC 版)
A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine (not to be confused with Post-Turing machines)—briefly, a finite state machine whose only tape is a FIFO queue of unbounded length, such that in each transition the machine reads the symbol at the head of the queue, deletes a fixed number of symbols from the head, and to the tail appends a symbol-string preassigned to the deleted symbol. (Because all of the indicated operations are performed in each transition, a tag machine strictly has only one state.)