[harshreality]

Is there any theorem that puts limits on how irregular the cycles can be in a general case of tape length L with N options corresponding to N outputs from each graph node?

What has to be constant is the cycle length for (node, tape instruction #) pairs, because all the state to determine every future step is based on the current node and tape position; if both are the same, the path will be the same as before. I think, at least without advanced math, the only thing to rely on for "true" loops is identical pairs of (instr #, node), not just instr # or tape steps or node individually.

[noxvilleza]

I haven't spent that much time thinking about it, but my guess is that there may or may not be:

* a "tail" -- some initial part of the path before you get into a true cycle (like the 002, 004 in the example above)

* an inner repeating cycle before you reach a node you've seen before.

In the case given |t| = 0 and |c| = 1, but it's easy to construct a more complex example with nodes (A, B, C, D), edges (A->B, B->C, C->D, D->B), and 'ending nodes' being B and D. In this case left and right paths go to the same node. This case would have a tail of length 1, and then the inner cycles would be of length {2, 1, 2, 1 ...}.

As a result, valid 'ending states' (Z-nodes) for this graph would be after {1, 3, 4, 6, 7, 9, 10, ...} steps.

[harshreality]

You can have an inner seemingly-repeating cycle by node, but not by (node, tape instr #) pair.

Initial tails are something they should've done, which would've foiled the naive "find the cycle lengths and use lcm" approach.