3 ms·

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:

by tocs3 2y ago

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

tocs3 2y ago
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.
- tux3 2y ago
  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)
- throwaway81523 2y ago
  That's surprisingly good, though yeah it misses a detail.
7373737373 2y ago
The definition used on https://wiki.bbchallenge.org/wiki/Collatz-like 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-function-that-bifurcates-on-primes 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 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.
- tocs3 2y ago
  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).
- isaacfrond 2y ago
  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_generalizations https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable...
  - NeoTar 2y ago
    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?
    - LegionMammal978 2y ago
      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.
  - empath75 2y ago
    > 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.
penteract 2y ago
Some earlier blog posts by the same author give more detail. https://www.sligocki.com/2021/07/17/bb-collatz.html 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.
throwaway81523 2y ago
" 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.

by tocs3 2y ago

tocs3 2y ago

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.

tux3 2y ago
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)
throwaway81523 2y ago
That's surprisingly good, though yeah it misses a detail.

7373737373 2y ago

The definition used on https://wiki.bbchallenge.org/wiki/Collatz-like 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-function-that-bifurcates-on-primes 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 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.

tocs3 2y ago
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).
isaacfrond 2y ago
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_generalizations https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable...
- NeoTar 2y ago
  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?
  - LegionMammal978 2y ago
    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.
- empath75 2y ago
  > 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.

penteract 2y ago

Some earlier blog posts by the same author give more detail. https://www.sligocki.com/2021/07/17/bb-collatz.html 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.

throwaway81523 2y ago

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