4 ms·
> Because it is finite it is computable. Busy Beaver numbers are finite, but not computable.
by eru 2y ago
> Because it is finite it is computable.
Busy Beaver numbers are finite, but not computable.
- rstuart4133 2y agoThe 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 agoI'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 agoThe 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.
- eru 2y ago> 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? https://en.wikipedia.org/wiki/Computability https://en.wikipedia.org/wiki/Computability has a bunch of definitions. Btw, your reasoning is not really valid. There's plenty of Turing machines that print out lots of 1s (either finite or infinite), where we can accurately predict in finite time how many it will print out. (To fill out the details: crucially the prediction runs much faster than the original machine, and you can assume that we give that answer in eg binary numbers, so we can write it down more compactly than in unary). > 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. Please be very careful about distinguishing a system with a fixed upper limit from one that can be arbitrarily big but finite. Also be careful, the opposite of your assertion doesn't hold: even an arbitrarily extendable tape doesn't mean that the halting problem must be a problem. As a last caveat: just because the definition of your problem uses infinity (or the limit of an infinite process, etc) doesn't mean that infinity is inherent to what you are defining. Eg 1 + 1/2 + 1/4 + 1/8 + ... is the sum of an infinite series, but you might be aware that we can calculate the result with a finite computation. Similarly, the classic definition of Busy Beaver numbers mentions infinity, but that doesn't automatically mean all means of arriving at these numbers have to involve infinite processes. > [...] infinite means non-computable. No. Not at all. You argued that non-computable implies an infinity somewhere, and I can grant that. But the reverse is not true. There's lots of variants of that Collatz conjecture with slightly different rules that also cover all numbers, and that we can definitely prove or disprove. Or more trivially: take any old mathematical statement over all natural numbers. Many of them can be proven true or false, despite the infinity.
- rstuart4133 2y ago
- jakelazaroff 2y agoI 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 agoTrue 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 agoI 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 agoAbout 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 agoThe 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 agoHere'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 agoYes, 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.)