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

+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

+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

+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

+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).

+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

+* 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

+* 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.

+There are also any number of hills, each with a fixed position and radius.

+These serve as goals; when the leader hedgehog reaches a goal 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.

+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.

+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.

+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

+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.