An Inefficient Representation of the Empty Word

Asveld, P.R.J. (1996) An Inefficient Representation of the Empty Word. In: A Dynamic and Quick Intellect -- Paul Vitanyi 25 years @ CWI. CWI, Amsterdam, pp. 11-18.

Preview

PDF
70Kb

Abstract:	We show that Post's system of tag with alphabet $\{0,1\}$ , deletion number 3, productions $0\rightarrow 00$ and $1\rightarrow 1101$ , and initial string $111\cdots 1$ (330 times) converges to the empty word after a very large number of rewriting steps.
Item Type:	Book Section
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:	http://purl.utwente.nl/publications/66564
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page