this is an attempt to visualize the results of a grammar compression of the first 6K collatz trajectories. not fully sure what it means yet, have to dig into it further. it seems to indicate that there are long “recursively repetitive” strings of up/down sequences that dont deviate very much (ie mean returning). it also seems to exhibit some scale-invariance. probably I need to be working with a large graph visualization software, has anyone heard of any? the decomposition is in the form of a fair-sized DAG. gotta figure out what that guy used in his masters thesis on SAT clause graph analysis lying around here somewhere….
hi all. coding has been very good to me over the years, ever since I was a teenager. could write a lot about it and already have elsewhere on the blog. I will be the 1st to admit its not for everybody [and have been saying that ever since I 1st learned it]. yet, it is very much worthwhile and occasionally exciting and transformative.
here is a big bag of informative, standout, high quality, engaging, and entertaining links & a post Ive been working on for the better part of a year. its styled as relatively diverse and focused at the same time. am timing it with Computer Science EDU week Dec 9-15 2013. its a celebration of coding and the complex environment and universe that surrounds it, its past, present and future. I also like to borrow heavily from popular stackexchange questions that delve into various aspects.
this is an idea that I tried out a few months ago but failed with a negative result. a slight variation leads to positive results that look quite promising to me. am immed posting it in very preliminary/rough form because its quite novel and am excited about the success. suspect it could lead to a lot of different analysis ideas and maybe be a key milestone/change in direction.
for years have been very interested in grammar compression related to TCS type research. it seems to me it could lead to very deep results. kolmogorov complexity analysis has some fairly rough natural relation to grammar compression. there are natural ways to express ideas about various important complexity results in terms of grammar compression. I tend to see a lot of complexity theory in terms of compression ideas & think the field would very much benefit from a review or conceptual reorientation/reformulation from that pov/angle. eg in the way that much of complexity theory can be approach from the circuit pov. ie a comprehensive “worldview”.
hi all. found some very neat new papers on the collatz conjecture. would like to go into much more detail about them, but if a blog writer writes and nobody comments, does it make any noise? in short michel finds some collatz-like problems at the heart of some low-complexity TMs. laarhoven ties the iteration dynamics into de bruijn graphs. cool! both refs show that this problem is increasingly being taken seriously. couldnt have imagined it would generate so much more research in the 2 decades since Ive been looking at it. 2 of my favorite quotes, both coming close to some of my original motivations for studying it…
“Because of its simple formulation, researchers from many different branches of mathematics have at one time or another encountered this problem and have become fascinated by it. This has lead to hundreds of papers in the last few decades, with each researcher using his own area of expertise to shed a new light on this problem.”
some new ideas. as mused on earlier and a continuing theme, it would seem that “derandomizing” has something to do with resolving collatz. derandomizing is part of some of the most important techniques and proofs in complexity theory eg AKS Primes in P, st connectivity in L, etc.
if an algorithm had a small amount of space (a buffer) to “derandomize” the output as best possible, how would that look? here are two interesting ideas along these lines.