> 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?
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.
> 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.
The reasoning is not-computable implies an infinity. As you know "implies" is not reflexive, so no I wasn't intending to say the reverse.
> > [...] infinite means non-computable.
You didn't quote the full sentence. It was "because there are infinite numbers to check and infinite means non-computable". Being forced to check an infinite number of possibilities is one definition of non-computable, as you acknowledged.
> The reasoning is not-computable implies an infinity. As you know "implies" is not reflexive, so no I wasn't intending to say the reverse.
OK, but you implied you were giving a definition? Definitions are usually two sided, where every 'if' is silently implied to be an 'iff' for convenience.
> You didn't quote the full sentence. It was "because there are infinite numbers to check and infinite means non-computable". Being forced to check an infinite number of possibilities is one definition of non-computable, as you acknowledged.
Not really. You'd need to prove that you actually need to check the numbers. We need to exclude that we just lacked the right idea.
Eg it fairly easy to prove that there's an infinite amount of prime numbers without having to check all numbers. It was a lot harder to prove Fermat's Last Theorem without checking all the numbers. For the Collatz conjucture, we don't know.
Why I did acknowledge was that _if_ you can prove an upper bound, then checking all numbers is computable, yes.
But if we haven't found an upper bound (yet), we have no clue whether the problem is computable or not.
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.