# collatz monotone estimator found?

last installment ended looking at the “forward/ lookahead trend” concept. heres a presumably stronger optimization/ test building on that idea using the hybrid system whipped off fairly quickly. the idea here is that the ~200 step lookahead function seems to be monotone (last bitwise experiment suggested max nonmonotone length is around ~200) and it would be useful to try to verify that as rigorously as possible. this calculates the ratio of the lookahead function at 200 steps fwd vs the initial point as ‘fr’ lightblue line and tries to maximize it along with the other trajectory metrics with no limit on starting iterate size. its indeed bounded very close to less than 1. there is one outlier point greater than one at about nl=235 bit size, but the fr vs nl graph seems to show a ceiling.

so awhile back the search was for a monotone predictor/ estimator of trajectory length and this fwd/ lookahead function seems to come very close. its computed in terms of collatz iterations yet is computable. it makes some kind of sense that a/ “the” predictor would be expressible in terms of the function itself.

earlier ideas were that possibly any sufficiently “solid” monotone predictor could somehow be converted into a proof. the ideas are related to loop invariants and induction built on top of the monotone predictor, and establishing provable relations/ bounds between the indeterminate (terminating?) function and the predictor. all that was never formally proven and now its time to try to realize that intuition—to really nail it down so to speak.

`hybrid22.rb`

(7/3) 💡 ❗ some ideas on how to formalize/ rigorize this. its quite natural. the idea is in terms of familar Big-O notation aka Bachmann–Landau notation or asymptotic notation. let f(x) be the collatz sequence for some n ie fn(x) where x is the index in the sequence. then one is attempting to show that eg that f(x) is O(g(x)) for some monotonically decreasing g(x), over all n. the prior lookahead function is a “disorderly” candidate for g(x) in the sense that even though its monotonic, with some order, its still not a very “orderly” function. “orderly” functions would be the typical “analytic” building blocks from complexity theory of polynomials, logs, exponentials. so then the problem is more to show that g(x) is O(h(x)) for some orderly/ analytic/ building-block function h(x) and by transitivity if g(x) is O(h(x)) and f(x) is O(g(x)) then f(x) is O(h(x)). got that? (not sure, dont recall seeing it, has that transitivity rule been proven somewhere?) the simplest h(x) to look for is just h(x) = x + c or h(x) = cx (actually these are equivalent wrt O(·) notation). thinking it over the 1st seems unlikely but the 2nd seems possible or even plausible, eg next to test for empirically.

(7/4) 😳 already 2nd thoughts on that. ok it all sounds great and theres nothing immediately wrong with it but theres that continual/ overarching/ background noise of nagging doubt. it seems the theme of Collatz is that one can empirically find limits everywhere, but proofs of anything seem nonexistent. the very 1st graph anyone ever made was probably the stopping distances and it “obviously looks bounded”. was/ sometimes thinking, is it possible to prove anything at all about the problem? probably have expressed something like these thoughts/ doubts before. maybe should look more for toy proofs/ properties of the problem that exist. how is this latest idea any different than the few hundred that have come before? my only defense is that its inspired by all the experiments and does seem to capture the idea of trying (somehow systematically as possible) to find order in the disorder (entropy).

(7/7) 💡 an old idea in this blog is just to prove that the collatz function calculation/ computation is O(f(n)) for any f(n), either time/ space complexity. this led me to think about how the function seems to be in linear time based on a lot of experiments. but thats not a simple concept. time complexity needs to be defined in terms of accept/ reject. so for collatz the natural mapping is to compute the stopping distance and accept if the sequence stops and dont accept (“hang”!) if it doesnt. but then the conjecture is reduced to that all seeds lead to a halting computation, and therefore that the accept language is the same as the language of all integers. but this language is equivalent to the language of a machine that doesnt compute anything to do with Collatz and simply accepts the language of integers.

heres some interesting factoid from complexity theory. the language of O(f(n)) Turing machines where f(n) is linear (time) is exactly the regular languages. this is due to a relatively obscure (rarely cited) yet ingenious result of Hennie. vaguely recalled that, didnt have the details, and then the wonders of googling yesterday turned up the exact ref (small world a question on `math.stackexchange`). +1! luv google and its near AI capabilities! tadaki et al have a nice survey of the general area. but alas cant figure out a way to leverage all/ any of this wrt the problem at hand. also wonder if there is some way to generalize Hennies result beyond linear time machines. it seems to expose the idea of crossing sequences as critical in understanding Turing machine time complexity. suspect there is something deeper there waiting to be uncovered.

(7/12) am thinking about some old ideas wrt this new estimation function. the original idea sketched out years ago was to try to prove two Turing machines equivalent or within a boundable error of each other. eg TM1 would be the stopping distance calculation via standard collatz calculation and TM2 would be a provably bounded estimate. an interesting idea, maybe outlined before, worth repeating. TM1 represents a sequence and TM2 represent a sequence. in the sense of a TM computing a function f(x) on integers where x is the collatz seed and f(x) is eg the stopping distance. (think technically “stopping distance” is sometimes defined as glide distance but here its trajectory length.) one could look for a sequence 3 generated by a new decidable TM3 and subtract it from both, and try to work with bounding the new sequence(s) (the “residuals” of each). or one could take the sequence TM1 – TM2 represented by a new TM and try to bound that (ie “bounding the error”).

my immediate idea was to look at a bound on the forward estimation function versus the stopping distance function (trajectory length). the difference grows without bound and then looked at the ratio of latter over former. this seems to be bounded under ~10 (‘c12’ black right side scale) based on this quick bitwise search.

`bitwise37.rb`

(7/30) (behind the scenes color commentary:) father-in-law died. moms sister died. Big Corp has a 1wk (5 day) bereavement benefit covering former but not latter. taking it this wk. lets see if they hassle me about the reporting, want to keep it confidential from team/ Mgr. the Mgr has taken on a sinister + nearly terrifying Darth Vadar + nazi guard side + been acting really hyper-control-freak lately and micro-managing-surveilling my screens in the @#%& open office hellscape, walking by constantly, breathing down my neck, confronting/ interrogating me 1-1 small room about any unusual screen + not typing fast enough, now feeling PTSD-paranoia-mix like feelings even to check news + weather and hes acting like opening a Ruby file is a fully legitimately punishable crime against the Big Corp to be prosecuted to the fullest extent of the law.™ woke up one nite in in sweat with vision or idea of being stalked/ hunted…! holy #\$^&!

so as you can see from this relatively short blog (ie wrt other epics on collatz from last yr) my “productivity” is down (something we can both agree on lol!). argh doncha luv the Dark Corporatocracy. honestly feels like grim reaper banging down my door… 5d off will take off a little )( of the heat but its probably gonna be at least as hot or hotter on return… yikes… stress + anxiety… aka snowball in hell… 😮 😳 😡 👿

better news: went to 30yr school reunion and amazingly actually knew a few ppl there. shared more of the “beautiful mind”-like story from my own family now about ~1decade old (almost 9yr exactly). met a close childhood friend hadnt seen in 30yrs. had very warm+personal conversation yet guessing at moment probably infinitesmal )( odds we will meet again given past history. also reconnected/ chatted with a gorgeous redhead who has modelled ages ~20-50 and ran in the same circles as melania trump, bought us tequila shots right around midnite on her (!) prompting, just as party was at full blast/ crescendo and ppl 2ft away were unhearable. got her #. we texted. she called me the wrong name. she had to get on airplane next day and is back in ~½ yr for xmas. my educated engr estimate is ~1/1M that we will meet again lol

using my vac time day 1 to buy a new ipad mini with tradein + credit card points, really beautiful screens on those, think they are even a little better as far as sharpness + color. day 1+ day 2 (today) spent many hours going thru last 1yr of collatz blogs carefully to try to get a bigger pov/ picture/ handle on past + new directions, have some ideas. this is a really big undertaking considering how long/ detailed/ complicated some of the blogs are from last year. elsewhere, \$300 of cool amazon books incl on satoshi nakamoto etc (maybe more on all that later). also with credit card points bought ps4 VR + beat saber + extensively enjoyed gorgeous \$350 Lafuma chair from france for this summer and got it on a friday after ordering it on a monday. amazon is evil awesome lol. using it saw 2 delta acquarid meteors last nite in 30 minutes. felt some tantric awe. + not just from the meteors. 🙂 😎 ⭐ ❤

(7/31) blast from the past, in the old 9/2018 blog at the end there was some investigation of simultaneous optimization of max lsb 1-runs left/ right (glide). while similar however, dont think/ recall this next experiment has been done before. it would be interesting just to try to (more generally) optimize max 0/1-runs left/ right ie not lsb only. this code attempts to push down left max 0/1-runs and push up right max 0/1-runs along with the other metrics. there are at least 2 ways to do that. (1) one approach is directly on the variables, and (2) another is to take the difference (right max 0/1-run minus left) ‘mxrl’ and try to push up the difference. the results generally seem similar except 2nd approach the difference trends/ corner-paints upward near the end.

the optimization overall seems to strongly avoid the ordered glide patterns but also shows that for long glides/ trajectories, somewhat like found in some earlier experiments, there is minimal difference between left/ right side max 0/1-runs (ie ‘mxrl’ red hovering near zero) even when the optimization is designed to push them apart. this seems to argue against 0/1-runs leading to any kind of strong feature distinguishability and that maybe any distinguishability wrt 0/1-runs is mostly associated with the ordered glides, where the ordering/ 0/1-runs tends to be in the initial parts. note max 0/1-runs lines plotted right side scale. 1st following run is 1st optimization scheme type. 2nd is 2nd type showing some paint-into-corner.

• the tendency/ alignment/ pattern of slow upward creep of the max 0/1 runs compared to the faster increase in bit width is similar to some other optimization schemes seen in the past. see also `bitwise9, review117, review124` from 10/2018
• another notable aspect is that no ufos are constructed in the right side even though the optimization is oriented toward finding/ uncovering/ constructing them. a disclaimer, is that iirc, on the other hand, no bitwise experiments have ever found ufos.
• the indistinguishability is familiar yet leads to a bit of a paradox + mystery. clearly there must be something different about left vs right sides that can be identified in individual iterates, which ofc are uniquely identified in binary. whatever it is, binary patterns (at least the various ones considered so far) dont seem to capture it. ❓

`bitwise38.rb`

## 1 thought on “collatz monotone estimator found?”

1. Pingback: collatz outline | Turing Machine