Historical Note On The Definition of Tag System
The above definition differs from that of Post 1943, whose tag systems use no halting symbol, but rather halt only on the empty word, with the tag operation t being 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 be less than m symbols.
The above remark concerning the Turing-completeness of the set of m-tag systems, for any m > 1, applies also to these tag systems as originally defined by Post.
Read more about this topic: Tag System
Famous quotes containing the words historical, note, definition, tag and/or system:
“Quite apart from any conscious program, the great cultural historians have always been historical morphologists: seekers after the forms of life, thought, custom, knowledge, art.”
—Johan Huizinga (1872–1945)
“His ear is so sensitively attuned to the bugle note of history that he is often deaf to the more raucous clamour of contemporary life.”
—Aneurin Bevan (1897–1960)
“The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)
“I believe in the flesh and the appetites,
Seeing, hearing, feeling, are miracles, and each part and tag of me
is a miracle.
Divine am I inside and out, and I make holy whatever I touch or am touch’d from,
The scent of these arm-pits aroma finer than prayer,
This head more than churches, bibles, and all the creeds.”
—Walt Whitman (1819–1892)
“Whoever places his trust into a system will soon be without a home. While you are building your third story, the two lower ones have already been dismantled.”
—Franz Grillparzer (1791–1872)