2-D Turing machine sequences

[Jonathan Post]

I'd like some feedback on a class of sequences I'm working on.  They are
generated by a (virtual)  2-dimensional Turing machine.  Let me start with
some involving prime factorization. All have, in common, a counter starting
with 1 (which becomes the n in the sequences), and a cursor (read/write
head) located in an initially blank square lattice, i.e. integer-valued
Cartesian space.

(device #1)

(1) start with cursor at origin, and count = 1.
(2) write the number where the cursor is.
(3) Add 1 to the counter.
(4) Find the prime factorization of the counter.
(5) If counter is prime, move cursor to first empty space to the Right, go
to statement (2).
(6) Else if counter is semiprime, move cursor to first empty space to the
Left, go to statement (2).
(7) Else move cursor Up to first empty space, go to statement (2).

Through n = 62 we have the following 2-D array of numbers produced:

__,__,58,57,56,59
__,__,__,__,55,54
__,__,__,__,52,53
__,__,__,__,51,50
__,__,__,__,__,49,48
__,__,__,__,46,45,47
__,__,__,__,__,44
__,__,__,__,42,43
__,__,__,40,41
__,__,__,39,38,36,37
__,__,__,__,__,35,34,33,32
__,__,__,__,__,__,__,30,31
__,__,__,__,__,__,28,29
__,__,__,__,__,__,27
__,__,__,__,__,__,26,25,24
__,__,__,__,__,22,21,20,23
__,__,__,__,__,__,18,19
__,__,__,__,__,16,17
__,__,__,__,__,15,14,12,13
__,__,__,__,10,09,08,11
6,4,01,02,03,05,07

This never moves Down.  It is not a random walk, but may be measured by
means typical of random walk theory.  One can ask approximately, and
asymptotically, what is the position of the cursor along the x and y axes at
time = n.  One can flatten it to the 1-D sequence of DistanceSquared from
origin a(n) = 0, 1, 4, 1, 9, 4, 16, 17, 10, 5, 26, 29, ... One can
differentiate to get velocity vector of the cursor.

One can project the shape to the sequence of number of values on nth row,
starting at row containing origin = b(n) = 7, 4, 4, 2, 2, 4, 3, 1, 2, 2, 4,
4, 2, 2, 1, 3, 2, 2, 2, 2, 4, ...

(device #2)

(1) start with cursor at origin, and count = 1.
(2) write the number where the cursor is.
(3) Add 1 to the counter.
(4) Find the prime factorization of the counter.
(5) If counter is prime, move cursor to first empty space to the Right, go
to statement (2).
(6) Else if counter is semiprime, move cursor to first empty space to the
Left, go to statement (2).
(7) Else if counter is 3-almost prime, move cursor Up to first empty space,
go to statement (2).
(8) Else (counter is k-almost prime for k>3) move cursor Down to first empty
space, go to statement (2).

By n = 55 we see:

__,__,__,__,__,__,30,31
__,__,__,__,__,28,29
__,__,__,__,__,27,22,21,20,23
__,__,__,__,52,26,25,18,19,24,53
__,__,__,55,51,50,15,14,13,54
__,__,__,__,__,10,09,08,11
46,06,04,01,02,03,05,07,45,47
__,__,__,__,__,__,49,16,17,44,48
__,__,__,__,42,35,34,33,32,43
__,__,__,39,38,36,37
__,__,__,40,41
__,__,58,57,56,59

Asymptotically, this moves mostly Down.  DistanceSqaured(n) =
0,1,4,1,9,4,16,17,10,5,26,29,40,20,13,10,17,25,34,41,32,29,52
where 17 is a fixed point.

This relates to the 2-D flow of control programminglanguage SNUSP, for which
definition, interpreter, compiler exist online.

I'll stop email here, before getting to the devices based on number of
distinct factors, and the class of devices that move R,L,U,D depending on
value mod 4 of sequences from OEIS, of which I first did a rigid example, a
silly example with length of english name of n, and some others.

This is a way of getting a 2-D graphic from almost any OEIS sequence.

I cannot easily show here some 3-D Turing machines I've played with.

My son has some clever questions about the inverse problem (inferring th
rules from the 2-D sequence), and what happens if one can overwrite or erase
(which lead quickly to noncomputable situations).

Any comments on this, and its suitability for OEIS, and some more citations?

Best,

Jonathan Vos Post
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20060929/91acf8d5/attachment-0001.htm>