6 ms·

> it's not at all obvious to me that the set of axioms would be finite or even computable The reasoning is representable with and by a finite number of element

> it's not at all obvious to me that the set of axioms would be finite or even computable The reasoning is representable with and by a finite number of elementary physical particles and so must itself be finite. Because it is finite it is computable. Said another way, you would need an infinitely large brain (or an infinitely deep one) to create infinite reasoning.

bubblyworld 2y ago
I think that doesn't work, because we don't know how to represent and predict the state of a cloud of elementary particles to that level of detail. You could argue that the mathematics proves that this is possible in principle, but I counter that you have no idea whether the theory extrapolates to such situations in real life because it is way out of humanity's compute budget to test. Like the rest of physics, I expect new regimes would come with new phenomena that we don't understand.
eru 2y ago
> Because it is finite it is computable. Busy Beaver numbers are finite, but not computable.
- rstuart4133 2y ago
  The Busy Bever numbers may be finite, but the machine (specifically its tape) that produces them is not. If the Busy Bever is running on a Turing machine with a finite tape length the number becomes computable. Turning it around, the answer to "can a machine of infinite size do things a finite computer can't" is "yes". That answer ends up being the reason many things aren't computable, including the halting problem. The halting problem is a trick in disguise. The trick is: no one said the program you are checking halts had to have finite code, or finite storage. Once you see the trick the halting problem looses a lot of its mystique.
  - bubblyworld 2y ago
    I'm not sure what you mean here - the Turing machine that represents a particular BB number halts by definition, which means that it can only visit a finite segment of the tape. Nevertheless BB numbers are incomputable in general. On your second point - allowing infinitely many steps of computation lets you solve the halting problem for regular Turing machines, but you still get an infinitary version of the halting problem that's incomputable (same proof more or less). So I don't think that's really the issue at stake.
    - rstuart4133 2y ago
      The difficulty of the problem is not determined by the answer. The Busy Bever's case the answer could be the number or the number of states in its code. Yes, they are both finite, but that doesn't matter. The difficulty of a problem (which is the time required to find it) is determined by how many possibilities you have to explore. Since Busy Bever is defined in terms of the number of 1's on a tape when it halts, a "possibility" is how many arrangements of 1's a Turing tape can support. As a Turing tape is infinitely long, the answer is it supports an infinite number of arrangements of 1's. This all follows from the definition of "not computable". We say a problem isn't computable if we can't find the the answer with a finite sized program, using finite space. It's not an unreasonable definition. How else could you define it? That definition does leave out the number of steps needed to find the solution. The OP's assertion above is that if the both the program and the space is finite, then the number of steps must also be finite or it must loop forever. I'll leave looking up why as a exercise for the reader. (The proof is pretty simple. It's only a few lines long.) That means in a finite system there is no "halting problem" because looping is easy enough to detect when it happens, and you will either eventually see the program loop or halt because there are no other possible outcomes. "Non-computable" therefore means "oops we hit an infinity". Twisting that around, if we decide something isn't computable an infinity must have snuck into the problem somehow. All the proofs you see demonstrating something is non-computable on a Turing machine happen because the infinite thing sneaking in is it's tape. Restrict the Turing tape to being finite, and every problem that can be solved on it is computable. If you want to see how this works in a practical sense, consider BusyBever(6). It's possible we will never solve it because to solve it you need to solve the Collatz Conjecture. The conjecture is simple: if you repeatedly replace a positive integer x by x/2 if x is even or 3x+1 if x is odd, you’ll always eventually reach x=1. It's easy to disprove: all you have to do is find a counter example. None has been found of course, but that doesn't mean much because there are infinite numbers to check and infinite means non-computable. But what if we remove the infinity? Lets just insist x < N, where N is an integer. Then the Collatz Conjecture becomes solvable, and if BusyBever(6) doesn't contain another such puzzle it becomes solvable too.
  - jakelazaroff 2y ago
    I mean, any given Turing machine has finite code. But with even a very small number of states you start getting into crazy territory. We’ve constructed Turing machines with fewer than 800 states that halt if and only if ZFC is inconsistent. Which means that even given infinite time and space, we still couldn’t find BB(800) without fundamentally changing our system of mathematics.
- roenxi 2y ago
  True but not relevant. In this case "it" is the number of states of a finite volume that we believe to be fundamentally quantised. Borealid isn't saying that any finite output is computable, but that outputs of this specific thing is computable because as far as we know it has a finite number of states. This implies that brains can't compute the general nth BB function which is also true as far as we know.
  - bubblyworld 2y ago
    I don't think this argument holds water for a number of reasons: 1. It is an unknown whether a finite volume of space can fundamentally be described by a finite number of states. You can extrapolate to this situation from your favourite theory, but this is not evidence that reality actually works like that. Physics has a long way to go to understand space-time completely. 2. Even assuming that is true, brains are not isolated systems. They are entangled with their environment. Why are you so sure that human cognition can be neatly separated into a finite box like this? The reality is almost certainly more complicated. 3. Lastly, you cannot measure a system like the brain to fundamental levels of detail without destroying it. You literally cannot clone a brain state if you take modern physics seriously, so this whole thing is a non-starter anyway.
    - eru 2y ago
      About 1, see https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound seems You are right that we don't have a theory of everything. However, we can go pretty far with what we have and some clever reasoning. Eg when you have two different gases, like hydrogen and helium, in separate containers and mix them, you can build a relatively simple engine to extract work from that mixing. That engine also works when your gasses are almost but not quite the same, eg when you have deuterium and hydrogen. But it doesn't work, when you have the same gas, like hydrogen in both sides. That gives a pretty strong hint that hydrogen atoms 'have no hair', ie they are all the same.
      - bubblyworld 2y ago
- Borealid 2y ago
  The Busy Beaver game is finite in space, but infinite in time. If you restrict the execution to a finite amount of runtime, it becomes computable. An immortal human might be able to produce incomputable reasoning, but I would say it's more reasonable to talk about humans with finite runtime.
  - eru 2y ago
    > The Busy Beaver game is finite in space, but infinite in time. Sorry, I have a hard time understanding this. Are we talking about the same thing? https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver The Busy Beaver deals with two kinds of programs: those that can use infinite amounts of time and space, and those that only use finite amounts of time (and thus also only finite amounts of space). As far as I can tell, there's no place in the Busy Beaver ever, where space is finite but time is infinite. And in any case, if your space is finite, you don't need infinite time: you 'trivially' can detect that you are reaching a tape state that you have reached before and abort. The busy beaver is harder than that.
    - jakelazaroff 2y ago
      Here's a Turing machine that uses finite space but infinite time: https://samwho.dev/christopher/?code=H4sIAAAAAAAAE8tNzMxTqFHQUqhRCNAw1FQIUtC1UyhKLSktyuOCUHBZA00FH5BsbmJmHgBlULd%2BNwAAAA%3D%3D https://samwho.dev/christopher/?code=H4sIAAAAAAAAE8tNzMxTqFH... (from Sam Rose's wonderful article on Turing machines [1]) Your last point is correct, though: if you can detect a "cycle" (like the one the Turing machine I linked to goes through) then you can conclude that the machine won't halt. [1] https://samwho.dev/turing-machines/ https://samwho.dev/turing-machines/
      - eru 2y ago
        Yes, it's trivial to write a Turing machine that only uses finite space but infinite time. But as you agree, they are of no concern for the computability of Busy Beaver numbers. (However, they are of major concern for people who want to find Busy Beaver numbers in practice.)
foobarian 2y ago
> The reasoning is representable with and by a finite number of elementary physical particles Do we even know this much?
- traverseda 2y ago
  I'm sorry you had to find out this way but no, souls aren't real.
  - mrybczyn 2y ago
    Show me the experimental results...
    - Xunjin 2y ago
      Well, I could argue the contrary, show that souls are real with experimental results! Your argument, might not be your intention, infer that just because you can't prove X thus Y exist.
      - costigan 2y ago
        The commenter's point was to disagree with the previous comment that "souls aren't real". Lack of evidence either way means we don't know. Occam's razor, while a good heuristic, is a heuristic, not a theorem.
    - sorokod 2y ago
      That result is stashed in a small china teapot that is orbiting the sun.
    - GoblinSlayer 2y ago
      Even according to platonism souls are forms and forms are described by science. The only difference is that forms are substance and can exist detached from matter, but this doesn't affect computability. Moreover, mathematics is epitome of eidos.

bubblyworld 2y ago

I think that doesn't work, because we don't know how to represent and predict the state of a cloud of elementary particles to that level of detail. You could argue that the mathematics proves that this is possible in principle, but I counter that you have no idea whether the theory extrapolates to such situations in real life because it is way out of humanity's compute budget to test. Like the rest of physics, I expect new regimes would come with new phenomena that we don't understand.

eru 2y ago

> Because it is finite it is computable. Busy Beaver numbers are finite, but not computable.

rstuart4133 2y ago
The Busy Bever numbers may be finite, but the machine (specifically its tape) that produces them is not. If the Busy Bever is running on a Turing machine with a finite tape length the number becomes computable. Turning it around, the answer to "can a machine of infinite size do things a finite computer can't" is "yes". That answer ends up being the reason many things aren't computable, including the halting problem. The halting problem is a trick in disguise. The trick is: no one said the program you are checking halts had to have finite code, or finite storage. Once you see the trick the halting problem looses a lot of its mystique.
- bubblyworld 2y ago
  I'm not sure what you mean here - the Turing machine that represents a particular BB number halts by definition, which means that it can only visit a finite segment of the tape. Nevertheless BB numbers are incomputable in general. On your second point - allowing infinitely many steps of computation lets you solve the halting problem for regular Turing machines, but you still get an infinitary version of the halting problem that's incomputable (same proof more or less). So I don't think that's really the issue at stake.
  - rstuart4133 2y ago
    The difficulty of the problem is not determined by the answer. The Busy Bever's case the answer could be the number or the number of states in its code. Yes, they are both finite, but that doesn't matter. The difficulty of a problem (which is the time required to find it) is determined by how many possibilities you have to explore. Since Busy Bever is defined in terms of the number of 1's on a tape when it halts, a "possibility" is how many arrangements of 1's a Turing tape can support. As a Turing tape is infinitely long, the answer is it supports an infinite number of arrangements of 1's. This all follows from the definition of "not computable". We say a problem isn't computable if we can't find the the answer with a finite sized program, using finite space. It's not an unreasonable definition. How else could you define it? That definition does leave out the number of steps needed to find the solution. The OP's assertion above is that if the both the program and the space is finite, then the number of steps must also be finite or it must loop forever. I'll leave looking up why as a exercise for the reader. (The proof is pretty simple. It's only a few lines long.) That means in a finite system there is no "halting problem" because looping is easy enough to detect when it happens, and you will either eventually see the program loop or halt because there are no other possible outcomes. "Non-computable" therefore means "oops we hit an infinity". Twisting that around, if we decide something isn't computable an infinity must have snuck into the problem somehow. All the proofs you see demonstrating something is non-computable on a Turing machine happen because the infinite thing sneaking in is it's tape. Restrict the Turing tape to being finite, and every problem that can be solved on it is computable. If you want to see how this works in a practical sense, consider BusyBever(6). It's possible we will never solve it because to solve it you need to solve the Collatz Conjecture. The conjecture is simple: if you repeatedly replace a positive integer x by x/2 if x is even or 3x+1 if x is odd, you’ll always eventually reach x=1. It's easy to disprove: all you have to do is find a counter example. None has been found of course, but that doesn't mean much because there are infinite numbers to check and infinite means non-computable. But what if we remove the infinity? Lets just insist x < N, where N is an integer. Then the Collatz Conjecture becomes solvable, and if BusyBever(6) doesn't contain another such puzzle it becomes solvable too.
- jakelazaroff 2y ago
  I mean, any given Turing machine has finite code. But with even a very small number of states you start getting into crazy territory. We’ve constructed Turing machines with fewer than 800 states that halt if and only if ZFC is inconsistent. Which means that even given infinite time and space, we still couldn’t find BB(800) without fundamentally changing our system of mathematics.
roenxi 2y ago
True but not relevant. In this case "it" is the number of states of a finite volume that we believe to be fundamentally quantised. Borealid isn't saying that any finite output is computable, but that outputs of this specific thing is computable because as far as we know it has a finite number of states. This implies that brains can't compute the general nth BB function which is also true as far as we know.
- bubblyworld 2y ago
  I don't think this argument holds water for a number of reasons: 1. It is an unknown whether a finite volume of space can fundamentally be described by a finite number of states. You can extrapolate to this situation from your favourite theory, but this is not evidence that reality actually works like that. Physics has a long way to go to understand space-time completely. 2. Even assuming that is true, brains are not isolated systems. They are entangled with their environment. Why are you so sure that human cognition can be neatly separated into a finite box like this? The reality is almost certainly more complicated. 3. Lastly, you cannot measure a system like the brain to fundamental levels of detail without destroying it. You literally cannot clone a brain state if you take modern physics seriously, so this whole thing is a non-starter anyway.
  - eru 2y ago
    About 1, see https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound seems You are right that we don't have a theory of everything. However, we can go pretty far with what we have and some clever reasoning. Eg when you have two different gases, like hydrogen and helium, in separate containers and mix them, you can build a relatively simple engine to extract work from that mixing. That engine also works when your gasses are almost but not quite the same, eg when you have deuterium and hydrogen. But it doesn't work, when you have the same gas, like hydrogen in both sides. That gives a pretty strong hint that hydrogen atoms 'have no hair', ie they are all the same.
    - bubblyworld 2y ago
Borealid 2y ago
The Busy Beaver game is finite in space, but infinite in time. If you restrict the execution to a finite amount of runtime, it becomes computable. An immortal human might be able to produce incomputable reasoning, but I would say it's more reasonable to talk about humans with finite runtime.
- eru 2y ago
  > The Busy Beaver game is finite in space, but infinite in time. Sorry, I have a hard time understanding this. Are we talking about the same thing? https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver The Busy Beaver deals with two kinds of programs: those that can use infinite amounts of time and space, and those that only use finite amounts of time (and thus also only finite amounts of space). As far as I can tell, there's no place in the Busy Beaver ever, where space is finite but time is infinite. And in any case, if your space is finite, you don't need infinite time: you 'trivially' can detect that you are reaching a tape state that you have reached before and abort. The busy beaver is harder than that.
  - jakelazaroff 2y ago
    Here's a Turing machine that uses finite space but infinite time: https://samwho.dev/christopher/?code=H4sIAAAAAAAAE8tNzMxTqFHQUqhRCNAw1FQIUtC1UyhKLSktyuOCUHBZA00FH5BsbmJmHgBlULd%2BNwAAAA%3D%3D https://samwho.dev/christopher/?code=H4sIAAAAAAAAE8tNzMxTqFH... (from Sam Rose's wonderful article on Turing machines [1]) Your last point is correct, though: if you can detect a "cycle" (like the one the Turing machine I linked to goes through) then you can conclude that the machine won't halt. [1] https://samwho.dev/turing-machines/ https://samwho.dev/turing-machines/
    - eru 2y ago
      Yes, it's trivial to write a Turing machine that only uses finite space but infinite time. But as you agree, they are of no concern for the computability of Busy Beaver numbers. (However, they are of major concern for people who want to find Busy Beaver numbers in practice.)

foobarian 2y ago

> The reasoning is representable with and by a finite number of elementary physical particles Do we even know this much?

traverseda 2y ago
I'm sorry you had to find out this way but no, souls aren't real.
- mrybczyn 2y ago
  Show me the experimental results...
  - Xunjin 2y ago
    Well, I could argue the contrary, show that souls are real with experimental results! Your argument, might not be your intention, infer that just because you can't prove X thus Y exist.
    - costigan 2y ago
      The commenter's point was to disagree with the previous comment that "souls aren't real". Lack of evidence either way means we don't know. Occam's razor, while a good heuristic, is a heuristic, not a theorem.
  - sorokod 2y ago
    That result is stashed in a small china teapot that is orbiting the sun.
  - GoblinSlayer 2y ago
    Even according to platonism souls are forms and forms are described by science. The only difference is that forms are substance and can exist detached from matter, but this doesn't affect computability. Moreover, mathematics is epitome of eidos.