5 ms·

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 seg

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

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.

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