4

It should be possible to prove the collatz conjecture by mapping the unit digit transitions between numbers, namely into a finite state machine. From there we could use predicates and quanitifiers to prove, by process of exclusion, that for any given combination of 10s digit and 1s digit, no number can transition to anything but whats specified in the state machine assuming that number equals x in x3+1 or x/2

Ipso facto, a series of equations proving by process of elimination, that state machines transitions are the only allowable ones, would prove the collatz conjecture by proving the fsm is a valid representation for any given integer N.

I'm actually working on it now but I don't know enough about modular arithmetic and predicate logic to write a proof. I just have the state diagrams on some dot matrix paper at the moment.

If anyone wants to beat me to it, feel free.

So for example any number ending in 13, will, after x3+1, end in 40.

Any number ending in 40 will end in 20. Any number ending in 20 will end in 10, which will end in 5 as the unit digit.

It's easier to prove in the single digit case, and the finite state machine for that is already written, at least on paper.

I'll post pictures when I get a chance.

Comments
  • 1
    By doing it this way we only have to prove the transition matrix holds for all two digit numbers and *not all* integers.

    I think it is a potential tidy approach sitting at the intersection of modular arithmetic, graph theory, and predicate logic.
  • 4
    Where do I get your crack

    Intelligence-Boost definitely needed
  • 1
    I believe the whole problem with the Collatz Conjecture is that it's not a *finite* state machine since it applies to every nat, and not a very nice infinite one either (if it had easy patterns then it would've been solved long ago). I could be talking out of my ass though, although that does sound like a good approach.
  • 0
    @RememberMe map out the transitions for individual digits.

    1 ends in 4.
    2 ends in 1
    3 ends in 0
    4 ends in 2
    5 ends in 6 (16)
    6 ends in 3 (10)
    7 ends in 2 (22)
    8 ends in 4
    9 ends in 1

    It's not that simple, you're right. It's only a start and doesnt cover more than the transition from number with a magnitude of 1 to numbers with a magnitude with two.

    In practice you can see the above is easily represented as a state machine.

    Probably the next step would be to identify edge cases and work out the rules for them. But for example, being able to prove any number that ends in 1 *eventually* reaches a number that ends in 4, would be I think, the same, but a weaker proof, of the conjecture.

    Edit: think I screwed up the graph, but you can see the general idea laid out.
  • 2
    @jackpearce 1. Become an alcoholic., 2. Fall on head repeatedly, 3. Become a savant but forget all social skills. 4. Breathe through mouth occasionally because of step three.
  • 1
    @Wisecrack

    I do all that except for Step 2 instead of falling on my head I hurt myself like stabbing my right Hand or slip and hurt myself at a high rope course (no I don't cut or hurt myself intentionally I just don't think things through!)
  • 1
    @jackpearce the brain is not in the hand tho bro.

    At best you'll be a crippled violinist.
    Which just makes you average at violin.

    *shrugs* theres always huffing glue I guess.
Add Comment