3 ms·

This is too much nerd for me. Can anyone tell me what is the required pre-requisite of knowledge to understand things like this? Like will knowing basic calcul

This is too much nerd for me. Can anyone tell me what is the required pre-requisite of knowledge to understand things like this? Like will knowing basic calculus be enough? What specific topics or subjects will give me good fundamentals on these things? Thank you.

jdthedisciple 3y ago
This fits squarely into theoretical computer science. Going through any introductory TCS textbook will help you understand most of this stuff. CS students do this in their first or second year of their studies, and yes it's tough (at my uni this was among the most feared exams).
- acmiyaguchi 3y ago
  A first or second year (undergrad) student doing theoretical science to this level is astounding to me. It was an upper-division course for me, albeit a prerequisite for things like compilers and cryptography, so I'm sure it could be put earlier in the journey. Sipser's "Introduction to the Theory of Computation" was the book I had to read, and it certainly makes this post more accessible.
  - auggierose 3y ago
    Interesting, Sipser starts the natural numbers with 1 in this book, instead of 0. I like this choice, and I would like to use it myself. But if ℕ starts with 1, what do I call {0} ∪ ℕ? I guess ℕ₀ is a reasonable choice.
    - thaumasiotes 3y ago
      > I like this choice, and I would like to use it myself. It's not a great choice, purely for the reason that there's already a convenient name for the positive integers, ℤ⁺.
      - auggierose 3y ago
        I've just checked with a few math books I like, and they are using ℕ and ℕ₀ throughout. What I don't like about ℤ⁺ is that 1) it talks about integers, although negative numbers might not be relevant in the current context at all, and 2) it's not really clear if ℤ⁺ denotes ℕ or ℕ₀. Of course, you have the same ambiguity problem with ℕ. Oh, see how I numbered this 1) and 2), not 0) and 1)?
        thaumasiotes 3y ago
        > Oh, see how I numbered this 1) and 2), not 0) and 1)? So what? > 2) it's not really clear if ℤ⁺ denotes ℕ or ℕ₀. On the contrary. ℕ is ambiguous between the positive integers and nonnegative integers, though in my experience it's usually the nonnegative integers. But ℤ⁺ is absolutely unambiguous. It's the positive integers. And since you frequently need to refer to the nonnegatives, it makes sense to have a symbol for them too. There's almost no benefit to having ℕ available as a synonym for ℤ⁺. There's a lot of benefit to having it available as a synonym for ℤ\ℤ⁻.
        auggierose 3y ago
        > So what? Well, it means I usually need either ℕ or ℤ, not ℕ₀. > And since you frequently need to refer to the nonnegatives It depends on the context. You don't use ℕ₀ much, if you agree that counting starts at 1. You then use either ℕ or ℤ, which just looks cleaner. No reason to complicate such a simple concept as {1, 2, 3, ...} with something complicated such as ℤ⁺. As I said before, to understand {1, 2, 3, ...}, you don't need the concept of negative numbers at all, so why drag it in through confusing symbols? > But ℤ⁺ is absolutely unambiguous. It's the positive integers. Or the non-negative integers. And that's not just my opinion. Here is what ChatGPT has to say about that: *system*: You are a mathematics professor, and happy to chat about mathematics and the philosophy of mathematics. -------------------- *user*: What would you say ℤ⁺ stands for? Are there multiple options? -------------------- *assistant*: ℤ⁺ typically stands for the set of positive integers. This usually includes all the whole numbers greater than zero. However, there can be some variation in its definition depending on the context. In some contexts, ℤ⁺ might be defined to include zero, so it would represent the set of non-negative integers. This is less common, but it does occur in some areas of mathematics. The symbol ℤ comes from the German word "Zahlen," which means "numbers." The superscript "+" is used to denote that we're only considering the positive members of this set (or non-negative, in some cases). So, yes, there can be multiple options for what ℤ⁺ represents, but they are all closely related. It's always a good idea to clarify these kinds of notational issues when they arise, to avoid any potential confusion.
    - deleted 3y ago
      [deleted]
jcagalawan 3y ago
Theory of Computation, Number Theory, and Probability are good starts.
- FartyMcFarter 3y ago
  You don't need any probability or number theory to understand busy-beavers even though the article mentions some probability stuff. You also don't need them to understand the basic properties of Collatz problems. So I'd reduce it to Theory of Computation and some extremely basic maths in order to have a reasonable basic understanding of the subject.
markuswt 3y ago
Calculus has little to do with this kind of problem. You should study theoretical computer science, in particular computability theory, to understand the article. Many CS undergraduate programs will have courses with public resources you can follow.
kybernetikos 3y ago
This [1] is a really accessible introduction to busy beaver numbers. [1] https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html
unhammer 3y ago
More like discrete math and automata theory https://en.m.wikipedia.org/wiki/Automata_theory https://en.m.wikipedia.org/wiki/Automata_theory or theory of computation. Hopcroft & Ullmann's intro book is nice. But there's so much related stuff here, it's just a starting point.

jdthedisciple 3y ago

This fits squarely into theoretical computer science. Going through any introductory TCS textbook will help you understand most of this stuff. CS students do this in their first or second year of their studies, and yes it's tough (at my uni this was among the most feared exams).

acmiyaguchi 3y ago
A first or second year (undergrad) student doing theoretical science to this level is astounding to me. It was an upper-division course for me, albeit a prerequisite for things like compilers and cryptography, so I'm sure it could be put earlier in the journey. Sipser's "Introduction to the Theory of Computation" was the book I had to read, and it certainly makes this post more accessible.
- auggierose 3y ago
  Interesting, Sipser starts the natural numbers with 1 in this book, instead of 0. I like this choice, and I would like to use it myself. But if ℕ starts with 1, what do I call {0} ∪ ℕ? I guess ℕ₀ is a reasonable choice.
  - thaumasiotes 3y ago
    > I like this choice, and I would like to use it myself. It's not a great choice, purely for the reason that there's already a convenient name for the positive integers, ℤ⁺.
    - auggierose 3y ago
      I've just checked with a few math books I like, and they are using ℕ and ℕ₀ throughout. What I don't like about ℤ⁺ is that 1) it talks about integers, although negative numbers might not be relevant in the current context at all, and 2) it's not really clear if ℤ⁺ denotes ℕ or ℕ₀. Of course, you have the same ambiguity problem with ℕ. Oh, see how I numbered this 1) and 2), not 0) and 1)?
      - thaumasiotes 3y ago
        > Oh, see how I numbered this 1) and 2), not 0) and 1)? So what? > 2) it's not really clear if ℤ⁺ denotes ℕ or ℕ₀. On the contrary. ℕ is ambiguous between the positive integers and nonnegative integers, though in my experience it's usually the nonnegative integers. But ℤ⁺ is absolutely unambiguous. It's the positive integers. And since you frequently need to refer to the nonnegatives, it makes sense to have a symbol for them too. There's almost no benefit to having ℕ available as a synonym for ℤ⁺. There's a lot of benefit to having it available as a synonym for ℤ\ℤ⁻.
        auggierose 3y ago
        > So what? Well, it means I usually need either ℕ or ℤ, not ℕ₀. > And since you frequently need to refer to the nonnegatives It depends on the context. You don't use ℕ₀ much, if you agree that counting starts at 1. You then use either ℕ or ℤ, which just looks cleaner. No reason to complicate such a simple concept as {1, 2, 3, ...} with something complicated such as ℤ⁺. As I said before, to understand {1, 2, 3, ...}, you don't need the concept of negative numbers at all, so why drag it in through confusing symbols? > But ℤ⁺ is absolutely unambiguous. It's the positive integers. Or the non-negative integers. And that's not just my opinion. Here is what ChatGPT has to say about that: *system*: You are a mathematics professor, and happy to chat about mathematics and the philosophy of mathematics. -------------------- *user*: What would you say ℤ⁺ stands for? Are there multiple options? -------------------- *assistant*: ℤ⁺ typically stands for the set of positive integers. This usually includes all the whole numbers greater than zero. However, there can be some variation in its definition depending on the context. In some contexts, ℤ⁺ might be defined to include zero, so it would represent the set of non-negative integers. This is less common, but it does occur in some areas of mathematics. The symbol ℤ comes from the German word "Zahlen," which means "numbers." The superscript "+" is used to denote that we're only considering the positive members of this set (or non-negative, in some cases). So, yes, there can be multiple options for what ℤ⁺ represents, but they are all closely related. It's always a good idea to clarify these kinds of notational issues when they arise, to avoid any potential confusion.
  - deleted 3y ago
    [deleted]

jcagalawan 3y ago

Theory of Computation, Number Theory, and Probability are good starts.

FartyMcFarter 3y ago
You don't need any probability or number theory to understand busy-beavers even though the article mentions some probability stuff. You also don't need them to understand the basic properties of Collatz problems. So I'd reduce it to Theory of Computation and some extremely basic maths in order to have a reasonable basic understanding of the subject.

markuswt 3y ago

Calculus has little to do with this kind of problem. You should study theoretical computer science, in particular computability theory, to understand the article. Many CS undergraduate programs will have courses with public resources you can follow.

kybernetikos 3y ago

This [1] is a really accessible introduction to busy beaver numbers. [1] https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html

unhammer 3y ago

More like discrete math and automata theory https://en.m.wikipedia.org/wiki/Automata_theory https://en.m.wikipedia.org/wiki/Automata_theory or theory of computation. Hopcroft & Ullmann's intro book is nice. But there's so much related stuff here, it's just a starting point.