Programming With String Rewriting and Thue

in #programming2 years ago

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
Sort:  

Guten Tag,

Mein Name ist GermanBot und du hast von mir ein Upvote erhalten. Als UpvoteBot möchte ich dich und dein sehr schönen Beitrag unterstützen. Jeden Tag erscheint ein Voting Report um 19 Uhr, in dem dein Beitrag mit aufgelistet wird. In dem Voting Report kannst du auch vieles von mir erfahren, auch werden meine Unterstützer mit erwähnt. Schau mal bei mir vorbei, hier die Votings Reports. Mach weiter so, denn ich schaue öfter bei dir vorbei.

Euer GermanBot

Congratulations @mattgroening! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You published more than 60 posts. Your next target is to reach 70 posts.

You can view your badges on your Steem Board and compare to others on the Steem Ranking
If you no longer want to receive notifications, reply to this comment with the word STOP

To support your work, I also upvoted your post!

You can upvote this notification to help all Steem users. Learn how here!

Great work! Your post was selected for curation by one of @curangel's dedicated curators for its contribution to quality!

...unfortunately, it had to be excluded from curation because you recently bought a vote from a bid bot (minnowvotes).In our efforts to support #newsteem, authors who participate in vote buying are not eligible for our votes.

But don't worry. It only takes 7 days of not buying votes to be able to receive our vote again, so maybe one of your next posts will make it!

Take care and steem on!