Comment by 7373737373 | Hacker News Reader

Comment by 7373737373 | Hacker News Reader

Parent Full thread

The definition used on https://wiki.bbchallenge.org/wiki/Collatz-like for a Collatz-like function is:

> a partial function defined piecewise depending on the remainder of an input modulo some number

(for the best known Collatz conjecture specifically: 2)

and

> A Collatz-like problem is a question about the behavior of iterating a Collatz-like function.

(Regarding the first part, there are other functions that do not use modulo to decide on which "path" to take but some other property of the input number (e.g. its primality: https://mathoverflow.net/questions/205911/a-collatz-like-fun...) that may perhaps also be described as Collatz-like.)

The notation for tape states is documented here: https://wiki.bbchallenge.org/wiki/Directed_head_notation

I think part of the reason why it's so difficult to learn more about this kind of problem is that humanity has simply not found the right language for it yet. And in the case of not only describing, but solving them, a terminology/classification for the "shapes" of halting or non-halting behavior of such systems is also still largely missing.

That's right, the function in the article is:

Given an input n, if n is of the form 3k then output 5k+6

if n is of the form 3k+1 then output 5k+9

if n is of the form 3k+2 then halt

So starting with 0, which is of the form 3x0, we go to 5x0+6=6, then to 5x2+6=16. Because 16 is 3x5+1 we then go to 25+9=34, etc.

The bb program is made such that one computation of the function takes an insane long time.

By the way Conway proved [0] that any computer program can be rewritten in the form of these collatz like functions. So they are pretty prowerful.

[0]: https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable...

Interesting - if any computer program can be rewritten in the form of a Collatz-like function, is it at all surprising that the BB problems appear in this form?

The interesting part is how simple the resulting Collatz-like functions are to describe, suggesting that the Collatz-like form is the most 'natural' form for hard problems given the TM formalism. E.g., any program can also be rewritten in the form of a Diophantine equation, but most of those would be monstrously large.

> By the way Conway proved [0] that any computer program can be rewritten in the form of these collatz like functions. So they are pretty prowerful.

I don't think that article supports that claim, but maybe I'm misunderstanding it.

The wikipedia article doesn't do full justice perhaps though the essence is there. The reason the halting problem is equivalent to solving collatz like problems is because you can rewrite any turing machine in terms of a generalized collatz function. The Fractran wikipedia page has more info.

(the original conway article itself is also very readable: FRACTRAN: A SIMPLE UNIVERSAL PROGRAMMING LANGUAGE FOR ARITHMETIC)

Re the link to the wiki and its introductory paragraph:

If you ask yourself why the 2nd part of the original Collatz function is:

  c(2k+1) = 3k+2

the reason is that:

3x+1 applied to (2k+1) is 6k+4 which can immediately be divided by 2 and results in 3k+2.

Thank you. I have been looking a little at your github Busy_Beaver repository. I think I will stick with my on code writing for a little while (amateurish but I am learning a little bit writing it).

Reply on news.ycombinator.com