collatz similarity to Turing Machine

hi all this is not a spectacular finding but it is the latest, seems interesting, and my last collatz post is starting to runneth over.

earlier there was some examination of the comparison of msb’s of 3n where n is the number of 3x+1 operations and the trajectory iterate and showed a remarkable correspondence, basically a correlation between them expressed/ tracked by a “plateau metric”. this analysis builds on that and wonders about how the plateau metric oscillates. the plateau metric moves “left or right” depending on the boundary between matching and unmatching msbs. but notice it never moved more than about ~10 increments at a time.

this is some different code that computes the plateau metric change locally instead of globally. its kind of a long story to explain so will not go into detail at this time. the code generates long glides and then computes the changing plateau metric within a local neighborhood “d” (line 67) and halts if there is a discrepancy with the globally computed metric (line 54). for d=20 there is never any discrepancy for a long search space as follows (more than ~1.5K seeds/ trajectories) because all delta adjustments occur in 18 (binary) digits or less. this code outputs the # of trials to generate unique trajectories, the # of unique trajectories, current glide length, current trajectory length, current max delta, overall max delta, and the ratio of unique trajectories vs trials. the last few lines of an output before manually terminating are listed below.

the plateau metric moves locally back and forth somewhat reminiscent of the way a TM head does on a tape. in this case the “tape” is continually changing on the “right/ lsb” side and unchanging on the “left/ msb” side. this dynamic seems to have similarities with tag systems and one wonders if there could be some stronger correspondence. while this suffices for now, there is presumably a more clever/ more efficient way to generate unique new trajectories than this declining-to-~50% throwaway scheme eg by partial seeds avoiding Hamming-distance matches with prior seeds etc.

from some examination the longer delta adjustments tend to happen with the familiar iterate lsb 1-runs, as those analyzed in the prior post. looking back on that it did not seem to try to look at max length of lsb 1-runs in “hard seeds” (long glides/ trajectories), now something of an omission in retrospect and maybe something to look into sometime—ie if the delta max is limited, and seems to tie in with the max lsb 1-runs, could maybe the max lsb 1-run lengths be limited somehow also? (although it did show long trajectories can start with arbitrarily long lsb 1-runs.) as the expr goes “not sure how all this fits together right now.”

addendum: the 1-runs are not actually the lsb of the full iterate but are embedded within the delta-size local “window”. the delta value can be computed looking within this “window”. as observed earlier & here, the plateau metric has a random walk similar to the iterate bit-length random walk.

plateau.rb

...
[3079, 1557, 100, 131, -7, -18, 0.505683663527119]
[3080, 1558, 117, 147, -5, -18, 0.505844155844156]
[3094, 1559, 106, 111, -7, -18, 0.50387847446671]
[3095, 1560, 141, 153, -7, -18, 0.504038772213247]
[3097, 1561, 104, 141, -5, -18, 0.504036164029706]
[3099, 1562, 179, 199, -8, -18, 0.504033559212649]
[3101, 1563, 129, 143, -7, -18, 0.504030957755563]
[3102, 1564, 138, 143, -10, -18, 0.504190844616377]
[3104, 1565, 135, 158, -5, -18, 0.504188144329897]
./plateaub:112:in `long': Interrupt
from ./plateaub:149:in `sort_by'
from ./plateaub:112:in `long'
from ./plateaub:111:in `long'
from ./plateaub:140
from ./plateaub:138

(9/26) 💡 ❗ ❓ 😮 😳 further thought, was thinking this over some more & had a wild idea last night that again am amazed have not thought of before, it seems so utterly obvious in retrospect. imagine the operation “3n” only. it creates a sort of convolution function over the bits in the string. but as just observed last night with a simple experiment, it is a generally local computation. this can be determined in the following way. truncate some of the lsb of a number n say called n2 and also compute 3n2 and compare it with 3n. the msbs match! now, what can one do with this simple factoid, how can it be exploited? it generally helps the idea that the plateau delta can be computed locally only looking within the window. need to code that variant/ idea up soon.

(9/27) this effect is striking and easy to replicate but here is some simple code to exhibit/ demonstrate it. it generates 1000 bit random numbers and truncates up to half of the lsb randomly determined, and then determines the # of matching bits of the msb between 3n1 and the truncated 3n2. as seen its strongly linearly correlated with some small “noise” offset on top. somehow this “effect” must be interrelating with the plateau metric but not sure how it meshes right now.

mult.rb

image

Advertisements

4 thoughts on “collatz similarity to Turing Machine

    1. vznvzn Post author

      yes am planning to blog on Tao’s recent breakthrough re EDP. there is some superficial similarity with my inquiries into collatz etc. it all falls roughly under “finding structure in apparent random walks based on inherent pseudorandomness”. think there may be some deeper unifying theory to eg automated thm proving & we are only seeing tips of icebergs right now.

      Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s