Programming With String Rewriting and Thue

Programmieren durch Zeichenkettenersetzung

deutsche Zusammenfassung unten

The String-Rewriting Theorem is easily understood although actually programming something in it might be quite difficult.

However by understanding state and something I call travelling one may easily succeed to even program a Universal Turing Machine or an Interpreter.

Today I have programmed a sample programm in the esoteric language Thue. In the appendix I have given the full code but as many lines are just there to allow 'travelling' I gave an explanation of the Code first which makes the whole thing less verbous and easier to read and to understand.

The programm can be run by copying the code into the Thue Interpreter. I recommend running it in debugging mode as this highly improves the understanding.

A sample programm which compares to numbers

There are to numbers A and B in the sample programm. I set the numbers to xoox and xoox in the programm but you can change the last line and set the numbers to values you prefer.

The last line looks like this :

@A-xoox..B-xoox

The current digit to compare is marked with a - .
The programm uses following travelling states which travel to the right : @ X O O! X!
Only the state R is travelling left or backward until it reaches A and then everything starts again with the initial state @ .

When @ comes into contact with x or o it changes to X or O or in other words it remembers whether it touched x or o.
The next digit is marked with - . Here are the relevant instructions:

@-x::=x-X
@-o::=o-O

Upon reaching B or the number to compare with X and O change to X! and O! .

The actual comparisons is done with the following commands or string replacements.

X!-o::=--different--
X!-x::=x-R
O!-o::=o-R
O!-x::=--different--
@-.::=--equal--

In case the digit has been the same it returns to the next digit in the first number which has been marked with - . Otherwise it can already show the resulft --different-- .

Zusammenfassung

Der Artikel beschreibt recht ausführlich wie man anhand des Zeichenersetzungstheorems oder "String-Rewriting" zwei binäre Zahlen vergleichen kann. Das detailiert beschriebene Programm ist bei Weitem nicht sparsam mit den verwendeten Zuständen noch ist ausgesprochen kurz.

Mehr Informationen dazu finden sich im Esolang-Wiki oder auf diversen Webseiten.

Appendix

#::=comparing two sequences
#::=skipping or travelling rules just for moving forward
@A::=A@
@B::=B@
@x::=x@
@o::=o@
X.::=.X
Xx::=xX
Xo::=oX
O.::=.O
O;::=;O
Ox::=xO
Oo::=oO
#::=travelling with O! and X! 
O!x::=xO!
O!o::=oO!
X!x::=xX!
X!o::=oX!
#::=travelling back when in R state 
xR::=Rx
oR::=Ro
-R::=R-
AR::=@A
BR::=RB
.R::=R.
#::=comparing
#::=memorizing digit (either x or o) and marking next digit
@-x::=x-X
@-o::=o-O
#::=upon reaching next sequence to compare
XB::=BX!
OB::=BO!
#::=comparing digit
X!-o::=--different--
X!-x::=x-R
O!-o::=o-R
O!-x::=--different--
@-.::=--equal--
::=
@A-xoox..B-xoox