Zame

Zame is an automaton-like esoteric programming language conceived around January 2009 by Chris Pressey. In fact, it is the reason Etcha was designed. However, it was forgotten about after Etcha was released and the author moved on to other languages.

Structure

A Zame configuration consists of a well-formed two-dimensional maze. For the sake of concreteness, we'll use # to represent walls and ASCII space characters to represent passages. "Well-formed" means that the maze's width and height are both odd and both at least 3, and that spaces only occur at coordinates where both x and y are even, or one of x and y is even and the other odd and the space is adjacent to two other spaces. This implies that the outer edge of the maze consists entirely of walls. For example, this is a well-formed maze:

#######
# #   #
# ### #
# ### #
# ### #
#     #
#######

Execution

A Zame configuration evolves as follows.

1. Find all possible paths from the upper-left to the lower-right of the maze. If there are none, halt (we say the Zame configuration has "dead-ended".) If there is more than one, also halt (we say the Zame configuration has "frayed".)

2. Convert the path to a series of turns (depicted by L's and R's) by "reading" it from the upper-left to the lower-right. If this series is not of even length, remove the final turn from it.

3. Convert the series to an Etcha program by replacing, from front to back, subsequences of two turns with Etcha instructions:

LL -> [
LR -> +
RL -> >
RR -> ]

4. Execute the Etcha program. If the Etcha program is not well-formed (mismatched while/wend), halt (we say the Zame configuration has "croaked".) If the Etcha program fails to terminate, we say the Zame configuration has "fallen into a black hole". If the Etcha program does terminate, it results in a 2-dimensional drawing. Use that drawing as a new maze (where drawn pixels are walls and undrawn pixels are spaces.) If the resulting maze is not a well-formed maze, halt (we say the Zame configuration has "bought the farm".)

5. Go back to step 1, using the new maze.

Example

Take the following initial configuration:

#########
# #     #
# # # ###
#   #   #
### # # #
#   # # #
#########

The path from upper-left to lower-right is

X XXX
X X X
XXX XXX
      X
      X

which translates to the following series of turns

LLRRLR

which translates to the following Etcha program

[]+

which draws the following new maze

#

which is not a well-formed maze; this Zame configuration has bought the farm.

Open Questions

If the evolution of a given Zame configuration ultimately dead-ends, frays, croaks, falls into a black hole, or buys the farm, we call that configuration "doomed".

• Are there any Zame configurations that are not doomed? If so, find one; otherwise show that none exists. The obvious choice for such a configuration would be one that is a fixed point, i.e. a maze which generates an Etcha program that draws the same maze. There may not be any such configuration because of the fact that you can only turn left so many times before you have to turn right again, and vice versa, meaning you cannot encode an arbitrarily chosen sequence of Etcha instructions into a planar maze.

• Suppose we consider Zame to be, not a single automaton, but a family of automata, each with its own permutation mapping two turns to an Etcha instruction. The Zame we've described above is actually the member Zame(LL,LR,RL,RR) of this family; other members include Zame(RL,LL,RR,LR), and so forth (there are a finite number of them.) Are there any Zame configurations in any members of the Zame family that are not doomed? If so, find one; otherwise show that none exists.

• Suppose we consider the Zame "extended family": we allow subsequences of turns to be longer than two, and we allow subsequences of differing lengths to be used (with the longest subsequence matching the front of the sequence first.) So, for example, Zame(LRL,RLR,L,R) is a member of this family (there are an infinite number of them.) Are there any Zame configurations in any members of the Zame extended family that are not doomed? If so, find one; otherwise show that none exists.

The author is quite certain that the answer to the third question is "yes", because it's possible to concoct a mapping which allows arbitrary Etcha programs to be encoded as mazes; for example,

LRLLRR   -> [
LLRR     -> +
LLLRRR   -> >
LRLRLLRR -> ]

so that the following fragments can be pasted together to form a long horizontal maze:

  #####
  #   #
#:# #:#
# # # 
# # #
#   #
#####

for +,

    #####
    #   #
#:### #:#
#   # #
### # #
  #   #
  #####

for [,

  #######
  #     #
#:# ###:#
# #   #
# ### #
#     #
#######

for >, and

      #####
      #   #
#:##### #:#
#   ### #
### ### #
  #   # #
  ### # #
    #   #
    #####

for ]. However, it is still an interesting problem to actually exhibit the maze which produces itself via the Etcha program -- very similar to writing a quine, but a bit different.

Variations

A variation that might make this easier is if we just find the longest possible path inside the maze from the upper-left, instead of one which reaches a specific goal such as the bottom-right. This would eliminate dead-ending.

If we let the automaton be non-deterministic, that is if we find all possible paths through each maze, and follow up on each one, we eliminate both fraying and falling into a black hole.

These variations could of course just widen the Zame family, with the particular Zame described here being Zame(LL,LR,RL,RR,bottom-right-goal,deterministic).