Understanding busy beavers (noncomputability)

[martix]

TL;DR Summary

It is said that the busy beaver function is noncomputable. I want to understand what that means.

An ill advised late night plunge into a math rabbit hole left me confused. It started with Graham's number and ended with me trying to understand what noncomputable numbers and functions are. I'm not ready to tackle things like Rayo's number or SGC(n), but I did come across something that seemed fairly simple - the busy beaver game.

It is said that the busy beaver function is noncomputable. I want to understand what that means.
My current understanding is that the function is noncomputable because the halting problem is embedded within.

Here is my current understanding, gleaned from the wikipedia article:
We have n - the number of states in a 2-symbol turing machine (0 and 1)
Σ(n), the busy beaver function gives us that turing machine that outputs the most 1s out of all n-state 2s machines.

The number of 2s machines with n states is finite - (4n + 4)^2n.

Based on the definition of the game, these finite machines can be split in 2 categories/sets:
Machines that halt
Machines that don't halt.

From this point alone, it seems clear to me why Σ(n) is noncomputable - while the categories are valid, a general way to decide which machine goes into which set is impossible to construct.
(Anything wrong with my reasoning so far?)

Here is where my confusion starts.

Wikipedia states that an algorithm to decide whether a given machine is a busy beaver cannot exist ("general algorithm" being the precise wording, don't know if it matters).

But... what if we take all (4n + 4)^2n machines with n states and run them in parallel. We already have infinite tape - what's stopping us from running them for an infinite amount of time? Doesn't this qualify as an algorithm? Or is there something about requiring infinite time that disqualifies something from being an algorithm, whereas requiring infinite space does not?

Or, even if we don't run them for an infinite amount of time, just a sufficiently large amount of time, I would expect to end up in one of 2 situations in a finite amount of time:
1. Machine halts
2. Machine enters a loop

At the point where we determine the loop of each machine that has one, we have "computed" the busy beaver function.

The one hiccup I can think of here is, if it's possible to run forever without entering some sort of loop, but I personally can't conceive how.

Another final confusion is what is meant by "state" of a turing machine. It's not the arrangement of 1s and 0s on the tape so far as I can determine. My current best guess is that a "state" is 1 row in the transition table of the machine.

 

[TeethWhitener]

The busy beaver is the longest running n-state machine that halts. We can look at all the machines one by one, but there’s no general algorithm to determine whether a given machine halts. Also, it’s certainly possible for machines to loop, but the loops can be arbitrarily long. So we can’t compute in general whether we’ve found the busy beaver without solving the halting problem.

Summary:: It is said that the busy beaver function is noncomputable. I want to understand what that means.

Another final confusion is what is meant by "state" of a turing machine. It's not the arrangement of 1s and 0s on the tape so far as I can determine. My current best guess is that a "state" is 1 row in the transition table of the machine.

I’d have to see a specific example to understand what you mean by “row” (e.g., one table in the link has the states arranged in columns). A state is basically a series of actions that the machine takes when presented with a tape symbol. So a 2-state machine might be:
State 1:
if tape symbol = 0 then
Replace 0 with 1, move the tape head to the right, change to state 2.
if tape symbol = 1 then
Leave the 1 alone, move the tape head to the left, change to state 2.
State 2:
If tape symbol = 0 then
Replace 0 with 1, move the tape head to the right, change to state 1.
if tape symbol = 1 then
Leave the 1 alone, move the tape head to the left, halt.

The halt state isn’t generally counted when talking about an n-state machine, which makes it a little confusing.

 

[fresh_42]

I would concentrate on the impossibility of computably enumerability.
I have found some proofs. Maybe one of them gives you more insights than the Wikipedia article:
https://web.stanford.edu/class/cs54n/handouts/15-UncomputableFunctions.pdf
https://homepages.hass.rpi.edu/heuv...Web/Presentations/The Busy Beaver Problem.pdf
http://mca.ignougroup.com/2017/01/solved-understanding-proof-for-busy.html
and an interesting article about BB(n) in general:
https://www.scottaaronson.com/papers/bb.pdf