Counter Machine Net Notation

From Esolang
Jump to navigation Jump to search

Counter Machine Net Notation (CMNN) is an esoretic (sic) notation for counter machines.

Inspired by the correction at User_talk:Salpynx/Minimal_TC_program_machines#Autopsy_is_TC and noting that in counter machine code like Counterfish#Copy_.28duplicate_and_add.29_a_prime_encoded_.27virtual.27_register, the bulk of the content is branch labels, suggesting the structure of such instruction-restricted programs is the interesting aspect, not a specific ordering of commands.

Description

A counter machine with n registers is represented in CMNN as a rooted directed minimally-labelled (multi)graph, having n vertex labels (colours) to represent the registers, and two distinct edge types.

Vertices cannot have an outdegree greater than 2. A vertex with outdegree = 0 is an end state or exit. There may be more than one end state. Analysing the effect of one or many end states is one of the goal of this notation. Vertices other than the single root may have any number of incoming edges.

In theory, a vertex can be connected to itself (loop), or connected to another vertex up to twice (including itself for a multi-loop). Analysing the effect of restricting these cases may be interesting.

Symbol Description
• Vertex, coloured to represent a particular register
/ True edge transition (default)
⌿ False edge transition (a crossed edge)
║ 'Next' restricted edge. More technically: edges forming a path which cannot contain ancestor vertices
  • The vertex colour (labelling) indicates which register is to be operated on.
  • The number of outgoing edges indicates which operation is to be performed. 1 = inc(r), 2 = dec(r)
  • The effect of the operation chooses the next edge transition. If the operation succeeded (i.e. the register was altered), follow the truthy edge /, else follow ⌿.

Notation is very flexible. CMNN does not mean to restrict notation to a character set, grid, or even a 2D plane. The above table suggests using forward and backslash { / , \ } for truthy edges and APL U+233F ⌿ and U+2340 ⍀ for the 'crossed' falsey edges. It is likely more practical to use a diagramming tool, or work directly with an abstract structure. Colour re-use could also be used to colour a truthy edge the same colour as the originating vertex, and the falsey transition a different colour. Using this scheme a 2 colour rooted directed multigraph with outdegrees <= 2 should represent a Turing complete system with effective instructions: { inc(r, z), dec(r, zTRUE, zFALSE) }.

Notes

There is some possibility of confusion with the notation: dec(r, zTRUE, zFALSE) -- what is being tested? It is not "Jump-if-zero", which the what the mnemonic and use of the single jump target jzdec(r, z) implies. Here I'm using the test "was the register altered?" as a default in order to keep the inc(r) transition notation consistent with the dec(r). This is in line with what Minsky uses in his 1961 paper: Ij1 is the target if r != 0 and a subtraction occurred (truthy on successful operation), and Ij2 as the alternate target if the register was already zero and the subtraction 'failed'. I'm not going to check all similar notations for consistency, but want to be clear here.

  • It is an error to encounter a vertex with two outgoing edges of the same type.
  • A vertex with no outgoing edges represents an end state.
  • A vertex with a single falsey edge also represents an end state. Theoretically that edge can't be travelled to reach the final vertex, which may be a problem as it introduces 'unreachable' vertices. These could be pruned in a normalisation stage since they represent the same thing as a vertex with no outgoing edges.
  • End nodes are NOPs, since they have no traversable edge to indicate an operation.

TODO:

  • Clarify root nodes. It seems reasonable to allow root nodes to have one or two outgoing edges and therefore represent either command, and also to allow arbitrarily many incoming edges to represent an jump back to the start... which hides their status as root nodes. Root nodes could be NOPs too, but that may have other implications. Unsure. Needs resolution.
  • It seems like NOP / unreachable edges must necessarily exist. An outgoing edge from a dec(r) vertex could trivially be constructed to never be selected. The edge needs to be there to give the vertex meaning, but the target is irrelevant, and could be anything -- a loop, or an entire unreachable sub-graph. A specific NOP would be clearer, but still wouldn't prevent the possibility of unclear, misleading, and unreachable structures. Not sure what to do about this.

Examples

inc(r, z) jzdec(r, z) dec(r, zTRUE, zFALSE) jdecnz(r, z) 
   •
   |
   z

  •
 / ⍀
•   z
 
     •
   /   ⍀
zTRUE  zFALSE

     •
    / ⍀
   z   •
dec(r) if(dec(r)) { b1 } else { b2 }; { b3 } while(dec(r)) { b1 }; { b2 } 
    •
   / \
   \ ⌿
    •

        •
       / ⍀
   {b1}   {b2}
       \ /
       {b3}

     __⦣|
    /   •
    \   |\
     {b1} \ 
          /
         ⌿
     {b2}
Autopsy INC DEC 
     __⦣|
    /   •
    | {Autopsy}  
    \___|

     •
    /• 
    \
     •

     •    <- r
    /•\   <- ?
    \  \
     • ⌿  <- r = (r + 1) % 4 
     •    <- r = (r + 1) % 4
Incdecisive Machine incjnz(r, z) dec(r) jdecnz(r, z) inc(r) 
    •
   ⌿ \
  •   •
  ║   |
  ║   •
  ║   |
  •   z

    •  
   ⫽ \
   ⑊ ⌿
    • 

     {incjnz}
      ⫽    \
   {dec}    z
     ║      |
     •    {dec}
            |
          {dec}
            |
            •

   {incjnz}
     ⑊ /
      •
bf: [ { b1 } ] { b2 } 
        |
        •    <- test if r == 0
      _⦣|\
     /  • \  <- inc(r)
    /   |  \
    \ {b1} |    NB:
     \__• /  <- Exit test. could be diff r.
        ┼⌿   (and possibly altered by {b1}
      {b2}    on every pass through)

See Also

External resources

Retrieved from "https://esolangs.org/w/index.php?title=Counter_Machine_Net_Notation&oldid=103427"