Failing At A Bouncing Ball

Deutsche Zusammenfassung unten

After my last article I was so motivated and enthusiastic that I could understand difficult things few people could understand or care about at all but then last Friday at the day of Allerheiligen I wanted to cook some tea for my parents and used a different plant. The result was horrifying and I am happy we survived it.

So what did I want to show days ago

Well, I wanted to show a simple program in Thue which emulates a bouncing ball or a ball which bounces back over and over again between two walls.

The code is relative simple and I wanted to show that it stays that simple for Turing Machines and further for 2-tag systems.

Here's the Code in Thue:

#::=bouncing ball program
))O.::=.))O
.O((::=O((.
]O((.::=].))O
.))O[::=O((.[
::=
]...))O...[

Produces

]...))O...[
]....))O..[
].....))O.[
]......))O[
].....O((.[
]....O((..[
]...O((...[
]..O((....[
].O((.....[
]O((......[
].))O.....[
]..))O....[

over and over again ...

Then I tried to program it in a Turing Machine and fortunately there is a quite good implementation.

Here's the code:

 ; simulates a bouncing ball as in bouncingball.thue
; however D is ))O or ball going to the right while 
; C is O(( or ball going to the left 
; ] [ are the reflecting walls on which the ball bounces off
;
; Input : ]....D....[
; alternative Input: ]....C....[

; 0 has to be the initial state 


0 ] ] R 0
0 . . R 0
0 D . R D> 
0 C . L C> 
D> . D R Dx
D> [ [ L Dx 
D> C D R Dx 
Dx . . L Dx 
Dx D . R D> 
Dx [ [ L C>
C> D C L Cx
C> . C L Cx 
C> ] ] R Dx
Cx . . R Cx
Cx C . L C> 
Cx ] ] R D>

And finally here is how I failed at 2-tag systems

Although the Turing machine program turned out to be much bigger than I expected --- at least it just took me a couple of minutes to program it. It was a bit annoying
that I could only write one symbol at a time and only scan or read one but despite all of that it was quite an easy task.

So I first thought --- "geistige Umnachtung" as it is said in German --- that the 2-tag system program would be as easy as the Thue program but it turned out to be far worse ...

2-tag systems are so called because the first symbol is read then the first two symbols are erased and then according to the rule associated with the symbol, symbols are
added. There is only one direction and no way you can read two or more symbols.

Here's a sample of a 2-tag system:

rule: a->aac , initial input: aaa

Here's the output:

aaa
aaac
acaac
aacaac
caacaac

... and then it holds because there is no rule for symbol 'c'

Here are some of my failing attempts into programming the bouncing ball for 2-tag systems.

   ] -> ]. 
   . -> ..
   D -> .D
   [ -> [.

The initial input was similar to that in the Turing Machine Program.

I realized that symbols can get skipped and that this might be the clue in programming a 2-tag system and making it as powerful as a Turing Machine probably but I somehow did not get it.

Zusammenfassung

Begeistert von meinem letzten Artikel und in voller Euphorie wollte ich dann zeigen wie man eine Turingmaschine durch ein 2-Tag-System emuliert. Als Beispiel hatte ich vor ein einfaches Programm zu schreiben, dass einen Ball darstellt, der immer an einer von zwei Wänden abprallt. Fürs 2-Tag-System habe ich das bis heute nicht geschafft.