Trajedy

Trajedy is a 2-dimensional language that involves a pointer moving through a square grid. Instructions in the grid may change the direction of the pointer or perform input/output. It is similar to Befunge in this way, except that the pointer moves continuously and non-orthogonal directions are possible. The instruction symbols ,./\ are similar to their counterparts in PATH.

Invented by Jafet (User:Jafetish) in 2017, Trajedy was conceived as an attempt to remove the memory stack from Befunge. Besides the finite grid and the pointer's own configuration, no other program memory is provided in Trajedy. This makes it quite difficult to store and manipulate data in a controlled way. Nevertheless, Trajedy is Turing-complete (proof sketch).

“Trajedy” is intended to be pronounced like the word “tragedy”.

Examples

The images link to (quite large) animations.

Hello, world! wH.H.e.l.l\ / w. .,.o./ \.o.r.l.d.!.
Infinite loop of beacons Y X X Y X
Truth-machine X Y ,?\Y X . / \ \/ 0\ Z . . 1 1 X Z
Cat program X Z /\$ Z  ? Y ,_/Y . Z Z \\ Q X I O \ Z	(one iteration only)
Reverse cat See #Stack example. The input is restricted to an alphabet of two characters only.

Specification

Syntax

A Trajedy program is written in lines of plain text. The official character encoding is UTF-8, but ASCII should be adequate for most programs. The text is split into lines and treated as a rectangle of characters, and spaces are appended to shorter lines to fill out the rectangle.

Note that newline characters are preserved, and padding spaces are added after the newlines.

Semantics

From now on the rectangle of characters will be referred to as the program area. The program area is divided into a grid of squares, with each unit square containing one character. The program pointer is a single moving point, and starts at the top-left corner of the top-left square, moving towards the bottom-right corner of that square. It keeps moving during the entire execution of the program.

(a) (b) (c)

When the pointer crosses the boundary of a square, it is said to enter a neighbouring square (a). If the pointer crosses a corner, it enters the square opposite to the square it came from (b).

The pointer is never allowed to move along the edges between squares (c). This is the no-edge rule.

If the pointer leaves the boundary of the program area, the program halts.

Entering a square

When the pointer enters a new square, it performs an action determined by that square's character, as well as whether the pointer is in a special mode. The initial mode of the pointer is the normal mode; the other modes are input, output and special-character.

When the program starts, the pointer is just about to enter the top-left square in normal mode.

Normal mode

If the pointer enters a square in normal mode, it performs an action depending on the square's character:

Character	Action
(space)	Nothing happens; the pointer continues on its path.
.	The pointer changes to output mode and will output from the next square.
,	The pointer changes to input mode and will input into the next square.
?	The pointer changes to special character mode. It will inspect the special character in the next square.
/ or \	A two-sided mirror between the appropriate corners of the square. If the pointer hits its surface, it reflects like a light ray. The pointer may reflect off the corners of mirrors, at the same angle (as if the mirror extends slightly past the corner). If the pointer is travelling on the same line as the mirror itself, its path is not changed.

Example of beacon interactions. The pointer turns towards the nearest point on any other beacon. The centre pointer (green) is unaffected because it is the same distance from both beacons.

For any other character in normal mode, the square is treated as a beacon. The pointer changes direction to move towards the nearest matching beacon; i.e. another square that contains the same character. More precisely, the pointer turns towards the nearest point, chosen from all the points on all matching beacons. If there is no unique nearest matching beacon, nothing happens.

Note that the pointer changes direction immediately, while it is still on the edge of the beacon being entered. If this causes it to move back towards the square that it came from, it will enter that square again.

If the nearest beacon is in a position that would cause the pointer to move along square edges, then the program has violated the no-edge rule and is considered invalid. (The reference implementation exits with a failure code.)

Input and output modes

The program can perform I/O when entering a square in input or output mode. (The normal behaviour of the square's character is ignored.)

• If the pointer is in input mode, the next character from program input is read and placed in the square. If there is no input available, an end-of-input marker is placed into the square instead. This marker is different from any other character and can be detected by entering the special character mode.

• If the pointer is in output mode, the square's character is output. If the square contains an end-of-input marker, no output happens (the marker does not correspond to any character).

Before entering the next square, the pointer returns to normal mode.

Special character mode

This mode allows the program to inspect input characters that happen to be one of the mode-switching characters (.,?), or the end-of-input marker.

If the current square has one of those characters, it is treated as a beacon for the corresponding character in the table:

Character	Beacon
.	I
,	O
?	Q
end of input	$

For other characters, the pointer's direction is unchanged. The pointer returns to normal mode before the next square.

Discussion

Implementation

The initial position and direction of the pointer, as well as all subsequent states, can be represented by Cartesian coordinates with rational numbers. Hence, Trajedy is implementable on a Turing machine.

The beacons are the only program elements to have non-local behaviour. Even this can be avoided by using, for example, Voronoi regions to pre-calculate the nearest beacon for every point. However, dynamic beacons (created in input mode) still entail non-local control flow.

Unicode

The language spec does not clearly describe how Unicode text should be handled.

The reference implementation has some basic support for Unicode, using codepoints (instead of characters).

The main rationale for Unicode is to not exclude programs that want a huge number of distinct beacons. However, if Unicode causes too many problems, it could potentially be dropped.

Infinitesimals

The pointer only needs to enter a square's (infinitesimally-thin) boundary to be affected by it. This leads to some physically unintuitive behaviour:

• In the following program, the pointer moves to the corner between the X beacons, then bounces between the beacons indefinitely. However, it does not move any nonzero distance.

X X

• Mirrors extend to the corners of their squares. However, the pointer must actually enter a mirror's square to be affected by it. Hence, pointers can “tunnel” between infinitesimally small gaps between mirrors:

/ /

The Turing-completeness construction relies heavily on this tunnelling artifact.

Newlines and padding

Each line is padded up to the width of the program area, but after the newline. This means that trailing whitespace is significant. A short source line will place a newline square away from the program area's right edge, and it can act as a beacon. Placing newlines this way is also the only way to output newlines without ending the program.

Control flow

A simple scheme for control flow is to constrain the pointer to move in orthogonal directions, i.e. parallel to the square edges. Orthogonal pointers remain orthogonal when reflected by mirrors; they also do not drift across rows or columns. A device for setting this up at the beginning of the program is:

XY … Y X

When designing an orthogonal-flowing program, beacons should be placed on the same row or column, and the pointer should be directed to beacon edges within that row or column. This preserves the orthogonal flow (or even resets a non-orthogonal pointer). The examples rely on this construction extensively.

Memory

All program memory (except for a few squares that store input characters) must be encoded into the pointer's state, one way or another. The pointer can easily enter an unbounded number of states from a finite program, like in this example:

XY AY A X

Below, we explain how a stack of bits could be simulated; this should be sufficient to implement any push-down automaton. While the known Turing-completeness proof uses a different memory representation, the stack-memory devices are still worth understanding because they are also used in that proof.

Storage

While a pointer may appear to have three rational-valued parameters (position and direction), only one is actually usable for persistent storage. Whenever the pointer hits a beacon (which is quite necessary for any kind of control flow), only the offset from the pointer to the beacon's corners is preserved; the two other parameters are lost.

So, let's refer to this offset as x, where 0<x<1 (see diagram). If we turn the pointer towards a beacon at distance (a, b), then redirect the pointer after it has travelled c squares, we can transform the offset x:

1. If c is along b: x → c(a+x)/b mod 1

1. If c is along a and x: x → b(c+x)/(a+x) mod 1

We will concentrate on the first transform, because the second one is messier to think about (it's not a simple affine function). Interesting special cases:

• a=0, b=2, c=1: x → x/2

• a=1, b=2, c=1: x → x/2 + 1/2

These let us selectively prepend a 0 or 1 bit to the binary digits of the offset x.

Retrieval

The previous devices tend to reduce x, which would make it difficult to read information back out. However, if we somehow take c>b, then we could increase x. In particular, if c=2b then we would multiply x by 2, into the range 0<x<2. Then, we could read the highest bit of x because it would span two distinct squares. Furthermore, the remaining bits would also be shifted up, effectively popping a bit off the stack.

One method is to abuse the fact that ? can be used to skip over instructions, allowing us to travel past the second beacon. This is shown below:

This abuse is inelegant, though; ? was intended to let programs inspect mode-switching characters, not to skip over squares. We can avoid ? by using a mirror to redirect the pointer before it hits the second beacon. The pointer will follow the same path, except with the x- and y-axes transposed:

Stack example

As a demonstration, the program below reads in a string of 0 and 1 characters, then prints the string in reverse. Note the transform used to pack bits (beacons named W) and the transform to unpack them (beacons named R).

X       / \
/ Y    ,_ /Y ← input loop
          
    X    W ← x' = x/2 + bit/2
\        /
         W10
        G ← prepare to merge; x' = x/2 + 1/2
            NB. merge device = GHIJ
       H
        
      G 
     /I/ ← begin merge; x' = 2x
   I   H
 / \  
      
      
      
      
      ← merged
   J
   R ← magnify x
   \      ⬐ now x' = -2x
   J       1.1 \ ← output
    R      0.0\ 
               \G  
              \g     ← alternative merge device
                  H   \H
                     gI
                    G \    
                              
                       I      J\J
 \                             /

Merging

Note that, after extracting the highest bit for output (at ← output), the two pointer paths need to be merged back again. (The program also needs to merge the input loop's exit path into the output loop.) We can construct a merging device from the same 2× multiplication device as before. The exit from the multiplier is non-orthogonal, which allows another orthogonal path to be inserted without a collision:

By adding a halving device before the multiplier, the merge will leave the pointer offset unchanged. In the example program, the halving beacons are GH and the doubling beacons are IJ.

Three dimensions

It is interesting, though useless, to note that a three-dimensional variant of Trajedy would easily be Turing-complete. The extra dimension would let us encode another stack and simulate a memory tape.

Computational class

Trajedy is Turing-complete, although it seems to be just barely so; here is a sketch of a reduction from Fractran. Note that this construction does not need to use ? either.

Recall that Fractran is a relatively simple language. To implement it, we only need:

1. Program state, which is some positive integer n. We represent it with a pointer offset of 1/n. (To keep the pointer offset less than 1 at all times, we can just pre-scale n by some large prime that is bigger than any intermediate value we need to deal with. For the following construction, the scaling factor should be at least 5 times the largest prime factor in the Fractran program.)
2. To divide the program state by fixed integers. We can use the multiplication device from before. Remember that we are storing the reciprocal of the Fractran state, so divisions become multiplications in Trajedy.
3. To multiply the program state by fixed integers. We can use the division transform from before.
4. To check if a division by a fixed prime number results in an integer. This can be solved using a zig-zag device, described in the next section.

Once we have these devices, we can implement any Fractran program as a big loop that tries each fraction in the program. For each fraction, we try dividing by each prime (with multiplicities) in the denominator. If any of them results in a non-integer (in other words, a pointer offset that is not an integer reciprocal), we restore the previous program state using multiplications, then try the next fraction. If all the divisions succeed, we then multiply by the numerator.

The zig-zag divisibility test

A zig-zag device is a tube made of facing mirrors, along with a pair of beacons to direct the pointer into the tube. Here is a simple zig-zag device (note that we will need a more complex version later):

↖/ (etc.) ↖/ /↘ (entry)→ A/ /↘ /↘ /↘ (outputs) A

By changing the pointer direction to almost-diagonal, we can bounce it within the tube, creating a zig-zag pattern, hence the name. The initial pointer offset determines the deviation from the diagonal direction vector (1, 1).

We can use zig-zag devices to create divisibility tests. The basic idea is that the pointer will reach one of the corners of the mirrors, and be able to escape through the infinitesimally small gap. For example, for x = 1/5, the pointer escapes past the first mirror:

For x = 2/5, the pointer escapes past the fourth mirror:

By “unfolding” the mirrors, we can see that the zig-zag mechanism adds the offset value on each bounce, until it reaches an escape point. Example for x = 1/3:

Hence, it implements a divisibility test using repeated addition. After the pointer leaves the tube, it still has the same (possibly reflected) direction that it started with. We can let it travel for a short distance to recover the initial offset x.

Corrected zig-zag test

Unfortunately, the simple zig-zag above does not work for all inputs. For example, if x = 6/7 the pointer only passes through interior corners and never escapes through the tube's sides. To avoid these unwanted “resonances”, we should set up the zig-zag to begin on the corner of the first mirror. This ensures that any potential resonance will include some corners of the mirror tube, and the pointer will always exit eventually.

This can be done by the following, more advanced gadget:

A \ (entry -->) A X / / / /X P / / /\Q P / / 1 P /\Q P / / 2\ Q P /\Q P / / 3\ Q P /\Q 4\ Q P etc.\ Q 4321 [ ] [ ] [ ] [ ] (output)

This gadget accepts an offset x = p/q (in lowest terms), where q is odd. For proper alignment, it also requires 0 < x ≤ 1/5. The A beacons first convert the offset p/q into the direction (-(q+p), q), then the X beacons move the pointer into the mirror tube with a direction of (q-p, q+p) = (1-p/q, 1+p/q).

With this direction, the pointer passes a p/q fraction of a mirror on each bounce, causing it to escape precisely after q bounces (as p and q have no common factors), i.e. after passing the p-th pair of mirrors. When q is odd, the pointer bounces an odd number of times and exits on the right side of the tube. (The gadget could be modified to accept even values of q, which escape on the left side, but we don't need to.)

Ultimately, we will get one output path for each possible denominator p. It is passed through an output gadget (PQ beacons) that restores the initial offset value. The sample path is for x = 2/11, hence it takes the output path labelled 2. The range of p can be extended by replicating the output gadgets and elongating the tube.

Now, we can use the zig-zag device to perform a Fractran step. First, we tentatively divide the Fractran state n by a fraction's denominator d, giving an offset x = d/n. We check if the reduced denominator is 1; if not, we multiply by d to restore the previous state. We can choose to check d with a single zig-zag test, or use a series of tests for each prime factor of d. The latter is more convenient, because we need a tube length proportional to d, and we need to provide one output path for every divisor of d. Splitting into primes minimises both.

Remember that the zig-zag device only handles offsets x ≤ 1/5, and only odd q. To ensure that q is odd, we can move the prime factors in the Fractran program around so that 2 is not used. To keep x small enough, we can pre-scale it by a prime that is at least 5*d, for the largest divisor d that we need to test.

Notes

Like most Fractran-based reductions, this involves encoding the input and output in unary. There may be a way to extend the earlier stack data structure to obtain Turing-completeness with non-encoded I/O, but this remains an open problem.

This construction actually allows branching based on the result of each test-and-multiply, whereas Fractran restricts the tests to a linear sequence. Thus, we could directly translate Minsky machines with arbitrary loops and jumps, while representing the counter state with Fractran's Gödel numbering as usual.

Corner tunnelling

The zig-zag device relies on the ability to tunnel the pointer through a corner gap between mirrors, which is quite unphysical and inelegant. Hence, Turing-completeness without mirror tunnelling is also an open problem. Conedy is a simplified variant of Trajedy that eschews mirrors entirely; its computational class is unknown.

If we don't want to use tunnelling, we'd need to let pointers that fail the divisibility test escape “freely” and be recovered within a constant distance. Unfortunately, the straightforward approaches do not seem to work; the pointer offset, at fixed distances from the escape region, loses information from the initial offset.

(Device:
→A/    
    E→/Escape
   /
    A)

Numer:    1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19
Denom:
    2:    0/2 
    3:    0/3   1/3 
    4:    0/4   0/4   2/4 
    5:    0/5   1/5   1/5   3/5 
    6:    0/6   0/6   0/6   2/6   4/6 
    7:    0/7   1/7   2/7   1/7   3/7   5/7 
    8:    0/8   0/8   1/8   0/8   2/8   4/8   6/8 
    9:    0/9   1/9   0/9   3/9   1/9   3/9   5/9   7/9 
   10:   0/10  0/10  2/10  2/10  0/10  2/10  4/10  6/10  8/10 
   11:   0/11  1/11  1/11  1/11  4/11  1/11  3/11  5/11  7/11  9/11 
   12:   0/12  0/12  0/12  0/12  3/12  0/12  2/12  4/12  6/12  8/12 10/12 
   13:   0/13  1/13  2/13  3/13  2/13  5/13  1/13  3/13  5/13  7/13  9/13 11/13 
   14:   0/14  0/14  1/14  2/14  1/14  4/14  0/14  2/14  4/14  6/14  8/14 10/14 12/14 
   15:   0/15  1/15  0/15  1/15  0/15  3/15  6/15  1/15  3/15  5/15  7/15  9/15 11/15 13/15 
   16:   0/16  0/16  2/16  0/16  4/16  2/16  5/16  0/16  2/16  4/16  6/16  8/16 10/16 12/16 14/16 
   17:   0/17  1/17  1/17  3/17  3/17  1/17  4/17  7/17  1/17  3/17  5/17  7/17  9/17 11/17 13/17 15/17 
   18:   0/18  0/18  0/18  2/18  2/18  0/18  3/18  6/18  0/18  2/18  4/18  6/18  8/18 10/18 12/18 14/18 16/18 
   19:   0/19  1/19  2/19  1/19  1/19  5/19  2/19  5/19  8/19  1/19  3/19  5/19  7/19  9/19 11/19 13/19 15/19 17/19 
   20:   0/20  0/20  1/20  0/20  0/20  4/20  1/20  4/20  7/20  0/20  2/20  4/20  6/20  8/20 10/20 12/20 14/20 16/20 18/20 

Table from initial to final offsets for a “free escape” version of the zig-zag device. The zeroes correctly identify exact divisions, but the other outputs follow no simple pattern. E.g. the outputs for n/11 are 0, 1, 1, 1, 4, 1, 3, 5, 7, 9.

Efficiency

Fractran is generally regarded as an inefficient computation system. Practical programs tend to get expanded exponentially when translating to a Minsky machine, then expanded again when translating to Fractran. This construction exacerbates matters further by expanding the travel exponentially: the zig-zag device moves the pointer by a distance proportional to the Fractran state n (hence exponential in the size of n). It seems unlikely that any programs will be run via this construction anytime soon.

Implementation

• Reference interpreter in C++, including the graphical debugger used to draw some of the images above.

See also

• Conedy