Today I had a weird dream about a kind of automata. Each automaton has a finite 2D grid wrapped around like a torus, formatted as a table. Execution starts in one cell. Each step it executes whatever is in the current cell, and in each cell there's a symbol and a numeric operator. In one variant the numeric part is said to be optional. The symbol can be "n" or "a", or some other letters that I don't remember. They are not arbitrary but have meanings.

If the symbol is "n", the numeric operator will rotate the current row or column by a number of cells like in a Rubik's cube(without changing the "execution pointer"). It's written like this: +1 for rotating a row to the right, -1 to the left (presumably other numbers are allowed too but I didn't see examples in my dream), $+\frac{1}{-}$ for rotating a column upwards, $-\frac{1}{-}$ for rotating downwards. There's no separate state apart from what's on the grid. I'm not sure what "a" means, but it may have meant rotating the whole grid in the given direction while keeping the execution cell position fixed. I saw an example in my dream with just one cell with "n" in it, described the the smallest automaton that doesn't do anything.

I didn't see any examples of explicit machine input or output. Maybe the input is encoded in the grid, or maybe it's designed to be interactive and the animation created by the moving cells is the intended output. I'm not sure if there's any way to halt/accept/reject in it.

Does this kind of automata happen to have a name? Is there any related research?

  • $\begingroup$ I don't completely understand your model, you could try to update the text to have a lower focus on the dream and a higher focus on the formal definition, if you want. However, I believe it is modeled by a Finite State Automaton (although a bit large), where you create every rotation as a separate state machine with the possibility of jumping around between them. $\endgroup$ – Pål GD May 12 '20 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.