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.

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.

(appreciate the background, but fyi I'm very familiar with the theory of computation)

I may have misunderstood what you meant when I replied.

I agree with basically everything you have written here in spirit, but I don't think "oops an infinity snuck in" is really a useful way to think about computability. There are lots of infinities that can be tamed by Turing machines, by a program that computes membership, for instance. The even numbers are a trivial example. The infinities of computation are asymptotic, not absolute - a Turing machine that solves a decision problem may use unbounded space as a function of input size, but this is not the same thing as literally using an infinite amount of space.

Restricting to finite tapes is pointless from a mathematical point of view, precisely because everything becomes computable in finite time/space.

> There are lots of infinities that can be tamed by Turing machines, by a program that computes membership, for instance.

To someone (which I assume covers most here) who are familiar with mid-level high school maths (calculus, infinite series) this is obvious, surely. We don't just tame infinities in maths and physics, we put them to work. You not only have to be aware of them, you have use them to get some important results. I doubt you would find someone willing to argue against this in mathematics.

The same statement is true in computing. You have to be aware of unwanted infinities. I'd lay long odds there are more programmers out there who have created unwanted infinite loops than there are maths students who have unwittingly divided by 0 and got a nonsensical result. Yet at the same time, infinities lie at the heart of some important results - like the halting problem. Everyone should be aware they are both a nuisance you don't want sneaking in unnoticed, and a very valuable tool.

> I agree with basically everything you have written here in spirit, but I don't think "oops an infinity snuck in" is really a useful way to think about computability.

I disagree. The halting program is one specific result. It is merely the outcome of a more fundamental idea. To wit, there are infinite states (think: infinite strings of bits) no finite program can describe (or equivalently reproduce, or recognise). It's one of those rare things that is hard to get your head around when you first hear it, then becomes obvious after a bit of thought. Somewhat less obvious, to me anyway, is the result applies even if you give that finite program infinite time and infinite space.

Like most fundamental ideas, it leads to other results with little effort. For example, if you view the finite program as a compressed version of the infinite space, it means some infinite spaces can not be compressed. This result is doubly interesting because it extends to finite systems, leading to linking of the seemingly disparate ideas of randomness, compression and computability. It also means if the universe has some infinity hiding inside it it's possible our finite minds can never understand it. It means you will never be able to write a finite program that proves some infinitely long programs halt. It almost certainly means there is an N above which BB(N) isn't computable, and from what we know now that N may be 6. It is why Gödel's theorem holds. Most of those things aren't near as easily deduced from the halting problem, which is why it isn't as useful understanding the effects of infinities on computability.

Above I think you are saying "but, but, introducing the idea that some infinities can be described might confuse some programmers. It may lead them to think a finite program can't describe an infinite series of 1's, for example". I'm not sure how many programmers you know, because in the world I live in not a single one would be confused by that. All are perfectly capable understanding some infinities can be described (not in the least because they've probably written a few by mistake) and this new idea some infinities can't be written down.

I don't know why you think I'm worried about confusing programmers? Did I say that?

My claim is that all of the results you are attributing to "infinity" are true for other reasons, like diagonalisation, and cannot be proven directly from the concept of infinity like you are claiming. It's a heuristic that is not helpful for actually doing the mathematics.

Feel free to prove me wrong by giving me a (mathematical, not hand waving) proof of the halting theorem that only makes use of "infinity" as you are describing it. You won't be able to do it, because it's not the crux of the halting problem. It holds for infinite programs too, because diagonalization arguments don't care how big your set is.

Anyway, I don't really have the energy for this. I appreciate the time and discussion, for which I thank you. But as someone who studied maths at a PhD level and now programs for a living, I'm not getting much out of these ideas. Perhaps we can just agree to disagree for now.

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

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

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.