|
|
|
|
|
|
by westoncb
3130 days ago
|
|
|
Cool idea! There were a couple points in the explanation which were kind of unclear to me, though: What makes it okay to identify the naming of a large number with producing that large number of things (e.g. 1's)? This felt like a disconnect to me since in the introduction we are asked the largest number we can write down in 15 seconds, but my understanding is that the Busy Beaver functions aren't 'naming a number', but instead we're counting the number of 1's output by them (or maybe the function returns the number of ones rather than the string itself?). Actually, I think I'm starting to see the connection now: if we're considering the mathematical function rather than an executing program, then it just 'instantaneously' gives back a single number, and that single number is whatever sequence of ones the Turing machine would produce, which we could interpret as a reference to a numeric value rather than counting the digits? Maybe still a bit lost. Another way of stating my confusion: a person could easily write down a number larger than the number of 1's output by the 7-state solution (102*10^10^10^1870532) within 15 seconds (I could write that number down in maybe 5 seconds or so)—so in what sense is the Busy Beaver function naming a larger number? There was another thing that tripped me up for a while, though I think I get it now, which was: what characterizes the Busy Beaver function? Is it that it "returns the maximum of the running times of all programs of length n that do eventually halt"—or is it that it "counts the number of 1's possible to be written by an n-state Turing machine before it halts"? It's pretty clear to me now that it's the latter, and that the former (the BBS function) is just one implementation of the general concept, but it gave me some trouble to figure that out. |
|
|
Nice catch! I glossed over this but this is pretty important. The issue is that for any _specific number_, it takes a constant amount of time to write a number larger than that. Related: solving chess is technically O(1) since there are a constant number of positions we have to check.
What we need instead for this concept is a series of numbers, those can be compared with the question "Does one eventually get to a point where it will always be larger than the second?". We can parametrize the "biggest number" by the number of seconds given, say we can write down one character per second. Then a person's largest number function might be something like "f(n) = 9 ^ n", which is easy to see _is_ a computable function, and thus smaller than BB(n) for the same number of seconds, eventually.
In practice, just something like BB(100) - or BB(BB(100)), even can't really be written out by any computable method in a finite amount of time.
> which was: what characterizes the Busy Beaver function?
The proper one is just the number of 1s, but I talked about the shift function because it's easier to see why it's uncomputable. Tibor Rado proved that the Busy beaver function is also uncomputable in his 1962 paper, if you're interested you could check out his reduction.