Computer Science - 2013-03-04

« first day (362 days earlier) ← previous day next day → last day (4077 days later) »

10:31 AM

hi

hlepcomputer

6 hours later…

4:34 PM

hi

1 hour later…

5:40 PM

@user58512 unf the idea seems not to have been written up or pursued much in the existing literature so there seems to be "not much ref"

Collatz conjecture— finite state machine transducer construction, origination?

Sunishtha Singh

6:08 PM

hi

Sunishtha Singh

6:22 PM

@deezy i cn solve it out

2 hours later…

7:54 PM

hi

@vzn, hello

1 hour later…

9:09 PM

@user58512 hey

hhey what sup

nottalotta

@sunishth nice combination, cooking and coding. all about "recipes" wink

@vzn, some fun with collatz

2^n(2k+1) gets reduced to 3k+2

but the diophantine equation 2^{n+1}k+2^n = 3k+2

@user58512 yeah something like that. so do you have any interest in coding on it

can only be solved if 2^{n+1} < 3

so there are no cycles where the 3x+1 thing happens once

now you can try to find the form of a number where you get a 2^n reduction then 3x+1 then a 2^m reduction then a 3x+1 again

and set it equal to see there's no loops like that

9:18 PM

yes stuff like that has been ruled out

there are known/computed limits on how many "iterates" any possible loop or diverging sequence must have.

the limits are very large

ruled out via computer searches & some theory etc

I got that idea from the Lagrias paper you linked

that is a lot lot better than his book :P

there is actually quite a bit of research on it. have not really looked into much of it...

me neither, could be fun but I doubt anyone would let you do a phd in it or whatever

too low chance of success

if the collatz sequence always gets down to 1

then it gives a well founded order of the natural numbers

I think?

yes it is some weird ordering of all natural numbers in several ways

if the conjecture is true

well founded total orders have ordinal ranks

9:24 PM

dont know much about that

I've been playing with small WF orders of prescribed rank

WF=?

well founded ok

well founded, basically if you kkeep going down you always hit 1 eventually

simplest example is just the normal order, rank is omega

as for doing a phd, if one came up with enough novel insight into the problem, but still short of a solution, it could be phd level

more interesting is order them this way: 1,3,5,7,9,11,....,2,4,6,8,10,12,...

then a sequence going down might be like 50,18,4,994846841,864663,3211,7,5,1

if that makes sense

rank is omega^2

because it's two copies of infinity

finite state automata can build orderings of rank omega^omega

9:27 PM

something like that

the paper for that is in french :/

ah

@user58512 what is transcendence theory?

just anything about how trancendental numbers work, Gelfond-Scheider etc

are you an undergraduate?

no

9:31 PM

in school? masters? phd student?

masters

@user58512 have you looked at goodstein sequence proof/ordinals. yes its a good example of deep connection between number/computability theory

once tried to nail that down further but it was shot down in flames

0

Q: CS complexity of famous complex ("fast-growing") mathematical functions

there is a branch of mathematics that has developed roughly in parallel with CS complexity theory that studies "complex" in the sense of "hard-to-compute" functions (because of the property of "fast/rapidly growing") & is related to some of the deepest thms. have long wondered if these func...

cc.complexity-theory reference-request complexity-classes time-complexity space-complexity

@vzn, yeah I need to understand the goodstein stuff, that's why I was workin my way up with smaller ones like omega^omega

are you gonna do a masters thesis? do you have a subj for it?

maybe goldbach conjecture

9:38 PM

cool

heard of some advances in that in last few yrs. cant remember details.

anyway do you have any interest/time for some collatz code experiments

what do you mean?

built some collatz code based on the fsm transducer construction. it seems to reveal the "fundamental ordering"

needs more attn. but its at a preliminary state that can be shared

what do you mean by fundamental ordering?

hard to describe without running the code... roughly, an algorithmic pattern/structure probably not previously discovered, which also seems to be close to revealing an inductive proof structure

there are various orderings of the natural numbers that collatz implies.

its computer assisted so far however. think however the pattern is possibly simple enough to extract from the numerical results.

think there is a function f(n) defined in literature typically called "stopping distance". that is one "ordering".

ok

9:45 PM

anyway, coded this all up in ruby.

found a wild pattern/structure a few wks ago & have to write it up...

needs peer reviewer(s) =)

what is your undergrad degree in?

math too

so: any interest in playing with the ruby code & looking at the "result"

I can look at it the day after tommorow

cool.

thats soon!

it needs ruby installed. ruby installs on just about anything eg windows etc. on good unix systems too.

@vzn, I made a mistake earlier, that was 2 omega not omega^2

1,3,5,7,9,11,....,2,4,6,8,10,12,...

for omega^2 you need infinitely many infinities

I did have a script to print out the numbers for it earlier

10:02 PM

hmm

« first day (362 days earlier) ← previous day next day → last day (4077 days later) »

Transcript for

Mar '134

Computer Science

General discussion for cs.stackexchange.com

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

site design / logo © 2024 Stack Exchange Inc; legal

mobile