<br><br>---------- Forwarded message ----------<br><span class="gmail_quote">From: <b class="gmail_sendername">jonathan post</b> <<a href="mailto:jvospost2@yahoo.com">jvospost2@yahoo.com</a>><br>Date: Oct 1, 2006 10:40 AM

<br>Subject: Several more 2-D Turing machines (#3, #4, #5); Re: 2-D Turing machine sequences<br>To: Jonathan Post <<a href="mailto:jvospost3@gmail.com">jvospost3@gmail.com</a>><br>Cc: <a href="mailto:jvospost2@yahoo.com">

jvospost2@yahoo.com</a>, <a href="mailto:andrewpost@gmail.com">andrewpost@gmail.com</a> (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.

<br>(4) Find the prime factorization of the counter [what<br>matters here is the number of DISTINCT prime factors,<br>omega(n)].<br>(5) If omega(n) = 1 [counter is prime or a prime<br>power], move cursor to first empty space to the Right,

<br>go to statement (2).<br>(6) Else if omega(n) = 2 [counter is product of two<br>primes or prime powers], move cursor to first empty<br>space to the Left, go to statement (2).<br>(7) Else if omega(n) = 3 [counter is of form p^a q^b

<br>r^c, p, q, r prime], move cursor Up to first empty<br>space, go to statement (2).<br>(8) Else if omega(n) > 3 move cursor Down to first<br>empty space, go to statement (2).<br><br>By n = 50 we see:<br><br>row 1:<br>

<br>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<br><br>row 2 (above row 1, 40 above 13):<br><br>40,_39,_38,_36,_35,_34,_33,_30,_31,_32,_37,_41<br><br>

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.

<br>(2) write the number where the cursor is.<br>(3) Add 1 to the counter.<br>(4) divide counter by 4, consider remainder (n mod<br>4).<br>(5) if 0 mod 4, move cursor Down to first empty<br>space, go to statement (2).<br>

(6) if 1 mod 4, move cursor Right to first empty<br>space, go to statement (2).<br>(7) if 2 mod 4, move cursor Left to first empty<br>space, go to statement (2).<br>(8) if 3 mod 4, move cursor Up to first empty space,<br>

go to statement (2).<br><br>This is crystalline:<br><br>_______________03<br>____________07_02_01<br>_________11_06_04_05<br>______15_10_08_09<br>___19_14_12_13<br>23_18_16_17<br><br>the pattern is:<br><br>____n+3<br>n+7_n+2__n_n+1

<br>n+6_n+4_n+5<br>n+8<br><br>so reading from left to right, top to bottom, we have<br>this permutation of the natural numbers:<br>3, 7, 2, 1, 11, 6, 4, 5, 15, 10, 8, 9, 19, 14, 12, 13,<br>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.

<br>(3) Add 1 to the counter.<br>(4) Calculate f(n) = number of letters in English<br>name of n.<br>(5) Find r = f(n) mod 4.<br>(6) if r = 0 move cursor Down to first empty space,<br>go to statement (2).<br>(7) if r = 1, move cursor Right to first empty space,

<br>go to statement (2).<br>(8) if r = 2, move cursor Left to first empty space,<br>go to statement (2).<br>(9) if r = 3, move cursor Up to first empty space, go<br>to statement (2).<br><br>After n = 44, we see:<br><br>________________________39_38_40

<br>___________________________37_41<br>___16_17_______43_35_34_33_36_42_44<br>___15_18____30_29_28_31_32<br>___12_11_10_______27<br>25_06_07_08_24_23_26<br>20_02_03<br>___01_04<br>______05<br>______13<br>______14<br><br>

========<br><br>Next email, we'll see<br><br>Device #6, naturally mod 4, which graphs the minimum<br>number of nonnegative squares needed to sum to n<br><br>========<br><br>--- Jonathan Post <<a href="mailto:jvospost3@gmail.com">

jvospost3@gmail.com</a>> wrote:<br><br>> I'd like some feedback on a class of sequences I'm<br>> working on.  They are<br>> generated by a (virtual)  2-dimensional Turing<br>> machine.  Let me start with<br>

> some involving prime factorization. All have, in<br>> common, a counter starting<br>> with 1 (which becomes the n in the sequences), and a<br>> cursor (read/write<br>> head) located in an initially blank square lattice,

<br>> i.e. integer-valued<br>> Cartesian space.<br>><br>> (device #1)<br>><br>> (1) start with cursor at origin, and count = 1.<br>> (2) write the number where the cursor is.<br>> (3) Add 1 to the counter.

<br>> (4) Find the prime factorization of the counter.<br>> (5) If counter is prime, move cursor to first empty<br>> space to the Right, go<br>> to statement (2).<br>> (6) Else if counter is semiprime, move cursor to

<br>> first empty space to the<br>> Left, go to statement (2).<br>> (7) Else move cursor Up to first empty space, go to<br>> statement (2).<br>><br>> Through n = 62 we have the following 2-D array of<br>

> numbers produced:<br>><br>> __,__,58,57,56,59<br>> __,__,__,__,55,54<br>> __,__,__,__,52,53<br>> __,__,__,__,51,50<br>> __,__,__,__,__,49,48<br>> __,__,__,__,46,45,47<br>> __,__,__,__,__,44<br>

> __,__,__,__,42,43<br>> __,__,__,40,41<br>> __,__,__,39,38,36,37<br>> __,__,__,__,__,35,34,33,32<br>> __,__,__,__,__,__,__,30,31<br>> __,__,__,__,__,__,28,29<br>> __,__,__,__,__,__,27<br>> __,__,__,__,__,__,26,25,24

<br>> __,__,__,__,__,22,21,20,23<br>> __,__,__,__,__,__,18,19<br>> __,__,__,__,__,16,17<br>> __,__,__,__,__,15,14,12,13<br>> __,__,__,__,10,09,08,11<br>> 6,4,01,02,03,05,07<br>><br>> This never moves Down.  It is not a random walk, but

<br>> may be measured by<br>> means typical of random walk theory.  One can ask<br>> approximately, and<br>> asymptotically, what is the position of the cursor<br>> along the x and y axes at<br>> time = n.  One can flatten it to the 1-D sequence of

<br>> DistanceSquared from<br>> origin a(n) = 0, 1, 4, 1, 9, 4, 16, 17, 10, 5, 26,<br>> 29, ... One can<br>> differentiate to get velocity vector of the cursor.<br>><br>> One can project the shape to the sequence of number

<br>> of values on nth row,<br>> starting at row containing origin = b(n) = 7, 4, 4,<br>> 2, 2, 4, 3, 1, 2, 2, 4,<br>> 4, 2, 2, 1, 3, 2, 2, 2, 2, 4, ...<br>><br>> (device #2)<br>><br>> (1) start with cursor at origin, and count = 1.

<br>> (2) write the number where the cursor is.<br>> (3) Add 1 to the counter.<br>> (4) Find the prime factorization of the counter.<br>> (5) If counter is prime, move cursor to first empty<br>> space to the Right, go

<br>> to statement (2).<br>> (6) Else if counter is semiprime, move cursor to<br>> first empty space to the<br>> Left, go to statement (2).<br>> (7) Else if counter is 3-almost prime, move cursor<br>> Up to first empty space,

<br>> go to statement (2).<br>> (8) Else (counter is k-almost prime for k>3) move<br>> cursor Down to first empty<br>> space, go to statement (2).<br>><br>> By n = 55 we see:<br>><br>> __,__,__,__,__,__,30,31

<br>> __,__,__,__,__,28,29<br>> __,__,__,__,__,27,22,21,20,23<br>> __,__,__,__,52,26,25,18,19,24,53<br>> __,__,__,55,51,50,15,14,13,54<br>> __,__,__,__,__,10,09,08,11<br>> 46,06,04,01,02,03,05,07,45,47<br>

> __,__,__,__,__,__,49,16,17,44,48<br>> __,__,__,__,42,35,34,33,32,43<br>> __,__,__,39,38,36,37<br>> __,__,__,40,41<br>> __,__,58,57,56,59<br>><br>> Asymptotically, this moves mostly Down.<br>> 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.

<br>><br>> I'll stop email here, before getting to the devices<br>> based on number of<br>> distinct factors, and the class of devices that move<br>> R,L,U,D depending on<br>> value mod 4 of sequences from OEIS, of which I first

<br>> did a rigid example, a<br>> silly example with length of english name of n, and<br>> some others.<br>><br>> This is a way of getting a 2-D graphic from almost<br>> any OEIS sequence.<br>><br>> 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).

<br>><br>> Any comments on this, and its suitability for OEIS,<br>> and some more citations?<br>><br>> Best,<br>><br>> Jonathan Vos Post<br>><br><br>