Troupe

Troupe is an esolang designed by Chris Pressey on June 25, 2012, in Winnipeg, Canada.

The name of this esolang is Troupe in the UK and Canada and Australia, but in the USA, where they drop the "u" in words where it follows an "o", its name is Trope.

Part I. Hedgehogs

We have a troupe of hedgehogs. Each has a position, a colour (in the USA: color), a possible hedgehog to its left, and a possible hedgehog to its right. In this troupe, there is only one hedgehog which has no hedgehog to its left, and only one hedgehog which has no hedgehog to its right, and the following is true: for each hedgehog X, if Y is the hedgehog to X's right (resp. left), then X is the hedgehog to Y's left (resp. right). (i.e. the hedgehogs are in a line formation.)

For some hedgehog X, the hedgehog to X's left and the hedgehog to X's right are the neighbours (in the USA: neighbors) of X.

We may say that a hedgehog is "one of the hedgehogs to the left" (resp. "right") of some other hedgehog; the meaning of this should be evident — it is just the transitive closure of "to its left" (resp. right).

All hedgehogs share a fixed speed at which they move (when they move), and a fixed radius. Also, the troupe consists of a finite number of hedgehogs at all times, and their colours come from a finite set of possible colours that can be distinguished from one another. (And that there is one distinguished "default" colour, which we will arbitrarily call "white".)

In the troupe, at any given time, there is either exactly one leader hedgehog, or exactly one leader-elect hedgehog; never both and never neither.

The leader hedgehog, when it exists, has a velocity. It moves through space with this velocity, changing its position. All other hedgehogs in the troupe try to "follow" it, which means the following:

Each hedgehog moves to minimize the distance between it and one of its neighbours (up to a certain point: if the distance between it and its neighbour is less than three times the hedgehog radius, it does not bother to move at all.)

The neighbour it moves toward is the hedgehog on its left (resp. right), if the leader is one of the hedgehogs to the left (resp. right).

Part II. Faery Rings

We also have a set of faery rings. Each ring has a fixed position, radius, inner colour, and outer colour; it optionally has a signpost, a unit vector pointing in any direction; and it optionally has an orientation, which is either clockwise or counterclockwise.

Faery rings may not intersect each other except if both rings have precisely the same position and radius and if they have different outer colours. (They may have the same inner colour.)

When a leader hedgehog intersects a faery ring (i.e. when the distance between the hedgehog is less than the sum of the hedgehog radius and the particular ring's radius), and if the outer colour of the faery ring is the same as the colour of the leader hedgehog, the following things happen, in this order:

• The faery ring, and all faery rings which intersect it, become temporarily inactive, in that intersection with a hedgehog does not set off this same sequence of events until it becomes active again.

• The leader hedgehog's colour is changed to the inner colour of the faery ring.

• If the faery ring has a counterclockwise (resp. clockwise) orientation, then the hedgehog to the leader hedgehog's left (resp. right) becomes the leader-elect hedgehog.

  (If there is no hedgehog to the left (resp. right) of the leader hedgehog, then one pops into existence, at the same position as the leader hedgehog, and with a white colouring; and it becomes the leader-elect hedgehog.)

  When the set of hedgehogs has a leader-elect, the leader-elect moves to minimize its distance to the faery ring that made it leader-elect, and all other hedgehogs follow the leader-elect, as described above.

  Once the leader-elect hedgehog intersects the faery ring which made it the leader-elect (which it will eventually, as it moves to minimize the distance), it becomes the leader hedgehog.

• If the faery ring has a signpost, the leader hedgehog is given a velocity in accordance with the direction of the signpost.

• Once the leader hedgehog no longer intersects the faery ring, the faery ring, and all rings that it intersects, become active once again.

Part III. Hills

There are also any number of hills, each with a fixed position and radius. These serve as goals; when the leader hedgehog reaches a hill, the troupe's quest is over, and they are free to break formation and nibble on clover or whatever it is that hedgehogs do for fun.

Part IV. Computational Class

The system outlined above should be Turing-complete, as it maps quite readily to the definition of a Turing machine.

The line of hedgehogs serves as the tape, with their colours being symbols on the tape, and the leader being the tape head.

The faery rings implement state transition rules, or rather, the parts of transition rules that say "If the symbol on the tape is..." (which in our system translates to "If the leader hedgehog is coloured...") Overlapped faery rings of all possible colours make for a traditional transition rule.

The state itself is encoded by the leader's position and velocity and which faery ring they're headed toward next. As long as the faery rings are arranged appropriately, we can guarantee that, when the leader hedgehog leaves a faery ring, possibly with a new velocity, it is bound to intersect another faery ring eventually. An example of an appropriate arrangement is:

• The signpost in each faery ring points in a cardinal direction.

• All faery rings have the same radius.

• For each faery ring, there is another faery ring which shares at least one of its coordinates.

Finally, the hills serve as halt states.

Part V. Extras

We can certainly allow for the presence of elements in this world which either do not affect the property of being Turing-complete, or if they do, are not required to be present in any particular instance of the world.

Rest Areas

A rest area has a fixed position and radius.

If the leader hedgehog enters a rest area, it does not move until no hedgehog in the troupe is impelled to move (i.e. until all hedgehogs are within three times the hedgehog-radius of another hedgehog.) This allows the troupe to "catch up" with the leader.

Part VI. Discussion

This system is, of course, crying out to be implemented with a visual animation of the hedgehogs moving around, possibly in a Java applet, or in an HTML5 canvas with Javascript.

We have not specified the dimensionality of the space in which these things exist; certainly, two dimensions would be a reasonable restriction, especially for an animated visual implementation.

The system probably continues to be Turing-complete in one dimension, but I have not convinced myself of that. One of the things that allows this (if it is true) is that hedgehogs are happily allowed to pass right through other hedgehogs as if they didn't exist. If this was not true, then a one- dimensional realization of this world is probably not Turing-complete.

In two dimensions, however, even if hedgehogs are not allowed to pass through each other, the system is still Turing-complete (cf. Beturing), although we might have to add one proviso. Since, in order to really be Turing-complete, the troupe of hedgehogs needs to be able to grow without bound, it might become intractably large. When the leader hedgehog is not able to make progress because of some other hedgehog in its way, it should act as if it entered a rest area. Also, we may require some "jitter" be introduced in follower hedgehog movements, lest they get stuck.

We may want to go further, and allow the space itself to expand whenever a hedgehog is added to the troupe — so long as all the relative directions between things are preserved, this should not affect the outcome.

(The idea for this system came to me sort of all at once when I was thinking about Beturing, specifically that Beturing doesn't address the tape at all in its concerns about wire-crossing. I mean, don't we have to communicate to the tape somehow, and might not those lines of communicate cross other lines of communication? Then I thought, well, it can assume that the tape is inside the state pointer somehow. And the rest followed more-or-less naturally.)

We have not specified, either, whether this system should be implemented with a discrete simulation or a continuous simulation. Actually, either should work, I think; and a continuous simulation would be somewhat interesting, if only for the fact that most language interpreters are discrete. A continuous simulation would use real numbers to measure both duration and distance, and real analysis techniques to discover the evolution of the system. Motion of the hedgehogs would be genuinely continuous except for the points where their velocities change due to one hedgehog approaching another too closely, etc.

Nor have we said much about the topology of the space all of these things are in. Naturally, the space could be infinite, or it could be mapped onto a torus so that the hedgehogs "wrap around" at the edges. (The fact that the space is finite is not a problem w.r.t. Turing-completeness, so long as there are still an infinite number of possible coordinates, i.e. the space of real or rational numbers; integers, though, would be problematic in a space of finite extent.) Or the space could be mapped onto the surface of a sphere, with appropriate modifications.

We have also not constrained the sets of faery rings and hills to be finite; so we could have an infinite number of them in an infinite space — but for correspondence with a Turing machine, these should probably be restricted to infinite sets. (Otherwise, if you have, say, an uncountable set of faery rings, specified non-constructively, you could encode all possible computations just in them, and the behaviour of the hedgehogs becomes essentially moot.)

The initial condition could either consist of the troupe having a leader hedgehog with an initial velocity, or a leader-elect hedgehog with an initially-selected faery ring to which it is attracted. The former is probably more "natural" for some definition of "natural".