Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A number that can't be calculated

amolas.dev

Post reply on HN
Print view View original

71–79 of 79 posts

Re: A number that can't be calculated

#71

Post by dllthomas »

puffoflogic wrote: post #69
vainguard wrote: post #37

Earlier quoted context omitted.

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.

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

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

Re: A number that can't be calculated

#72

Post by dllthomas »

vainguard wrote: post #37
dllthomas wrote: post #21

Earlier quoted context omitted.

> 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?

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.

Ah, so pointing out that the number itself, being an integer, is computable even though the function isn't. Makes sense.

Re: A number that can't be calculated

#73

Post by Kranar »

alexmolas wrote: post #38
Kranar wrote: post #31

Earlier quoted context omitted.

If you recall from predicate logic, these two statements are not the same: 1) For all Turing Machines A, there exists a Turing Machine M such M can compute whether A halts. 2) There exists a Turing Machine M such that for all Turing Machines A, M can compute whether A halts. Statement 1 is true, statement 2 is false. You can apply a similar reasoning to BB(n) or your notion of Omega. For any particular choice of n, t…

But imagine that we could compute BB(n) for any n, even if we need to use a different algorithm for each n. Then, we could build the mapping n -> BB(n). But the existence of this mapping is forbidden by the unsolvability of the Halting Problem, isn't it?

No you can't conclude this and in fact the more general principle is that being able to prove P(0), P(1), P(2), etc... does not mean that it's also possible to prove P(n) for all n. The property of a formal system for which this does follow is known as Omega completeness, but Peano arithmetic and ZFC more broadly are both Omega-incomplete systems, hence there are propositions for which P(0), P(1), P(2)... can all individually be proven and yet it is not possible to prove P(n) for all n.

Wikipedia touches on this subject with an article on omega-consistent systems, which is a very closely related property:

https://en.wikipedia.org/wiki/%CE%A9-consistent_theory

And this gives a very brief description of Omega completeness:

https://encyclopediaofmath.org/wiki/Omega-completeness

Re: A number that can't be calculated

#74

Post by singularity2001 »

VyseofArcadia wrote: post #12

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/Compu…

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.

Re: A number that can't be calculated

#75

Post by gotthetshirt »

Kranar wrote: post #46
gotthetshirt wrote: post #44

Earlier quoted context omitted.

No, you cannot compute BB(k) for a given k. https://scottaaronson.blog/?p=2725

I love that article but that does not state what you are claiming it does. What that states is that there exists a k (whose upper bound is 8000) whose solution is independent of ZFC. That does not mean it can't be computed. In the very comment section of that blog post someone brings this issue up, and Scott himself says: "Yes, fine, you’re right, there’s not a single “boundary between the knowable and the knowable.”…

Suppose BB(8000) could be computed: 1) Compute BB(8000). 2) Run the program specified in the article until it either halts or it runs for BB(8000)+1 steps. 3) We then know if the program ever halts, and then have a proof within ZFC whether or not ZFC is sound.

Re: A number that can't be calculated

#76

Post by Kranar »

gotthetshirt wrote: post #75
Kranar wrote: post #46

Earlier quoted context omitted.

I love that article but that does not state what you are claiming it does. What that states is that there exists a k (whose upper bound is 8000) whose solution is independent of ZFC. That does not mean it can't be computed. In the very comment section of that blog post someone brings this issue up, and Scott himself says: "Yes, fine, you’re right, there’s not a single “boundary between the knowable and the knowable.”…

Suppose BB(8000) could be computed: 1) Compute BB(8000). 2) Run the program specified in the article until it either halts or it runs for BB(8000)+1 steps. 3) We then know if the program ever halts, and then have a proof within ZFC whether or not ZFC is sound.

No, what you will have is a proof that ZFC is sound but that proof will not be within ZFC. That proof will rely on additional axioms that are extensions to ZFC.

Re: A number that can't be calculated

#77

Post by gotthetshirt »

Kranar wrote: post #76
gotthetshirt wrote: post #75

Earlier quoted context omitted.

Suppose BB(8000) could be computed: 1) Compute BB(8000). 2) Run the program specified in the article until it either halts or it runs for BB(8000)+1 steps. 3) We then know if the program ever halts, and then have a proof within ZFC whether or not ZFC is sound.

No, what you will have is a proof that ZFC is sound but that proof will not be within ZFC. That proof will rely on additional axioms that are extensions to ZFC.

Well, OK, I suppose you could add something like 'BB(8000) is 6,' but once you go beyond ZFC, you're going beyond anything required for computation as we know it.

Re: A number that can't be calculated

#78

Post by Kranar »

gotthetshirt wrote: post #77
Kranar wrote: post #76

Earlier quoted context omitted.

No, what you will have is a proof that ZFC is sound but that proof will not be within ZFC. That proof will rely on additional axioms that are extensions to ZFC.

Well, OK, I suppose you could add something like 'BB(8000) is 6,' but once you go beyond ZFC, you're going beyond anything required for computation as we know it.

No this is also wrong. You would not be able to add an axiom like 'BB(8000) is 6' or just any arbitrary value without introducing an inconsistency. The reason for the independence of BB(8000) from ZFC is precisely because there is some non-standard model of arithmetic for which a Turing Machine halts in that non-standard model but does not halt in the standard model.

The only axioms you could introduce to ZFC that would not introduce an inconsistency would be one that eliminates that non-standard model of arithmetic without also eliminating the standard model of arithmetic.

https://en.wikipedia.org/wiki/Non-standard_model_of_arithmet...

None of this requires going beyond any kind of notion of computation and any value that is computed for one such extension would necessarily have to be the same value among all consistent extensions of ZFC. It's not like you could have one extension of ZFC where BB(8000) is X and another extension where BB(8000) is Y without one of those extensions being inconsistent.

There are plenty of extensions to ZFC that add new axioms for the sake of exploring niche mathematical ideas. ZFC is nice in that it's easily motivated and can serve as a well understood foundation whose proofs can be stated without reference to additional hypotheses. It also satisfies an unbelievably broad set of mathematics, but mathematicians studying set theory often extend ZFC with additional axioms such as large cardinal axioms, Neumann/Bernays/Godel (NBG) set theory is another common extension, Kelley Morse (KM) set theory. The latter two extensions are even able to prove the consistency of ZFC. As I referenced in Scott's quote, BB(8000) is almost certainly computable by adopting one of the large cardinal axioms.

Re: A number that can't be calculated

#79

Post by VyseofArcadia »

singularity2001 wrote: post #74
VyseofArcadia wrote: post #12

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/Compu…

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…

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.

Post reply on HN