Registered: Jan 2008
Posts: 7

Greetings. I just had a course about Adaptive Finite Automata (AFA) during my post-graduate studies. One of our professors, João José Neto is very interested on the subject, and inspires us a lot to study it.

I developed a C++ simulator for AFAs that has its own peculiarities, and I tried to make a program space sweep, something similar to Wolfram's famous study on unidimensional binary CAs. I enumerated a class of "simple" programs and started to test each one of them, looking for interesting behaviour.

I did find machines with simple, trivial behaviours, then oscillators, and machines that could recognize series such as: multiples, triangular and square numbers, powers of two and other exponential expressions. (This means that the machines recognize the numbers from these series when you input them. Think of the input as numbers in unary representation.)

One of the machines had a behaviour that I could not find a closed arithmetical expression for it yet, and I thought some NKS fans out there might be interested in trying to "crack" it. I already posted about this machine at my blog in Nature Network. (There is also a portuguese version)

One way to look at the problem is defining a sort of transformational grammar that operates over a kind of circular string. You can also look at it as reading symbols from a LIFO stack, or perhaps using two FIFO stacks, choose your favourite. The alphabet is:

{F, G, o}

The rules are:
"o" -> "" (push "o")
"Fx" -> "oG" (push "F")
"Gx" -> "F" (push "o")

The initial state is:
"Foo"

The question is: what will be the size of the string at the Nth time you come full circle on the string? Or better, what will be the size at the Mth time you process a character? The picture below illustrates this automaton. (This is from my blog post where I tell the problem in a mythological fashion.)

http://img208.imageshack.us/img208/3682/saproid3.th.png

It seems there are only four possible patterns:
oGoo( N* Foo)F
oGo( N* Foo)F
Fo( N* Foo)
( N* Foo)

Here are the first strings that I calculated, their lengths, and the
pattern in abridged format:
1. 3: ( 1 Foo)
2. 5: oGoo( 0 Foo)F
3. 7: oGo(1 Foo)F
4. 10: oGo( 2 Foo)F
5. 14: Fo( 4 Foo)
6. 21: ( 7 Foo)
7. 32: oGoo( 9 Foo)F
8. 47: Fo( 15 Foo)
9. 71: oGoo( 22 Foo)F
10. 106: oGo( 34 Foo)F
11. 158: Fo( 52 Foo)
12. 237: ( 79 Foo)
13. 356: oGoo( 87 Foo)F
14. 533: Fo(177 Foo)
15. 800: oGoo(265 Foo)F
16. 1199: Fo(399 Foo)
17. 1799: oGoo(598 Foo)F
18. 2698: oGo(898 Foo)F


I believe we will end up finding some sort of formula based on successive multiplications and decisions based on modular arithmetic operations... Something not very different from a conventional pseudo-random generator based on

T=T*A%b+C

But what is the expression?

PS: I identified this behaviour as "complex" because when you apply the technique of calculating the successive differences of the series in many orders, you don't reach a constant (as with polynomial expressions) or an exponential series. It's something strange instead... I wonder if we can't perhaps map this problem to another famous chaotic system, I would be thrilled!...

Report this post to a moderator | IP: Logged

Registered: Nov 2007
Posts: 16

Actually, your system is simple:
As soon as the cyclic string begins with G, the system enters a cycle of length 3 which merely does the operation
"Gxy" -> "G" (push "oFo")

From this observation, you can certainly compute anything you want.

Report this post to a moderator | IP: Logged

Registered: Jan 2008
Posts: 7

Nice hint, thanks!

I also saw something like this too. I'm not quite sure, but I think you can just make:

"F**" -> "F" (push "Foo")

(where the * means any possible character, not two of the same)

Our simplifications (or perhaps "complifications"?) stack a lot of "oFo"s or "Foo"s, and that explains why the strings grow like "...ooFooFooFooFooFooF...". But as you said, this takes three steps. We are defining a sort of "internal state" here, and I want to predict this too.

The problem is to find a formula that says the next string size and what will be the next pattern each time we "come full circle", finishing to process the string and starting over again. In other words, given the start of the string (each "necklace" pattern) and the size of the "Foo" sequence, tell the next. I couldn't find it...

I believe it's some kind of mapping like: for each possible start (the 4 possible patterns), and depending on the value of the modulo of the number of "Foo"s for some base, calculate the number of "Foo"s somehow, and select the next pattern according to some rule.

The modulo thing is because I can't see a simple rule that maps the current pattern to the next one. If we label them 4, 3, 2 and 1, the sequence of patterns is:

1,4,3,3,2,1,4,2,4,3,2,1,4,2,4,2,4,3...

What I want to find out is a relation between this pattern change and the size of the "Foo" part. The hard part is not just understanding why it grows like this, but finding out exactly the size and pattern of the next necklace!... The point of the three steps that we stop at each iteration is also relevant.

PS: I like the "F**" simplification better (instead of the G one) because some times the necklace reaches a pattern (that I labeled 1) composed only by "Foo"s, with no "G"s, and starting at the "F". I tried to predict when those happen, but I still could not. First few cases are 1, 6 and 12, with sizes 3, 21 and 237...

And notice we always could "compute" whatever I want, but not however. The problem is the type of computation. I did compute the first 18 necklaces, but applying the rules directly. I want to find out whether there is a closed-form expression. The simple and classical pseudo-random generator I mentioned can be "computed", but not "predicted easily with a closed expression". Its recursion formula, tough, is quite simple. I couldn't even find a recursion formula to my problem yet...

__________________
Nicolau Werneck <nwerneck@gmail.com>
http://www.lti.pcs.usp.br/~nwerneck
9F99 25AB E47E 8724 2F71 EA40 DC23 42CE 6B76 B07F
"The purpose of computing is insight, not numbers." --- R. W. Hamming

Last edited by nwerneck on 01-29-2008 at 04:11 AM

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

I think RLamy's confusion is that the rules you wrote above are not the actual necklace problem rules you give in your blog.

He is correct that the rules you give, applying at the front of the string, just give a trivial cycle.

What you want instead is to read through the string making all the possible substitutions, ending with a new "single step" string.

But the rules as stated in words on your blog, are ambiguous. How the scan is supposed to handle the new insertions is vague, for example. (A next white is said to "count" as the next bead in that same application - but trivially, since whites are unchanged - but nothing is said about the last substitution, which is the one that could "recurse" within the "same" step).

As is the order of application of the rules (since some involve an "any after bead X" pattern, there are multiple ways they could be applied). Presumably it is meant to be a sequential scan - but the blog explicitly refers to an "end" and a "wrap" condition for the next time through, again ambiguous, since the head of the string from which the scan is to start on the next overall iteration, is unclear. Since the rules are positional (some beads ignored because of their predecessor), the scan will not produce the same string from different starting points.

What we actually need is a set of replacement rules that fully specifies the system. Then it would be trivial to implement it in Mathematica and investigate how it behaves etc. But there is no sense in us guessing which way you mean each of the ambiguities, since each makes a slightly different system.

Report this post to a moderator | IP: Logged

Registered: Jan 2008
Posts: 7

Thanks for the reply!

Sorry if I'm not being clear enough...

First of all, you must understand that the original problem was given in the adaptive finite automaton realm. It is a machine with two different adaptive functions and a single symbol. The program is the one I posted at my blog, but since that is written in a language that I invented myself for a simulator program that I wrote in C++, using a model that is not well-known, I decided to find another way to express the same problem.

The string must be processed character by character. It is not a proper transformational grammar where you can make any change at any time. The rules must be applied only to the top of a stack. Characters can be pushed at the bottom of the stack, and you can also change the values of the first few characters.

The difficulty is because there is a mark of "end of string" that must be followed. I'm interested in when this mark is reached and what is the size of the string / necklace each time this happens (what I call sometimes an "iteration", do not confuse with the "iteration" of each character processing) This mark is the red line in the picture I sent in the first message.

The mythical tale of the girl that picks up the necklace and builds a new necklace from it every year applying the rules to the beads that are taken out from the old necklace in sequence should be clear enough. You can't go on changing the colour of beads in the middle of the necklace.

I actually implemented a program in C using a list to show the problem. I'm uploading it attached. I would be glad if anyone could pass this program to Mathematica...

There is a character that marks the end of the necklace. It must be handled adequately... I also could not find a formula for the series given by the step where each old necklace is completely processed.

***
You don't need to understand the program to study the problem. Just give me a formula for this series, and I'll be satisfied. It is the series of the sizes of the necklaces, that I calculated for the first 18 cases

3, 5, 7, 10, 14, 21, 32, 47, 71, 106, 158, 237, 356, 533, 800, 1199, 1799, 2698, ...

Give me a"trivial" closed formula for this series and I'll be satisfied. I have found machines with "trivial" polynomial and exponential formulas. I could not find for this machine, tough.

For the curious, here are the successive differences of this series in increasing orders:


3 5 7 10 14 21 32 47 71 106 158 237 356 533 800 1199 1799 2698

2 2 3 4 7 11 15 24 35 52 79 119 177 267 399 600 899

0 1 1 3 4 4 9 11 17 27 40 58 90 132 201 299

1 0 2 1 0 5 2 6 10 13 18 32 42 69 98

-1 2 -1 -1 5 -3 4 4 3 5 14 10 27 29

3 -3 0 6 -8 7 0 -1 2 9 -4 17 2

-6 3 6 -14 15 -7 -1 3 7 -13 21 -15

It doesn't seem to me to be either a simple polynomial or exponential. If it is, or whatever closed formula it is, please, help me finding out what formula would that be.

You can't tell me this problem "trivial" and not present a formula to me. How is this trivial formula? Is there a simple exponential formula for this series, or what? A sum of a couple of exponentials and a pylonomial?...

Attachment: gramring.txt
This has been downloaded 895 time(s).

__________________
Nicolau Werneck <nwerneck@gmail.com>
http://www.lti.pcs.usp.br/~nwerneck
9F99 25AB E47E 8724 2F71 EA40 DC23 42CE 6B76 B07F
"The purpose of computing is insight, not numbers." --- R. W. Hamming

Report this post to a moderator | IP: Logged

Registered: Jan 2008
Posts: 7

The rules at my blog are:

"""
To each black pearl found in the old necklace, put it in the new necklace, and substitute the following stone by a haematite and a white pearl. (Notice this white pearl becomes the next bead to be counted.)

Each white pearl found must be immediately passed to the new necklace.

To each haematite found you must put a white pearl in the new necklace, discard the haematite, and replace the next bead in the old necklace by a black pearl.
"""

'F' is the black stone, 'o' the white and 'G' the haematite.

first rule:
"Fx" -> "oG" (push 'F')

The "(push F)" comes from the "put it in the new necklace". In "Fx", the "x" is the "following stone" being substituted. "oG" is the "haematite and a white pearl" that we are putting in place of the "following stone". Notice that in the text I say Haematite first because these stones are being pushed in the top of the necklace / string / stack.

Using '|' to denote the end of the necklace / string / stack, if we find "F|xabc", we then push F at the bottom, and substitute the x for oG. We end up with "|oGabc.......F". This happens at the image I uploaded in the very first post and in my blog between the 4th and 5th lines.

Second rule:
"o" -> "" (stack o)

"Each white pearl found must be immediately passed to the new necklace."

This one is simple... The 'o' is taken away, substituted by an empty string (""), and pushed at the bottom of the string.

Third rule:
"Gx" -> "F" (push "o")

"To each haematite found you must put a white pearl in the new necklace, discard the haematite, and replace the next bead in the old necklace by a black pearl."

This is just like the first rule. The G is turned intro a 'o' that is pushed, in the adaptive finite automaton this is just a relabelling of the transition. The 'x' then becomes an 'F'... This happens in the image between the third and fourth lines, where we have:

Go|Fo
F|Foo


I can't see why you said the rules I posted here differ from the rules in the website unless you only mean the confusion because I said it was "like a transformation grammar" when in fact it should more properly be understood as an automaton with two stacks.

***

I'm sorry if I'm sounding a little blunt in the last post and this one, but I'm a bit bothered that I wasn't able to express the problem properly... I tough that just saying that there is a rule to update the necklace bead by bead, depending on the colour of the top bead, and showing that picture of the necklace being updated step-by-step would be enough... Here is the first steps again in text:

(start of first necklace)
Foo|
oGo|F
Go|Fo
F|Foo
|oGooF

(start of second necklace)
oGooF|
GooF|o
FoF|oo
oGF|ooF
GF|ooFo
F|ooFoo
|oGoFooF

(start of third necklace)
oGoFooF|
GoFooF|o
FFooF|oo
...

Notice that both the "F**" and "G**" simplifications are valid. The problem is that we must account for the exact point in the three steps where the necklace ends. (When the '|' reaches the extreme left.)

If you look at the '|' character, it does seem that is moving in a quite regular fashion. But in the end, I still could not find a formula for the series I'm interested in.

I do believe that in the end we might just reach something simple, based on the modulus operator, similar to that traditional pseudo-random generator. I just couldn't find the formula yet!... I thought you might find it interesting to crack the system and find the formula, and not just dismiss the problem as "potentially trivial"...

__________________
Nicolau Werneck <nwerneck@gmail.com>
http://www.lti.pcs.usp.br/~nwerneck
9F99 25AB E47E 8724 2F71 EA40 DC23 42CE 6B76 B07F
"The purpose of computing is insight, not numbers." --- R. W. Hamming

Report this post to a moderator | IP: Logged

Registered: Nov 2007
Posts: 16

I read the blog but I was too lazy yesterday to tackle the full problem.

First though, the cyclic string case, i.e. ignoring the complications added by the end-of string marker. In Mathematica, it is specified by cyclicTransform = {{o, tail___} -> {tail, o}, 
{F, x_, tail___} -> {o, G, tail, F}, 
{G, x_, tail___} -> {F, tail, o}}.

I agree that it is clearer to use the F cycle, which goes {F, x, y, tail} -> {o, G, y, tail, F} -> {G, y, tail, F, o} ->{F,tail, F, o, o}. So in 3 steps, the second and third characters are eaten and "Foo" is added. Noticing that string length increases by one at the first step and is constant otherwise, this means that in the general case the length is lo+Quotient[t-t0,3] at step t (counting from 0), where l0 is the length of the initial string and t0 is -2, 0 or -1 depending on whether the initial string starts with 'F', 'oG' or 'G'.

Concerning the overall expression of the string, there is a period 9 cycle :
Foo(n*Foo) -> oGo(n*Foo)F -> Go(n*Foo)Fo ->F(n*Foo)Foo -> oGoo(n*Foo)F ->Goo(n*Foo)Fo -> Fo(n*Foo)Foo -> oGFoo(n*Foo)F ->GFoo(n*Foo)Fo ->Foo(n*Foo)Foo.

Now, all that remains to crack the full problem is to determine at which time the new string is produced. Since a string is produced only after an F or G step, it can only start with oG or F.

If it starts with F and its length is odd, the next string starts with F and is produced at t= 3(l-1)/2+1. If it is even, the next string starts with oG at t=3l/2.
If it starts with oG and length is even, the next string starts with F at t=3(l-2)/2 + 2. If length is odd, the next string starts with oG at t = 3(l-3)/2+3.

I'm tired, so I stop here, but I don't think there's much more work needed to obtain a recurrence relation based on congruences modulo 18.

Report this post to a moderator | IP: Logged

Registered: Nov 2007
Posts: 16

OK, let's finish this!

For any starting string that contains at least one 'F' or 'G', the system reaches the 9-cycle described above in at most 2 complete string scan. This justifies introducing a string index i = 9n + s, where s numbers the steps in the above-mentioned cycle. Note that whenever i is defined, and whatever the starting string, i(t) has the form i(t) = t - t0. When the starting string is "Foo", t0 = 0.

It is now possible to write an explicit function that relates the next string's index to the current one's. Its expression depends on i % 18. Calling i_n the index of the nth string and l_n its length, we have:
If i_n = 18m, l_n = 6m + 3 and i_n+1=27m + 4, l_n+1 = 9m + 5.
If i_n = 18m + 1, l_n = 6m+4 and i_n+1=27m + 6, l_n+1 = 9m + 5
If i_n = 18m + 4, l_n = 6m+5 and i_n+1=27m + 10, l_n = 9m + 7
If i_n = 18m + 6, l_n = 6m+5 and i_n+1=27m+13, l_n+1 = 9m+8
If i_n = 18m + 9, l_n = 6m+6 and i_n+1=27m +18, l_n= 9m + 9
If i_n = 18m+10, l_n = 6m+7 and i_n+1=27m + 19, l_n+1 = 9m + 10
If i_n = 18m+13, l_n = 6m+8 and i_n+1=27m + 24, l_n+1 = 9m + 11
If i_n = 18m+15, l_n = 6m+8 and i_n+1=27m+27, l_n+1 = 9m +12

The other cases cannot happen when starting with "Foo".

I don't think there's a closed form for i_n but it's easily computable and therefore "simple" in an NKS sense, though there may exist questions about it that are complex, like in Collatz conjecture. To give an example, that turns out to be easy, does it ever happen that the string is an even repetition of "Foo"s? Answer: yes, for the first time at t=46, when the string is (114932728*Foo).

Report this post to a moderator | IP: Logged

Registered: Jan 2008
Posts: 7

Nice! Thanks so much for your analysis. Now that is what I was talking about!... :) I owe you R$5,00 from the humble prize I launched at my blog, please give me your paypal account name. :]

I must confess I didn't quite followed your expressions, but the 9-step cycle is really the key to see what is going on in the system...

We can see the cycle paying attention to the two first characters in the string:

0 - 3: Fo o|
1 - 4: oG o|F
2 - 4: Go| Fo
3 - 4: F|F oo
4 - 5: oG ooF|
5 - 5: Go oF|o
6 - 5: Fo F|oo
7 - 6: oG F|ooF
8 - 6: GF| ooFo

9 - 6: F|o oFoo
10 - 7: oG oFooF|
11 - 7: Go FooF|o
12 - 7: FF ooF|oo
13 - 8: oG ooF|ooF
14 - 8: Go oF|ooFo
15 - 8: Fo F|ooFoo
16 - 9: oG F|ooFooF
17 - 9: GF| ooFooFo

But to calculate the number of steps and the length of the necklace at each "epoch", we only need to look out for two phenomena that have only 3-step periods, the increase of the string size, and the movement of the end-of-string (the knot of the necklace)

Below we have the position of the knot, the number of the iteration and the size of the necklace.

3 0 - 3: Foo|

3 1 - 4: oGo|F
2 2 - 4: Go|Fo
1 3 - 4: F|Foo

5 4 - 5: oGooF|
4 5 - 5: GooF|o
3 6 - 5: FoF|oo

3 7 - 6: oGF|ooF
2 8 - 6: GF|ooFo
1 9 - 6: F|ooFoo

7 10 - 7: oGoFooF|
6 11 - 7: GoFooF|o
5 12 - 7: FFooF|oo

5 13 - 8: oGooF|ooF
4 14 - 8: GooF|ooFo
3 15 - 8: FoF|ooFoo

3 16 - 9: oGF|ooFooF
2 17 - 9: GF|ooFooFo
1 18 - 9: F|ooFooFoo

10 19 - 10: oGoFooFooF|
9 20 - 10: GoFooFooF|o
8 21 - 10: FFooFooF|oo

8 22 - 11: oGooFooF|ooF
7 23 - 11: GooFooF|ooFo
6 24 - 11: FoFooF|ooFoo

6 25 - 12: oGFooF|ooFooF
5 26 - 12: GFooF|ooFooFo
4 27 - 12: FooF|ooFooFoo

4 28 - 13: oGoF|ooFooFooF
3 29 - 13: GoF|ooFooFooFo
2 30 - 13: FF|ooFooFooFoo

2 31 - 14: oG|ooFooFooFooF
1 32 - 14: G|ooFooFooFooFo
14 33 - 14: FoFooFooFooFoo|

14 34 - 15: oGFooFooFooFoo|F
13 35 - 15: GFooFooFooFoo|Fo
12 36 - 15: FooFooFooFoo|Foo


The length increases every n=1 mod 3. at the same time, the n=1 mod 3 are the iterations when the knot does NOT move towards us, because of the extra 'o' created by 'F'. That unless the knot is at position 1, in which case it immediately goes to the end of the necklace.

It turns out that this following simple (and probably sub-optimal) C++ program can calculate the series:

---8<----------------------
#include <iostream>
using namespace std;

int main () {
long unsigned int len=3, knot=3, n=0, k=0;
while (len< (long unsigned int) -1 ) {
if (len==knot) {
cout.width(3); cout << k++ << ": ";
cout.width(20); cout << n << "( ";
cout.width(1); cout << n%9 << " mod9) - ";
cout << len << endl; }

if (n%3==0) len++;
if (knot==1) {
knot = len;
} else if (n%3!=0 ) knot--;

n++;
}
return 0;
}
---8<----------------------

The output for the first 53 necklaces ("epochs") is attached. The format of it is: the number of the necklace, the number of iterations to get to it (n), n%9, which gives us the pattern of the necklace (according to the 9-step cycle), and the length.

We can see the interesting case you pointed out: the first (n*Foo) with even n. It even turns out that the next two necklaces have the same property.

The sizes come really close to an exponential series proportional to 1.5^n for larger values of n... I wonder if we can find a model to the series as an exponential plus some noise, and also a formula to the patterns. But these are other stories!... :)

Thanks again for your attention, I'll be at a workshop about Adaptive Finite Automata after tomorrow, and I'll talk about this machine (and others). I'll certainly mention the NKS forum and your contributions!...

Attachment: output_53.txt
This has been downloaded 843 time(s).

__________________
Nicolau Werneck <nwerneck@gmail.com>
http://www.lti.pcs.usp.br/~nwerneck
9F99 25AB E47E 8724 2F71 EA40 DC23 42CE 6B76 B07F
"The purpose of computing is insight, not numbers." --- R. W. Hamming

Report this post to a moderator | IP: Logged