Hacker News Reader

Comment by tocs3 | Hacker News Reader

Is there a more "popular science" description of what is being said here. I would like to understand what is meant by "Collatz-like". Is it a function like:

  f(n) = {n/2 : for even n,
          3n+1 : for odd n}

Can I sit round for days making trivial calculations looking for patterns?

What does

  M(n) = 0^inf < A 1^n 0^inf.

mean?

I have really enjoyed the Busy Beaver stuff and play with simple code to try and learn what I can but when I read about it I run into the brick wall of math reading comprehension. Numberphile on youtube is pretty good sometimes with explanations but is not a reference. I do not know where to turn (I might ask chatGPT just to see what happens).

View on HN

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.

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).

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.

Some earlier blog posts by the same author give more detail.

https://www.sligocki.com/2021/07/17/bb-collatz.html is one that covers the analysis of a particular machine in great detail, including explaining what definitions like "M(n) = 0^inf < A 1^n 0^inf" mean.

OK, you were not fast enough. I asked chatGPT. I think it helped but there is still a lot I do not understand.

  M(n) = 0^inf <A 1^n 0^inf.

Is, in pseudo math/English, some Turing machine in state n is equal to

  An infinite list of zeros up to the position of the machine pointer followed by some number of ones (maybe zero ones?) followed by another infinite list of zeros.

I think at this point chatGPT gets something wrong but at this point I hit the Free plan limit for GPT-4o and will have to wait till 2:13PM.

A turing machine has a position on a tape and an internal state

The <A means the machine is in state A and facing left. To its left are infinitely many zeroes (0^inf), to its right are n 1s, and then infinitely many zeroes (the initial tape is infinite, and starts filled with zeroes)

That's surprisingly good, though yeah it misses a detail.

" M(n) = 0^inf < A 1^n 0^inf."

I read that as an infinite string of 0's (0^inf), then the tape head (<), then a string of exactly n 1's (1^n), then infinitely many 0's. So a block of n 1's starting at the tape head, surrounded by endless 0's to the left and right.

Reply on news.ycombinator.com