Fwd: Several more 2-D Turing machines (#3, #4, #5); Re: 2-D Turing machine sequences

[Jonathan Post]

---------- Forwarded message ----------
From: jonathan post <jvospost2 at yahoo.com>
Date: Oct 1, 2006 10:40 AM
Subject: Several more 2-D Turing machines (#3, #4, #5); Re: 2-D Turing
machine sequences
To: Jonathan Post <jvospost3 at gmail.com>
Cc: jvospost2 at yahoo.com, andrewpost at gmail.com

(device #3)

(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 [what
matters here is the number of DISTINCT prime factors,
omega(n)].
(5) If omega(n) = 1 [counter is prime or a prime
power], move cursor to first empty space to the Right,
go to statement (2).
(6) Else if omega(n) = 2 [counter is product of two
primes or prime powers], move cursor to first empty
space to the Left, go to statement (2).
(7) Else if omega(n) = 3 [counter is of form p^a q^b
r^c, p, q, r prime], move cursor Up to first empty
space, go to statement (2).
(8) Else if omega(n) > 3 move cursor Down to first
empty space, go to statement (2).

By n = 50 we see:

row 1:

28,_26,_24,_22,_21,_20,_18,_15,_14,_12,_10,_06,_01,_02,_03,_04,_05,_07,_08,_09,_11,_13,_16,_17,_19,_23,_25,_27,_29

row 2 (above row 1, 40 above 13):

40,_39,_38,_36,_35,_34,_33,_30,_31,_32,_37,_41

row 3 (above row 2, 42 above 41):

50,_48,_46,_45,_44,_42,_43,_47,_49

========

Device #4

The first of several where we take f(n) mod 4 for
various f(n).  We start with the simplest:

(1) start with cursor at origin, and count = 1.
(2) write the number where the cursor is.
(3) Add 1 to the counter.
(4) divide counter by 4, consider remainder (n mod
4).
(5) if 0 mod 4, move cursor Down to first empty
space, go to statement (2).
(6) if 1 mod 4, move cursor Right to first empty
space, go to statement (2).
(7) if 2 mod 4, move cursor Left to first empty
space, go to statement (2).
(8) if 3 mod 4, move cursor Up to first empty space,
go to statement (2).

This is crystalline:

_______________03
____________07_02_01
_________11_06_04_05
______15_10_08_09
___19_14_12_13
23_18_16_17

the pattern is:

____n+3
n+7_n+2__n_n+1
n+6_n+4_n+5
n+8

so reading from left to right, top to bottom, we have
this permutation of the natural numbers:
3, 7, 2, 1, 11, 6, 4, 5, 15, 10, 8, 9, 19, 14, 12, 13,
23, 18, 16, 17, 27, 22, 20, 21, 31, 26, 24, 25, 35,
30, ...

========

Device #5

where we take f(n) mod 4 for f(n) = number of letters
in English name of n.

(1) start with cursor at origin, and count = 1.
(2) write the number n = counter where the cursor is.
(3) Add 1 to the counter.
(4) Calculate f(n) = number of letters in English
name of n.
(5) Find r = f(n) mod 4.
(6) if r = 0 move cursor Down to first empty space,
go to statement (2).
(7) if r = 1, move cursor Right to first empty space,
go to statement (2).
(8) if r = 2, move cursor Left to first empty space,
go to statement (2).
(9) if r = 3, move cursor Up to first empty space, go
to statement (2).

After n = 44, we see:

________________________39_38_40
___________________________37_41
___16_17_______43_35_34_33_36_42_44
___15_18____30_29_28_31_32
___12_11_10_______27
25_06_07_08_24_23_26
20_02_03
___01_04
______05
______13
______14

========

Next email, we'll see

Device #6, naturally mod 4, which graphs the minimum
number of nonnegative squares needed to sum to n

========

--- Jonathan Post <jvospost3 at gmail.com> wrote:

> 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/20061001/8cbd4ef5/attachment-0001.htm>