Challenge - Loop with brain

[simsim314]

I'm offering a 25$ Award (I've won for this solution: viewtopic.php?p=13652#p13652), for the first one who will build a "Loop" rule with the following properties:

1. Universal Contruction arm (i.e. that has operations: Push + Pull + Turn Left & Right + Construct X). Any other UC design is acceptable but universality is a must. This includes self deleting mechanism as well.

2. Can contain quadratic or more DNA "information" per it's wall length. For reference see this explanation:

viewtopic.php?p=11852#p11852

And exponential loop rule:
viewtopic.php?p=12280#p12280

3. Has a brain i.e. a universal calculation, which is used by the "DNA" not used for copy operation, to make "decisions" and change itself, and it's inner state by some logic. It's also important that the calculation would be performed "inside" of its boundaries, and that the decisions could influence the copy commands as well (the size of the loop can grow for example).

4. In addition to prove the concept is working in real life implementation, design a loop that:
Will copy itself to the right only once, after copying itself it will know it's "index" (number of the place in a row of such loops), and will delete itself if it's not prime. The loops should grow bigger as their index is growing, i.e. it will add one to it's current state, make decision of the loop size that will be needed to contain the current index, and will contain a mechanism that determines whether the current index is prime or not. The size of the loop should be "optimized" (i.e. not always growing by one, but always "calculated" according to the loop storage capacity).

5. Provide an explanation of how the loop is working. This is to allow others to use this rule, and understand its states. There is no need in very detailed explanation, just some basic explanation to allow further development.

[dvgrn]

4. In addition to prove the concept is working in real life implementation, design a loop that:
Will copy itself to the right only once, after copying itself it will know it's "index" (number of the place in a row of such loops), and will delete itself if it's not prime.

This is certainly an ambitious spec for a loop rule! Loops for the most part have been exercises in minimizing complexity as much as possible, but now suddenly this loop has to be able to sustain a significant amount of logic circuitry...

The loops should grow bigger as their index is growing, i.e. it will add one to it's current state, make decision of the loop size that will be needed to contain the current index, and will contain a mechanism that determines whether the current index is prime or not. The size of the loop should be "optimized" (i.e. not always growing by one, but always "calculated" according to the loop storage capacity).

... up to and including a log-base-N calculation the current index, as well as a primality test -- ouch! Anyone who completes this project would certainly earn their $25.

It seems tempting to implement something like this in an existing rule where we already know how to do logic circuitry. So what makes a rule a loop rule, or what makes a loop a loop? I can see how a static tape, along the lines of the Nobili-Pesavento machine and many others along those lines, would disqualify a pattern from being a "loop" (where the data circulates instead of sitting still.)

But what about, let's say, a redesigned Golly/Patterns/JvN/Boustrophedon-replicator.rle? This would be a pattern that works in the Hutton32 rule to circulate data in some kind of (heavily folded) loop, and then uses that data to build calculation circuitry and propagate an incremented index value to the next copy of itself -- probably modifying its own data slightly whenever a size increase became necessary. Would that then count as a "loop rule", or am I missing an important part of the definition?

[simsim314]

Hi dvgrn, and thanks for the clarification comment:

what makes a loop a loop

I mean "loop" in wider sense - circulating "data", while the circulation is on the boundary, and the "data analysis and manipulation" is inside it (in geometrical sense). This definition is straight forward: I expect the moving particles to be "outside" of the convex hull (probably some rectangle) and the logic parts to be "inside" the data stream, except of a single "exit point" for commands that control the construction arm. For example the current replicator in Hutton 32 is not a loop, because the interpretation unit is placed outside the circulating data, but probably can be made a loop pretty easily. It's also fine to have some "special" boundaries or reflection particles on the "outside", as long as their only function is supporting the data stream, and can be considered part of the stream. I hope this was clear enough.

This is important detail - because I want each loop to have well defined rectangular boundaries (this is why i call them "loops"). This small detail can allow further development of this rule into some sort of game I hope.

including a log-base-N calculation the current index

Not necessary log-base representation, you could simply add another "particle". This detail was mainly placed to make sure the size should be calculated and not "automatically added". This will show the logic part can manipulate the construction commands as well (and not some rule/construction tricks). One can use a quadratic estimator, and add single particle per index if it helps, but the loop size should grow at least as O(Sqrt(N)) and not O(N).

along the lines of the Nobili-Pesavento machine...a redesigned Boustrophedon-replicator

The technical implementation of a primer is kinda the trick here. If you manage to redesign some existing rule to make a loop, and primer calculator, and you think it's the simplest way to do so - you welcome. My guess is that the existing approaches are very complex, and implementing primer inside of the currently existing rules is much harder than creating a simple and elegant rule that will do that (something like WireWorld+GaucherLoop). My point is the current rules have too much states and too complex to implement even something simple as primer, so if you implement a primer - you either have too much free time, or you have thought it through and found a simple and elegant rule in which a primer is piece of cake. I hope for the second, this is why the first one who will do this wins - my hopes are for something clever and elegant.

NOTE You can use "steady states" as well and as few particles as you wish. As long as the "flow of the information" is on the borders as well. If some elegant steady state rules is coming up, making a loop from it is pretty simple, just go around in rectangle for construction commands - it's very simple addition.

[dvgrn]

I mean "loop" in wider sense - circulating "data", while the circulation is on the boundary, and the "data analysis and manipulation" is inside it (in geometrical sense). This definition is straight forward: I expect the moving particles to be "outside" of the convex hull (probably some rectangle) and the logic parts to be "inside" the data stream, except of a single "exit point" for commands that control the construction arm.

In general I can understand the logic-inside, data-outside idea, but I'm a bit worried about engineering the exit point so that the data can keep circulating but the construction arm can still operate. I immediately start thinking about some kind of double-walled loop going (almost) all the way around the outside -- inside in one direction, and no doubt through a large 2D folded area, and then around the very outside in the other direction. Is that cheating?

Another angle for maybe the same question: classic loops (Shapeloop and NovoLoop being recent examples) naturally return to their initial configuration after a while, just because the data loops around and gets to the same place. If any child loops are removed, these loops will cheerfully keep trying to do the same replication cycle over and over. Is that what you're looking for with this challenge also -- no net internal change in state after the data has completed one cycle of the loop?

If so, this would seem to imply that as replication continues, a lot of loops with composite index numbers are going to be getting continually constructed and re-constructed by the prime loops in the series. Or is it okay if a loop simply shuts down, stops trying to make (index+1) descendant copies, after it has made its initial copy and successfully tested itself for primality?

Not necessary log-base representation, you could simply add another "particle". This detail was mainly placed to make sure the size should be calculated and not "automatically added". This will show the logic part can manipulate the construction commands as well (and not some rule/construction tricks). One can use a quadratic estimator, and add single particle per index if it helps, but the loop size should grow at least as O(Sqrt(N)) and not O(N).

Hmm... okay, then, suppose each loop passes along to its descendant

• a list of all loop indices that have been found to be prime so far, and
• for each prime P in the list, the value of index-mod-P as of the last loop (easily incremented by one while making the new copy.)

That's a lot more information than just the index number in log-base representation, but even if the prime list is sent in unary, I suppose it could be folded up into something less than O(N) size. Would that be cheating?

[simsim314]

Or is it okay if a loop simply shuts down, stops trying to make (index+1) descendant copies, after it has made its initial copy and successfully tested itself for primality

Well this detail is ill formulated but let me elaborate. The loop should be able in general perform any long calculation as it wishes and still "survive" afterwards (be able to make the same calculation again), it should not in general "mess totally its brain after calculation". Think of primality test as decision - after you make a decision you should be able in general to make another decision, i.e. the brain should remain functional. But if it's not a limitation of the rule, and making it non functional simplifies your life a lot, it's also accepted solution. Just notice that if you mess up the brain after calculation you will need to show that this is just limitation of current implementation and not of the way the calculations are made inside the rule. So the best way to go here in my opinion, is to continue making sure the loop has prime index, again and again while circulating (after the copy).

Think of a loop as part of some complex universe in which it would required to make complex decisions again and again using its brain.

but even if the prime list is sent in unary, I suppose it could be folded up into something less than O(N) size.

This is all legit. As long as you calculate the size of the newly born loop, and not just increase it's boundaries size with some replication trick, but use logic for that purpose its all accepted. Less than O(N) should be a rule of thumb. There is also no need in optimizations of this sort - there is no request for primality test to be optimal or fast, it could be done very slowly. Instead of saving all primes, one can divide by all numbers from 2 to N, and it will suffice.

. I immediately start thinking about some kind of double-walled loop going (almost) all the way around the outside -- inside in one direction, and no doubt through a large 2D folded area, and then around the very outside in the other direction. Is that cheating?

I'm not sure what you mean. If I understand you, it would be cool if the copy operation will be inside the boundaries of the parent loop. But it's not a must - the request is to circulate, and the only exit point is for the construction arm as in every existing loop rule. Remove the construction commands stream, and you'll get a closed boundaries loop. You can make circulation in every way you like, cheat as much as you want, as long as the boundaries contain a circulating particle, and the boundaries grow sub-linearly it's all fine. Think of it as kind of fence that you're making to define your borders, it could be just a formality.

---

Another detail about cheating - no special states for primality check. The primality check should be done using states from the universal computing unit. That been said, it's fine to add states to simplify algebraic operations (kind of ALU).

[Tezcatlipoca]

Exciting! You should post a bitcoin address to hold the bounty and let all us interested parties contribute.

[fluffykitty]

(I've won for this solution: viewtopic.php?p=13652#p13652)

That's a LFOD spaceship...?

[praosylen]

(I've won for this solution: viewtopic.php?p=13652#p13652)

That's a LFOD spaceship...?

viewtopic.php?p=12513#p12513

[fluffykitty]

Ohh. So it's a solution to a different bounty. Makes sense