6 ms·

A number that can't be calculated

41 points by alexmolas 4y ago

swid 4y ago
I’m not sure I buy the argument that you can say that we know the halting problem is unsolvable and therefore we can’t calculate BB. The halting problem is unsolvable due to a contradiction, but there is a finite set of programs with given number of symbols; one or more of them share the max non infinite running time, and if you did have the oracle to answer that, you can in fact run the algorithm provided, except for how long this would take in real time. A different take is that you can write a program that will only terminate if ZF set theory is false, which is impossible to prove using math due to Gödel's incompleteness theorems. We assume this program should run forever, but would not be able to prove it. That program provides some upper bound to the highest BB number we could ever hope to prove with certainty: 748 according to this article from a few years back. The problem of the post is that an all knowing oracle doesn’t have this problem, and assuming the program has finite length, our being able to prove whether it halts or not does not stop there from being an answer to that question. https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/ https://www.quantamagazine.org/the-busy-beaver-game-illumina...
- zaik 4y ago
  > if you did have the oracle to answer that I think you are correct, but the question is simply if we can compute this maximum number - without any oracles. Then the answer will be no, since we could decide the halting problem as shown by the author.
- alexmolas 4y ago
  Thanks for the link, it was an interesting read! I'm not arguing that you can't calculate BB numbers, in fact we've calculated some of them. What I'm arguing is that you can't calculate all the BB numbers, since this will mean that the Halting Problem is solvable. Using the results of your link I guess we can say that BB numbers can be computed if n<748 (or <20 according to Aaronson). > In 2016, he and his graduate student Adam Yedidia specified a 7,910-rule Turing machine that would only halt if ZF set theory is inconsistent. This means BB(7,910) is a calculation that eludes the axioms of ZF set theory. Those axioms can’t be used to prove that BB(7,910) represents one number instead of another, which is like not being able to prove that 2 + 2 = 4 instead of 5. OMG! A number that's so much big that can be contained in the ZF set theory.
- NotYourLawyer 4y ago
  Yes, an all-knowing oracle knows the busy beaver numbers.
  - alexmolas 4y ago
    I don't think so. If that was the case, then for any program we could compute its length n, and then ask the all-knowing oracle the value of BB(n). And knowing BB(n) for any n we could solve the Halting Problem, but we know that the Halting Problem is unsolvable. Therefore we must conclude that such an all-knowing oracle can't exist.
    - NotYourLawyer 4y ago
      Yes, that’s my point. The all-knowing oracle could also just tell you whether or not your program halts.
sebastialonso 4y ago
cool series. In my opinion, Chaitin constant is the best example to understand incomputable numbers, hopefully author can include it later.
- alexmolas 4y ago
  Thanks for your comment! Indeed, Chaitin constant is an amazing example, however I failed to understand how can it be computed at least approximately. What I like about the example in the post is that you can compute some digits of the $\Omega$ constant, which in my opinion is more pedagogical. If you have some resources regarding Chaitin constant I would be very happy to read them :)
  - sebastialonso 4y ago
    I'll look some videos from a while ago. Again, great series, hope you keep publishing!
    - alexmolas 4y ago
      haha thank you very much! I'm happy you enjoyed it :)
  - tromp 4y ago
    Chaitin computed the first few bits of a LISP based version of Omega in one of his books. For my own lambda based version of Omega I was able to compute the first 4 bits [1]. [1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Halting_probability https://tromp.github.io/cl/Binary_lambda_calculus.html#Halti...
moomin 4y ago
I think it’s much simpler than that. If you remember your maths well enough to remember the proof that the reals are uncountable and the rationals are countable, consider that the list of programs that produce a number is countable. You don’t need to check if the program halts or not, even if we “count” the “numbers” from the programs that don’t halt _it’s still countable_. But we’re still left with an uncountable set of numbers for which we can’t even write a program. Easiest way to construct one is to use the diagonal argument that’s used to prove, amongst other things, the halting problem.
- kotlin2 4y ago
  You have an assumption that each number needs a unique program to compute the digits. You'd need to prove that statement first.
  - craggyjaggy 4y ago
    How can the same program produce multiple different results?
  - sblom 4y ago
    By definition, each program only produces the digits of one number. It's okay for more than one program to produce the same number. Am I misunderstanding your point?
    - kotlin2 4y ago
      I didn’t realize the initial state of the tape was part of the definition of a Turing machine. I was picturing having the same operations applied to different tapes, but that’s not the definition so I’m wrong.
- alexmolas 4y ago
  yes, I didn't think about it, but you're right! However, I liked the idea to have a constructive way to build an uncomputable number
- 4y ago
ashton314 4y ago
> Even if God himself came from Heaven, he could not compute these numbers. Uncomputable numbers are numbers that can’t be computed because of maths limitations. I like to think that God has access to much better math and computational resources than we can even begin to conceive of. ;-)
- kibwen 4y ago
  There are numbers that god can't compute, but that supergod can compute. Of course, that also means there are numbers that supergod can't compute, but that superdupergod can compute. And from there it's turtles all the way up.
fallingfrog 4y ago
Something about that proof feels wrong.. Are you sure the allusion to the halting problem applies here? The proof that the halting problem can't be computed relies on a self-reference where you query whether the program halted and then do the opposite. But- and here's the important part- when the program references itself it requires at least one more symbol to do so as it needs somewhere to store the answer. It therefore needs an infinite stack. But we have a fixed number of symbols. Or, to put it another way: if your set of symbols is bounded, then you can only call functions that use at least one fewer symbol than the calling one, which means you will eventually run out of symbols and have a base case. Doesn't that mean the halting problem doesn't apply to the busy beaver problem?
VyseofArcadia 4y ago
I mean, almost every real number is not computable. If you stick your hand into a grab-bag of reals, you will grab an incomputable number with probability 1. As another commenter mentioned, the computable reals are countable, and the reals are very much not. There is a whole field of mathematics striving to see how far you can go, analysis-wise, with just computable numbers.[0] [0] https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis
- singularity2001 4y ago
  I copy an interesting paragraph: "A notable result is that integration (in the sense of the Riemann integral) is computable. This might be considered surprising as an integral is (loosely speaking) an infinite sum. While this result could be explained by the fact that every computable function from {[0,1]} to R is uniformly continuous, the notable thing is that the modulus of continuity can always be computed without being explicitly given. A similarly surprising fact is that differentiation of complex functions is also computable, while the same result is false for real functions." Are real functions not a subset of complex functions? Oh, if you redirect the output to R it gets harder, just like with finding zero roots.
  - VyseofArcadia 4y ago
    I think you could get an idea some of the subtleties of this if we try to make what you mean be "subset" explicit. Starting off on a set theoretic foot, what even is a function f:A->B? Well, it's a set of pairs (a, b) with a in A, b in B, such that (a, b) in f and (a', b) in f implies a = a'. In this sense, you could say a function r:R->R is a subset of some c:C->C by defining r = {(x, x') in c : x in R} On the other hand, the set of functions C->C is a different beast entirely, because that consists of all functions whose domain is C, whereas the set of functions R->R is all functions whose domain is R. While each individual function in R->R is a subset of some function in C->C, R->R itself is not a subset of C->C. I'm no analyst, complex or real, but my intuition is that C simultaneously has more wiggle room in the topological sense (you have a whole extra dimension) but less wiggle room in an algebraic sense (deg n polynomials are guaranteed to have n roots in C), it's pretty easy to just stumble upon surprising and unintuitive results. Thinking back to my grad school complex analysis course, limits are fundamentally different in C. In R, you have two directions from which you can approach a point, but in C, any sequence converging on the point is a valid perspective from which the limit must make sense. You can approach the point from a straight line in any direction, or a squiggly line, or a spiral, etc etc. So this extra dimension of wiggle room puts a hell of a strong condition on what functions can even be differentiable in the first place, and this restriction on differentiability often translates to stronger results.
tromp 4y ago
> If after these steps the program hasn’t halted it means it’ll never halt (by the definition of the Sigma(n)) This argument doesn't quite work since Sigma(n) is the maximum number of characters printed before halting rather than the maximum finite number of steps of computation. The argument would work for the other flavor of Busy Beaver though.
Kranar 4y ago
Don't think this article is correct when it says that Omega can't be computed to arbitrary precision, it certainly can be. While it's true that there is no algorithm that can compute BB(n) for all n, it is always possible to compute BB(k) for a specific and arbitrary k. This is a very subtle detail. Similarly for Omega, while there's no algorithm that can compute Omega to an arbitrary precision, that is not the same as saying that there's some upper bound on the precision that Omega can be computed. For any precision k, it's possible to compute Omega up to that precision. The issue is that whatever algorithm you devise to compute Omega up to a precision of k, that algorithm will fail to compute Omega for some other precision q > k. You will need a fundamentally different algorithm for q > k, but such an algorithm does exist. You'll also need a fundamentally different algorithm for precision r > q, but that also exists... ad infinitum.
- dllthomas 4y ago
  > it is always possible to compute BB(k) for a specific and arbitrary k How do you do that once k is large enough that it admits Turing machines whose halting behavior is independent of our axioms?
  - vainguard 4y ago
    BB(k) for a specific k is just a number. Ao just write it to the output. Proofing correctness is different from „computing“ and not required here.
    - puffoflogic 4y ago
      > BB(k) for a specific k is just a number. That's not as obvious as you might think. The value of BB(800) is independent of ZFC. So it isn't "just a number" if you're working in ZFC.
      - dllthomas 4y ago
        Hmm... As ZFC specifically cannot identify that number as special (at least as relates to the Busy Beaver function), maybe it is quite specifically "just a number"!
kotlin2 4y ago
I'm unfamiliar with BB(n), so this raises an interesting question for me. How do we know that BB(n) exists for all n? This is relevant to this post because the author's definition of omega relies on BB(n) being defined for all n. Obviously there are numbers that are not computable, but it seems one needs to be careful that the numbers discussed are sure to exist.
- morelisp 4y ago
  > How do we know that BB(n) exists for all n? It's trivial to construct a candidate for each n, which gives a lower bound.
- nimih 4y ago
  > How do we know that BB(n) exists for all n? What would it mean for BB(n) to "not exist"? Recall that BB(n) is defined in a very concrete way: you take all the Turing machines of size n (which are easily enumerable combinatorial objects), remove ones which do not halt, then take the largest runtime of the ones that are left. Since we can always write down a Turing machine which halts immediately, we know that there's a trivial lower bound for each BB(n), and since the Turing machines are deterministic, we know that any machine that halts must do so in a fixed number of steps. With such a straightforward construction, it's hard to see how such a number could "not exist," at least not without appealing to an ontology somewhat outside of the mainstream (e.g. ultrafinitism).
  - kotlin2 4y ago
    In the proof you just provided, you have a step "remove ones which do not halt". By which process do you do that? By the halting-problem, you can't actually make that selection. This ties back into the fact that BB(n) is not computable for all n. I guess what I'm looking for is a proof that the number exists without violating the halting problem. Intuitively, we feel BB(n) should exist because there are finite turing machines with n states. But I'm not sure how to express that rigorously. Or maybe relying on a solution to the halting problem doesn't matter in terms of a proof.
    - 4y ago
zokier 4y ago
I feel the article is mixing up S(n) (max number of steps) and Σ(n) (max number of 1s written), going by the wikipedia article of BB https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver Notably the list of BB numbers in the article matches the values of S(n) in wikipedia instead of Σ(n). Also this sentence makes more sense if you replace Σ(n) with S(n) > If after these steps the program hasn’t halted it means it’ll never halt (by the definition of the Σ(n)).
- alexmolas 4y ago
  Oh yeah, you're right, I mixed up the terms. I just started learning about this topic and I got excited and wrote the post. I'll fix it ASAP. Thank you very much for spotting it :)
lcuff 4y ago
The code he gives, and the explanation of the busy beaver problem, strikes me as pretty poorly explained. If I didn't already know about the busy beaver problem, I don't think I could get it from this explanation.
- alexmolas 4y ago
  hi, author here! Thanks for your comment. Which where the parts that are poorly explained? I would love to get some feedback from you. I just started learning about computability theory, so maybe I explained some concepts wrong. Also, english is not my first language, so perhaps I lost something in translation. Thanks :)
aaplok 4y ago
> since we don’t know Σ(n) we can’t know the exact value of Ω. Hmmm. Just because you don't know the individual terms of the sequence, it doesn't follow that you don't know their infinite sum. Here's a trivial example: take the sum `(-1)^n Σ(floor(n/2))`. The infinite sum is obviously 0, yet we can't calculate each of the terms, nor many of the partial sums.
- alexmolas 4y ago
  > Just because you don't know the individual terms of the sequence, it doesn't follow that you don't know their infinite sum Yes, this is not true in general. But I think it's true for the specific definition of Ω we use in the post.
  - aaplok 4y ago
    Intuitively I'd say you're probably right. But computation theory is full of counter-intuitive results. Your statement might be provable by adapting the argument that Σ(n) is not always computable. Something like computing the sum would require solving some version of the halting problem. Perhaps add a small edit to your article to highlight that this particular statement isn't to be taken as a mathematical proof?

41 points by alexmolas 4y ago

swid 4y ago

I’m not sure I buy the argument that you can say that we know the halting problem is unsolvable and therefore we can’t calculate BB. The halting problem is unsolvable due to a contradiction, but there is a finite set of programs with given number of symbols; one or more of them share the max non infinite running time, and if you did have the oracle to answer that, you can in fact run the algorithm provided, except for how long this would take in real time. A different take is that you can write a program that will only terminate if ZF set theory is false, which is impossible to prove using math due to Gödel's incompleteness theorems. We assume this program should run forever, but would not be able to prove it. That program provides some upper bound to the highest BB number we could ever hope to prove with certainty: 748 according to this article from a few years back. The problem of the post is that an all knowing oracle doesn’t have this problem, and assuming the program has finite length, our being able to prove whether it halts or not does not stop there from being an answer to that question. https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210/ https://www.quantamagazine.org/the-busy-beaver-game-illumina...

zaik 4y ago
> if you did have the oracle to answer that I think you are correct, but the question is simply if we can compute this maximum number - without any oracles. Then the answer will be no, since we could decide the halting problem as shown by the author.
alexmolas 4y ago
Thanks for the link, it was an interesting read! I'm not arguing that you can't calculate BB numbers, in fact we've calculated some of them. What I'm arguing is that you can't calculate all the BB numbers, since this will mean that the Halting Problem is solvable. Using the results of your link I guess we can say that BB numbers can be computed if n<748 (or <20 according to Aaronson). > In 2016, he and his graduate student Adam Yedidia specified a 7,910-rule Turing machine that would only halt if ZF set theory is inconsistent. This means BB(7,910) is a calculation that eludes the axioms of ZF set theory. Those axioms can’t be used to prove that BB(7,910) represents one number instead of another, which is like not being able to prove that 2 + 2 = 4 instead of 5. OMG! A number that's so much big that can be contained in the ZF set theory.
NotYourLawyer 4y ago
Yes, an all-knowing oracle knows the busy beaver numbers.
- alexmolas 4y ago
  I don't think so. If that was the case, then for any program we could compute its length n, and then ask the all-knowing oracle the value of BB(n). And knowing BB(n) for any n we could solve the Halting Problem, but we know that the Halting Problem is unsolvable. Therefore we must conclude that such an all-knowing oracle can't exist.
  - NotYourLawyer 4y ago
    Yes, that’s my point. The all-knowing oracle could also just tell you whether or not your program halts.

sebastialonso 4y ago

cool series. In my opinion, Chaitin constant is the best example to understand incomputable numbers, hopefully author can include it later.

alexmolas 4y ago
Thanks for your comment! Indeed, Chaitin constant is an amazing example, however I failed to understand how can it be computed at least approximately. What I like about the example in the post is that you can compute some digits of the $\Omega$ constant, which in my opinion is more pedagogical. If you have some resources regarding Chaitin constant I would be very happy to read them :)
- sebastialonso 4y ago
  I'll look some videos from a while ago. Again, great series, hope you keep publishing!
  - alexmolas 4y ago
    haha thank you very much! I'm happy you enjoyed it :)
- tromp 4y ago
  Chaitin computed the first few bits of a LISP based version of Omega in one of his books. For my own lambda based version of Omega I was able to compute the first 4 bits [1]. [1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Halting_probability https://tromp.github.io/cl/Binary_lambda_calculus.html#Halti...

moomin 4y ago

I think it’s much simpler than that. If you remember your maths well enough to remember the proof that the reals are uncountable and the rationals are countable, consider that the list of programs that produce a number is countable. You don’t need to check if the program halts or not, even if we “count” the “numbers” from the programs that don’t halt _it’s still countable_. But we’re still left with an uncountable set of numbers for which we can’t even write a program. Easiest way to construct one is to use the diagonal argument that’s used to prove, amongst other things, the halting problem.

kotlin2 4y ago
You have an assumption that each number needs a unique program to compute the digits. You'd need to prove that statement first.
- craggyjaggy 4y ago
  How can the same program produce multiple different results?
- sblom 4y ago
  By definition, each program only produces the digits of one number. It's okay for more than one program to produce the same number. Am I misunderstanding your point?
  - kotlin2 4y ago
    I didn’t realize the initial state of the tape was part of the definition of a Turing machine. I was picturing having the same operations applied to different tapes, but that’s not the definition so I’m wrong.
alexmolas 4y ago
yes, I didn't think about it, but you're right! However, I liked the idea to have a constructive way to build an uncomputable number
4y ago

ashton314 4y ago

> Even if God himself came from Heaven, he could not compute these numbers. Uncomputable numbers are numbers that can’t be computed because of maths limitations. I like to think that God has access to much better math and computational resources than we can even begin to conceive of. ;-)

kibwen 4y ago
There are numbers that god can't compute, but that supergod can compute. Of course, that also means there are numbers that supergod can't compute, but that superdupergod can compute. And from there it's turtles all the way up.

fallingfrog 4y ago

Something about that proof feels wrong.. Are you sure the allusion to the halting problem applies here? The proof that the halting problem can't be computed relies on a self-reference where you query whether the program halted and then do the opposite. But- and here's the important part- when the program references itself it requires at least one more symbol to do so as it needs somewhere to store the answer. It therefore needs an infinite stack. But we have a fixed number of symbols. Or, to put it another way: if your set of symbols is bounded, then you can only call functions that use at least one fewer symbol than the calling one, which means you will eventually run out of symbols and have a base case. Doesn't that mean the halting problem doesn't apply to the busy beaver problem?

VyseofArcadia 4y ago

I mean, almost every real number is not computable. If you stick your hand into a grab-bag of reals, you will grab an incomputable number with probability 1. As another commenter mentioned, the computable reals are countable, and the reals are very much not. There is a whole field of mathematics striving to see how far you can go, analysis-wise, with just computable numbers.[0] [0] https://en.wikipedia.org/wiki/Computable_analysis https://en.wikipedia.org/wiki/Computable_analysis

singularity2001 4y ago
I copy an interesting paragraph: "A notable result is that integration (in the sense of the Riemann integral) is computable. This might be considered surprising as an integral is (loosely speaking) an infinite sum. While this result could be explained by the fact that every computable function from {[0,1]} to R is uniformly continuous, the notable thing is that the modulus of continuity can always be computed without being explicitly given. A similarly surprising fact is that differentiation of complex functions is also computable, while the same result is false for real functions." Are real functions not a subset of complex functions? Oh, if you redirect the output to R it gets harder, just like with finding zero roots.
- VyseofArcadia 4y ago
  I think you could get an idea some of the subtleties of this if we try to make what you mean be "subset" explicit. Starting off on a set theoretic foot, what even is a function f:A->B? Well, it's a set of pairs (a, b) with a in A, b in B, such that (a, b) in f and (a', b) in f implies a = a'. In this sense, you could say a function r:R->R is a subset of some c:C->C by defining r = {(x, x') in c : x in R} On the other hand, the set of functions C->C is a different beast entirely, because that consists of all functions whose domain is C, whereas the set of functions R->R is all functions whose domain is R. While each individual function in R->R is a subset of some function in C->C, R->R itself is not a subset of C->C. I'm no analyst, complex or real, but my intuition is that C simultaneously has more wiggle room in the topological sense (you have a whole extra dimension) but less wiggle room in an algebraic sense (deg n polynomials are guaranteed to have n roots in C), it's pretty easy to just stumble upon surprising and unintuitive results. Thinking back to my grad school complex analysis course, limits are fundamentally different in C. In R, you have two directions from which you can approach a point, but in C, any sequence converging on the point is a valid perspective from which the limit must make sense. You can approach the point from a straight line in any direction, or a squiggly line, or a spiral, etc etc. So this extra dimension of wiggle room puts a hell of a strong condition on what functions can even be differentiable in the first place, and this restriction on differentiability often translates to stronger results.

tromp 4y ago

> If after these steps the program hasn’t halted it means it’ll never halt (by the definition of the Sigma(n)) This argument doesn't quite work since Sigma(n) is the maximum number of characters printed before halting rather than the maximum finite number of steps of computation. The argument would work for the other flavor of Busy Beaver though.

Kranar 4y ago

Don't think this article is correct when it says that Omega can't be computed to arbitrary precision, it certainly can be. While it's true that there is no algorithm that can compute BB(n) for all n, it is always possible to compute BB(k) for a specific and arbitrary k. This is a very subtle detail. Similarly for Omega, while there's no algorithm that can compute Omega to an arbitrary precision, that is not the same as saying that there's some upper bound on the precision that Omega can be computed. For any precision k, it's possible to compute Omega up to that precision. The issue is that whatever algorithm you devise to compute Omega up to a precision of k, that algorithm will fail to compute Omega for some other precision q > k. You will need a fundamentally different algorithm for q > k, but such an algorithm does exist. You'll also need a fundamentally different algorithm for precision r > q, but that also exists... ad infinitum.

dllthomas 4y ago
> it is always possible to compute BB(k) for a specific and arbitrary k How do you do that once k is large enough that it admits Turing machines whose halting behavior is independent of our axioms?
- vainguard 4y ago
  BB(k) for a specific k is just a number. Ao just write it to the output. Proofing correctness is different from „computing“ and not required here.
  - puffoflogic 4y ago
    > BB(k) for a specific k is just a number. That's not as obvious as you might think. The value of BB(800) is independent of ZFC. So it isn't "just a number" if you're working in ZFC.
    - dllthomas 4y ago
      Hmm... As ZFC specifically cannot identify that number as special (at least as relates to the Busy Beaver function), maybe it is quite specifically "just a number"!

kotlin2 4y ago

I'm unfamiliar with BB(n), so this raises an interesting question for me. How do we know that BB(n) exists for all n? This is relevant to this post because the author's definition of omega relies on BB(n) being defined for all n. Obviously there are numbers that are not computable, but it seems one needs to be careful that the numbers discussed are sure to exist.

morelisp 4y ago
> How do we know that BB(n) exists for all n? It's trivial to construct a candidate for each n, which gives a lower bound.
nimih 4y ago
> How do we know that BB(n) exists for all n? What would it mean for BB(n) to "not exist"? Recall that BB(n) is defined in a very concrete way: you take all the Turing machines of size n (which are easily enumerable combinatorial objects), remove ones which do not halt, then take the largest runtime of the ones that are left. Since we can always write down a Turing machine which halts immediately, we know that there's a trivial lower bound for each BB(n), and since the Turing machines are deterministic, we know that any machine that halts must do so in a fixed number of steps. With such a straightforward construction, it's hard to see how such a number could "not exist," at least not without appealing to an ontology somewhat outside of the mainstream (e.g. ultrafinitism).
- kotlin2 4y ago
  In the proof you just provided, you have a step "remove ones which do not halt". By which process do you do that? By the halting-problem, you can't actually make that selection. This ties back into the fact that BB(n) is not computable for all n. I guess what I'm looking for is a proof that the number exists without violating the halting problem. Intuitively, we feel BB(n) should exist because there are finite turing machines with n states. But I'm not sure how to express that rigorously. Or maybe relying on a solution to the halting problem doesn't matter in terms of a proof.
  - 4y ago

zokier 4y ago

I feel the article is mixing up S(n) (max number of steps) and Σ(n) (max number of 1s written), going by the wikipedia article of BB https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver Notably the list of BB numbers in the article matches the values of S(n) in wikipedia instead of Σ(n). Also this sentence makes more sense if you replace Σ(n) with S(n) > If after these steps the program hasn’t halted it means it’ll never halt (by the definition of the Σ(n)).

alexmolas 4y ago
Oh yeah, you're right, I mixed up the terms. I just started learning about this topic and I got excited and wrote the post. I'll fix it ASAP. Thank you very much for spotting it :)

lcuff 4y ago

The code he gives, and the explanation of the busy beaver problem, strikes me as pretty poorly explained. If I didn't already know about the busy beaver problem, I don't think I could get it from this explanation.

alexmolas 4y ago
hi, author here! Thanks for your comment. Which where the parts that are poorly explained? I would love to get some feedback from you. I just started learning about computability theory, so maybe I explained some concepts wrong. Also, english is not my first language, so perhaps I lost something in translation. Thanks :)

aaplok 4y ago

> since we don’t know Σ(n) we can’t know the exact value of Ω. Hmmm. Just because you don't know the individual terms of the sequence, it doesn't follow that you don't know their infinite sum. Here's a trivial example: take the sum `(-1)^n Σ(floor(n/2))`. The infinite sum is obviously 0, yet we can't calculate each of the terms, nor many of the partial sums.

alexmolas 4y ago
> Just because you don't know the individual terms of the sequence, it doesn't follow that you don't know their infinite sum Yes, this is not true in general. But I think it's true for the specific definition of Ω we use in the post.
- aaplok 4y ago
  Intuitively I'd say you're probably right. But computation theory is full of counter-intuitive results. Your statement might be provable by adapting the argument that Σ(n) is not always computable. Something like computing the sum would require solving some version of the halting problem. Perhaps add a small edit to your article to highlight that this particular statement isn't to be taken as a mathematical proof?