Talk:Busy beaver
Page contents not supported in other languages.
Edit (29-12-15): The change has been applied. --Negrulio (talk) 01:33, 29 December 2015 (UTC)[reply]
Edit (28-12-15): I am going for this change tomorrow. --Negrulio (talk) 16:00, 28 December 2015 (UTC)[reply]
The current article introduction has several issues. I will first cite it and then I will enumerate the problems it has:
I propose the following introduction:
At the moment, only Σ (number of nonzeros in result) and S (number of steps taken) are mentioned. There are others that could be investigated:
.... -- Smjg 15:11, 27 September 2005 (UTC)[reply]
It says that there are [4(n+1)]^(2n) machines in this section... aren't there only [4n+2]^(2n)? Or are 1-left-halt and 1-right-halt different???
I happened upon the Sci Am refrences in an old notebook of mine; they are "unverified" in that I haven't laid eyes on them in 20-odd years. The Rado reference actually appears in Booth's references for his chapter 9 titled "Turing Machines". So it is "quasi-unverified" as well. I'm staring at the pages of the Booth book, so I guess we could argue that reference is verified.wvbailey22:08, 6 January 2006 (UTC)
The pdf is currently available at this URL:
https://www.cs.auckland.ac.nz/~chaitin/bellcom.pdf
I don't know how to properly edit references, sorry.
68.7.137.69 (talk) 04:32, 26 May 2016 (UTC)[reply]
The link to "The Busy Beaver Problem : A NEW MILLENNIUM ATTACK" is also broken — Preceding unsigned comment added by 199.203.204.197 (talk) 06:50, 28 June 2022 (UTC)[reply]
Maybe it can be replaced with https://homepages.hass.rpi.edu/heuveb/Research/BB/index.html ?Seems like the same referece in a different address — Preceding unsigned comment added by 199.203.204.197 (talk) 06:53, 28 June 2022 (UTC)[reply]
The article makes inconsistent use of "1's", "1s", and "ones" to refer to the plural of "1". How should this be standardized? Also, what is meant by the notation "SRTM(n)"? Pmdboi 14:24, 8 March 2006 (UTC)[reply]
In the statement about known values, there is a very strange usage of the reverse-superscript notation (which, if I understand correctly, connotes tetration). The reason I find it strange is that it's being mixed in with up-arrow notation which connotes the same thing. I find this to be a bad practice, as it should just be one or the other.From the up-arrow notation article:
But in the text we currently have a seemingly-unnecessary mixing of the two notations and a failure to identify the alternate form:
where is Knuth up-arrow notation and A is Ackermann's function.
If we stick to just one notation, it should be equivalent to either:
OR
Finally, I find the use of a single \quad
to be confusing (because it just looks like an extra space or so being added and still a multiply, as opposed to a clearer delimited) so I'd instead prefer something like:
I'll note that I'm not totally bent on this last modification if it's something that's really standard that I simply haven't seen or noticed before. Thanks. — Koyae (talk) 06:28, 25 December 2014 (UTC)[reply]
I have noticed a slight problem with this proof. It assumes the number of states required for EvalS is constant no matter the value of n0. What if the number of states required for EvalS varies according to n0? Perhaps the turing machine encoding of EvalS can be computed from n0?
I noticed that the artical states that the 2 symbol, 3 state value is 14 with six 1's printed, yet elsewhere I've seen a mention of "In 1965 Rado, together with Shen Lin, proved that BB(3) is 21." I don't have the knowledge of where to go look up that state machine or to find definitive proof either way, it was just something I caught looking at the wiki page and this other article. --72.94.0.116 (talk) 06:27, 22 March 2008 (UTC) (Draco18s)[reply]
Hi,
this article is pretty nice but it's very sophisticiated! I consider myself okay with maths and a minimum of computing but most of this goes over my head. Wikipedia should be accessible to laypeople, and even though it's hard when you're an expert and the audience is not, I think that the editors should dumb this down a little! If a middle school student who has no maths or computing skills cannot completely understand the article then it has no place in an encyclopedia! If something cannot be left out then include links as a minimum. -- ben 18:03, 11 July 2006 (UTC)[reply]
You are correct. The numbers 'explode' after 4 instructions (states). And "busy beavers" have no earthly use ... yet. But who can say? Someday something incredible may come from studying them. But "busy beavers" is a "hard" topic. The "busy beaver" challenges the very best computer scientists, folks who've had years experience working with computers. wvbailey
In The Busy Beaver game, Consider a Turing machine with the binary alphabet {0, 1} ... Now start with a blank tape (i.e. every cell has a 0 in it) and a TABLE of n instructions. is confusing in the context of the classic Turing machine that has an input alphabet Σ and a tape alphabet Г, with the latter containing the former plus (at least) a blank symbol. It seems that here we have a TM with a tape alphabet of {0, 1}, where 0 is the blank symbol. Of course we don't actually care about the input alphabet, as the input is effectively ε, but all of this should be made more clear. Pascal Michel's pages, referenced in the article, while not labouring the point, do explicitly state that 0 is the blank symbol.Onkelringelhuth 15:22, 27 January 2007 (UTC)[reply]
"Busy beavers" is a game. The goal? To find "the instructions" that cause you as the busy beaver to print the most ones on a piece of paper tape. But like all games there are rules, and to play, first you will need to learn them.
Rule #1: Know what a "two-symbol Turing machine" is. The Turing machine is NOT easy to understand. But think of it as a really weird, clunky, simple-minded calculating-machine, the most difficult-to-use pocket calculator on the planet, but the most powerful. It has a hugely-long piece of paper tape (marked off into "squares") running through it, and 4 buttons: PRINT, ERASE, LEFT ONE SQUARE, RIGHT ONE SQUARE, a robot that pushes the buttons, and a list of instructions called "the Table" that the robot must follow.
As a busy beaver you will be the robot. You have the tape running past you. You will have a list of instructions. You (as a two-state busy-beaver) can PRINT only 1's (tally marks) or ERASE them (in other words, make blanks, print 0's) on this all-blank (all-0's) tape. You can print or overprint, erase or overerase, but only one mark on one square at a time. You can move the tape only one square LEFT or RIGHT at a time. The tape is as long as you want it to be. If you would rather, you can use the push-button console rather than doing this by hand.
RULE #2: The busy beaver always follows its unchanging list of instructions. You will need to know how to read them and you must follow them without fail. See below, with an example.
RULE #3: Always obey rules #1 and #2. You are now a computer/robot, after all.
If you can do RULE #1, #2 and #3 without mistakes you too can leave the world of humans and join the ranks of the busy beavers!
Your mission:
Your mission (and your life) as a busy beaver will come in three parts:
Mission Part I:
Mission Part II:
Robots, your busy beaver trial is over. You have succeeded: you either came to HALT or you failed to HALT (how did we know this? -- ahh, that's an interesting question!), OR, you printed some ones. The score-keepers are standing by, ready to count your ones and record the instructions that you followed.
Mission Part III:
Repeat Part I and Part II forever! This is the life of a "busy beaver". Aren't you glad you're a robot and not a human!
>>>>>> <<<<<<<<
How to read busy beaver instructions:
Here is the instruction table for a 2-state Turing-machine busy beaver.
Current instruction A: | Current instruction B: | |||||
PRINT/ERASE: | Move tape: | Next state: | PRINT/ERASE: | Move tape: | Next state: | |
tape symbol is 0: | RIGHT | B | LEFT | A | ||
tape symbol is 1: | LeFT | B | NONE | H |
Busy beavers always start at "instruction A" with a blank tape (instructions are usually called "states" in Turing-world). The "HEAD" is where the scanned square is -- where your eye is looking (so "eye" might be a better word).
HEAD | At start of Instruction: | |||||||||
A |
In the instruction table, look down the column on the left. Is the scanned square (in the button console, or before you on the tape, beneath HEAD) blank (or 0), or does it have a 1 written there? It should be blank/0, because we're starting from scratch. Since it is blank/0, under A follow the top row from left to right and do the following in this order:
HEAD | At start of Instruction: | |||||||||
A | ||||||||||
1 | B |
At instruction B we look to see if the scanned symbol is a 1 or a blank/0. Since we know it is a blank/0, we follow the top row again, but under B, and do the following:
HEAD | At start of Instruction: | |||||||||
A | ||||||||||
1 | B | |||||||||
1 | 1 | A |
Now that we find that there's a 1 printed on the scanned square. So we follow the bottom row under A and find the instructions are:
HEAD | At start of Instruction: | |||||||||
A | ||||||||||
1 | B | |||||||||
1 | 1 | A | ||||||||
1 | 1 | B |
We continue this, when finally we hit the HALT instruction. We're done!:
HEAD | At start of Instruction: | |||||||||
A | ||||||||||
1 | B | |||||||||
1 | 1 | A | ||||||||
1 | 1 | B | ||||||||
1 | 1 | 1 | A | |||||||
1 | 1 | 1 | 1 | B | ||||||
1 | 1 | 1 | 1 | H |
You as a busy beaver have printed 4 ones. They didn't have to be all in a row, but indeed this is nice work. You have done as well as any "2-state 2-symbol busy beaver" can do. Now its time to go to a three state instruction. Robots: are you ready?
>>>>>> <<<<<<<<
An example of a "little" busy beaver -- a one, two, three, or four-state busy beaver -- can be "run" on any spreadsheet such as Excel. Five and six-state busy beavers cannot -- their "productions" -- the numbers of ones they can print -- are too huge to fit. You will need some help setting a model up. It will help you to know what the INDEX(....) instruction does (for example, INDEX(B5:B20,,A3)), but you can make a Turing machine on a spreadsheet without this. Still it's kind of tricky. For an example of what a busy beaver's "run" looks like, see Turing machine examples and Post-Turing machine.wvbaileyWvbailey 17:39, 8 September 2006 (UTC)[reply]
The following is a test-case to see what it looks like. It will look better with Netscape viewer. You can find the 2-state 2-symbol busy beaver at Post-Turing machine and as mentioned in the article, the 3-state 2-symbol busy beaver at Turing machine examples. wvbaileyWvbailey 20:37, 22 August 2006 (UTC)[reply]
wvbailey's example should go on the main page. The main page currently makes no sense to anyone who doesn't already understand the subject. His explanation and example was entirely understandable and at least allowed me to understand what was being described in the main article. Thanks for that wvbailey!
A few readers (see above) have requested that the article contain some context, explanation and example. I don't feel competent to address the more technical parts here (I could work on the historical -- I want to see Rado's paper, for example). I would suggest the following:
Suggestions? Comments? wvbaileyWvbailey 14:47, 15 September 2006 (UTC)[reply]
I've added quite a bit of new information based upon Rado's original paper and some of your comments on this talk page. I hope that this has made the page more readable and accessible. Because of the major content change, I have removed the Confusing tag on this page. I hope that you all will review the page to see if it ought to be put back or not. If you do have any comments or requests, I would be very interested in hearing them.
Happy Busy Beavering! Sligocki 17:30, 12 December 2006 (UTC)[reply]
The article states that though the busy beaver fonction itself is non-computable, any finite sequence Σ(0),...,Σ(n) is computable. Of course, this is true -- indeed, it is true for every finite set of natural numbers : the trivial algorithm which, on the input of n, prints the value Σ(n), solves the problem. To put it another way, it only means that Σ restricted to [1, N] can be described finitely -- which is obvious -- and nothing more : while it is not, theoretically, impossible to compute Σ(n) for some given n, we might never be able to, even with unimaginably powerful machines. The article arguably might suggest some kind of stronger property to a non-initiated reader. I'm trying to rephrase it carefully. Dabsent (talk) 11:12, 31 May 2008 (UTC)[reply]
Although Σ is a non-computable function, nevertheless for each natural number n, the finite sequence Σ(0), Σ(1), Σ(2), ..., Σ(n) is computable.
(The quotation is in L. De Mol's "Tracing Unsolvability", p.462.) Although the present section of the article is about non-computability, perhaps this point about the search for a different type of "non-computability" should be emphasized more?Our interest in these very special problems was motivated by the fact that at present there is no formal concept available for the “effective calculability” of individual well-defined integers like Σ(4),Σ(5), .... (We are indebted to Professor Kleene of the University of Wisconsin for this information.) We felt therefore that the actual evaluation of Σ(3), SH(3) may yield some clues regarding the formulation of a fruitful concept for the effective calculability (and noncalculability) of individual well-defined integers.
I was wondering if it would be possible to extend the notion of Turing Machines to transfinite numbers of states or symbols. If, for example, we labeled the states by the natural numbers (instead of alphabetically), and used two algorithms to determine the instructions at each state for symbol 0 and for symbol 1, would it be possible to create a machine that halts after an infinite number of steps and/or prints an infinite number of 1's? Alternatively, could we use an infinite number of symbols and a finite number of states? Or a infinite number of symbols and of states?
I haven't thought too long about it, but it seems like it should be possible, perhaps even easy, to create such machines that halt either in a finite or infinite number of steps, or which do not halt. Ones that do not halt are trivial, and ones that halt in a finite number of steps obviously do not need an infinite number of states or symbols, but ones that halt after some infinite time span might be interesting.
Finally, if such a thing is possible, would it make a difference which infinite number of steps it takes ( vs. vs. vs. , etc.)? Eebster the Great (talk) 03:49, 1 October 2008 (UTC)[reply]
This doesn't seem right to me. It seems to be saying, of the Goldbach conjecture, that "There exists an N such that, if no counterexamples n < N exist, then no counterexamples n > N exist either." And we find N by coming up with a Turing machine to sequentially test for counterexamples and then plug its number of states and number of symbols into the busy beaver function.
So firstly that's a massive claim. And I figure it needs some citation. Secondly, I don't believe it, but it's hard to say why. Of course if you imagine a computer program searching for counterexamples, memory etc. means there's always a limit to how high you can look. (In 2GB of RAM I guess my computer couldn't look past 2^16,000,000,000 for counterexamples, at least without going to the hard drive.) But I'm also having trouble imagining a turing machine that could solve the problem. —Preceding unsigned comment added by 58.96.121.81 (talk) 05:31, 16 December 2008 (UTC)[reply]
My apologies to Mr. Chaitin, who has never stated that his constant or Busy Beavers can be used to solve Riemann's or Goldbach's unlike someone claims at the Chaitin's constant page. You can't check each even number eventually "without referring to any sort of infinities" unless you're a real die-hardcore ultrafinitist denying the existence of more than a finite number of integers. If Goldbach's is true then no matter how big a Turing machine you build, it can only check the first n even integers. You can't have an algorithm with computable length checking all the numbers. If you don't find a counterexample below the number given by calculating the Busy Beaver function of Turing machines with programs the length of Graham's number, it STILL doesn't prove a counterexample doesn't exist. By checking numbers you can only prove it wrong, never right. To prove it right you need induction or some other kind of THEOREM. I'm not saying a Busy Beaver wouldn't be a helpful tool in finding large primes or perfect numbers or proving Goldbach's wrong if it is wrong and getting arbitrarily large lower bounds for the possible counterexample. It is NOT "guaranteed to find any counter-example". Only any counterexample below any preset bound, however large but still finite.
Of course there's the teeny-weeny problem of Busy Beavers being non-computable and growing faster than any computable function, so the only way to find a Busy Beaver for a class of Turing machines is to run every possible program and at some point prove all still going on to never be going to terminate, the complexity of such a proof also growing at a non-computable rate, and then declaring the machine which went on the longest before halting the Busiest Beaver. During that process you have ran trough all possible algorithms of that class, but you can assign them with different meanings next time. I think building a quantum computer offers far more feasible prospects in the quest for bigger and better means of numbercrushing.
Check out Gregory Chaitin's website, he's got a lot to say about a lot of subjects, computability being only one of them. I once again apologize for hurriedly blaming him for someone drawing false conclusions from his amazing work.
A rather recent lecture on computability, in which he repeatedly states that you can only prove Riemann's or "no odd perfect number" hypothesis or generally any conjecture equivalent to a halting problem WRONG here: http://www.cs.auckland.ac.nz/~chaitin/wlu.html Though he doesn't specifically name Goldbach's or a,b,c,d>1 a^b+1=c^d only when a=d=2 and b=c=3 there they are also of the type equivalent to a halting problem. —Preceding unsigned comment added by 91.133.35.83 (talk • contribs) 07:56, 5 December 2009
and he goes on to explain exactly how. He is an expert in the field and he is correct. But let me go further, here is a finite python program that will search for a counter-example to the Goldbach conjecture:
def goldbach_check(): """Check Goldbach's conjecture for each even number N until it fails. If it never fails, never return.""" N = 4 while True: # Test Goldbach's conjecture for N. if not sum_of_primes(N): return N # If N is not the sum of two primes, fail. # Otherwise try the next even number. N += 2def sum_of_primes(N): """Is N the sum of 2 primes?""" # Try all ways N could be the sum of 2 integers. for k in range(N): if is_prime(k) and is_prime(N-k): return True # N is the sum of two primes (k and N-k) # If none work, then N is not the sum of two primes. return False
" and he goes on to explain exactly how"The explanation goes like this
"An experimental approach is touse a fast computer to check whether or not P is true, say for the�first billion natural numbers. To convert this empirical approach into aproof, it would suffice to have a bound on how far it is necessary to testP before settling the conjecture in the affirmative if no counterexamplehas been found, and of course rejecting it if one was discovered. SIGMAprovides this bound, for if P has program-size complexity or algorithmicinformation content k, then it suffices to examine the f�irst SIGMA(k +O(1))natural numbers to decide whether or not P is always true. Note thatthe program-size complexity or algorithmic information content of afamous conjecture P is usually quite small; it is hard to get excitedabout a conjecture that takes a hundred pages to state."
Neither Goldbach nor Riemann has program-size complexity or algorithmicinformation content. Read the newer article.
Here is the fallacy in the program:The subprogram
# Try all ways N could be the sum of 2 integers. for k in range(N): if is_prime(k) and is_prime(N-k): return True # N is the sum of two primes (k and N-k) # If none work, then N is not the sum of two primes.
grows infinitely complex.Only the sums of odd integers need be checked, that is N/4 ways. You can improve a little but it grows the rate N/k where k is not much. "say for the�first billion natural numbers" For N=1 000 000 000 that certainly is over 1 000 000 steps. For N= 1 000 002 that is the same amount of NEW steps none of which are previously taken. The program is finite in python but no finite Turing machine is a model for even the subprogram.
There is also no general function "is_prime". There is no general finite algorithm either. Erastothenes' sieve is longer for larger numbers. There certainly isn't a Turing machine or subprogram "is_prime" For every new N you need to check if N-3 is prime.Rantalaiho74 (talk) 18:21, 1 October 2010 (UTC) a.k.a.91.133.35.83[reply]
"There is an analog to the Σ function for Minsky machines ... This is a consequence of the Church-Turing thesis."Please excuse me if I misunderstand the concepts here. I thought that the equivalence of register machines and turing machines was a mathematical theorem, whereas the CT-thesis was an unproven philosophical assertion. Should it say instead "There is an analog for register machines because somebody proved they are equivalent", perhaps followed by "it is probably impossible to calculate the function by any means because of the CT-thesis." —Preceding unsigned comment added by 24.2.48.202 (talk) 20:02, 9 January 2009 (UTC)[reply]
In the Known Values section, the present article states the following:
Milton Green constructed a set of machines demonstrating that : (Where is Knuth up-arrow notation and A is Ackermann's function)in his 1964 paper "A Lower Bound on Rado's Sigma Function for Binary Turing Machines".
That seems to be a (possibly incorrect?) result of someone other than Green. I don't have Green's paper, but I do have two papers that discuss it, and they seem not to support the above inequalities. The first paper is Improved Bounds for Functions related to Busy Beavers by Ben-Amram and Petersen, 2002, which (on p.3) merely cites Green 1964 as showing that Σ(4n + 3) > A(n,n), where A is the Ackermann function. (Note the "4n+3" rather than "2n+4".) The second paper is Ackermann's Function in the Numbers of 1s Generated by Green's Machines by Julstrom, 2002. This paper discusses a function fM(x,y) (whose definition is very similar to that of the Ackermann function), which is the number of 1s left on the tape by a 2x-state Green's machine when started on the rightmost 1 of a tape containing a block of y 1s. Such a block of y 1s can be produced by a (y+1)-state TM started on an all-0 tape, so evidently one has the lower bound Σ(2x+y+1) ≥ fM(x,y); e.g., y = 3 gives Σ(2x+4) ≥ fM(x,3). However, this does not support the inequality stated in the article, as it is not generally the case that fM(x,3) > 3^^...^3 (with x up-arrows); e.g., one finds fM(3,3) = 45 < 3^^^3. Possibly the inequality should be Σ(2k+4) > 3^^...^3 (with k-2 3s) > A(k-2,k-2) ?
— r.e.s. 14:52, 16 November 2009 (UTC)[reply]
I re-aquired a copy of Green's paper. Of note: the numbers I have called here, he refers to as and he [Green] uses for a different sequence of machines (Class G machines) which appear to be what Ben-Abrams refers to. On the other had, Julstrom talks about Class M machines, which are yet another class Green used in the paper. Thus, I believe that we are all bounding completely different machines. Cheers, — sligocki (talk) 04:26, 18 November 2009 (UTC)[reply]
For a possibly more-direct way of seeing that is implicit in Green's results, we can define
and , noting that
and that .
Then Green's definition of the B-functions yields
which can be directly compared line-by-line to the definition of the c-functions:
,
giving the desired inequality:
.
Hence
,
where the case for k = 2 is treated separately and follows from the known value Σ(4) = 13.
— r.e.s. 14:20, 23 November 2009 (UTC)[reply]
The article says: "there is, for each input n, an algorithm An that outputs the number Σ(n) (see examples).". But what's so remarkable about this? This is true of all integer-valued functions, and to define such an algorithm is trivial. - Gigasoft 84.211.109.82 (talk) 04:51, 3 April 2010 (UTC)[reply]
Here was written:
A trivial but noteworthy fact is that every finite sequence of Σ values, such as Σ(0), Σ(1), Σ(2), ..., Σ(n) for any given n, is computable
But why is it "trivial"? Perhaps for some n there would be such a Turing machine that we couldn't identify whether it halts or not.
Eugepros (talk) 11:18, 5 August 2010 (UTC)[reply]
Oh, sorry, I understand. The Turing machine in itself is such an algorithm: Even if we cannot identify whether it halts or not, the predicate "it halts" is defined as partial recursive (but not necessarily total recursive) function. Perhaps it's worthwhile to explain explicitly?
Eugepros (talk) 10:56, 9 August 2010 (UTC)[reply]
Hmm, I don't understand why "A similar program exists for every finite n". Actually I know that we haven't at our disposal even program for "PRINT <Σ(10)>". And we can face fundamental mathematical problems, trying to find the number Σ(10), because halting problem for some Turing machine (of 10 states) might be unresolvable. Can't we? — Eugepros (talk) 11:22, 10 August 2010 (UTC)[reply]
Oh, I beg pardon for unintended applying of constructive logic. I understand that you deduce "Σ(10) exists" from "every 10's state Turing machine or halts, or not". But this axiomatics is too strong for me... I'm interested in what can say about computability of Σ(n) those, who don't accept law of excluded middle...Eugepros (talk) 12:28, 10 August 2010 (UTC)[reply]
As to the role of constructive logic: As far as I know, it was specially developed to answer such kind of questions. Constructive proof of existence for such an individual integer (like Σ(10)) is supposed to be the proof of its "effective calculability". Or did I misunderstand something?Eugepros (talk) 08:44, 11 August 2010 (UTC)[reply]
Conserning the conjecture that "there exist values of n for which Σ(n) is not effectively calculable": I guess that it would be more precise to say that it's possible to state, but not possible to prove. This conjecture is formalized as in the constructive predicate calculus. But it isn't the case of the classical predicate calculus, because in the last one it's trivially disproved (using the law of excluded middle).
In the constructive logic (see Brouwer–Heyting–Kolmogorov interpretation) the proof of is the pair of an individual number n and the proof of . The last proof is the implication to absurdity from the conjecture , it means that we should find such an individual Turing machine M, for which it's undecidable - does it halt or not. We cannot formalize the concept of "proven undecidability" for an individual Turing machine halting problem. Thus, we cannot prove the conjecture , but we can state it, and this statement isn't "trivially false" in the constructive sense.
It's my opinion, perhaps it's wrong...Eugepros (talk) 10:18, 12 August 2010 (UTC)[reply]
I cannot find any mention of the initial state(the start state) with which "running the machine" has to begin with. Or am I just blind?
— H.Marxen (talk) 16:35, 26 August 2010 (UTC)[reply]
HelloI've seen recently that an edit stating that Σ(2,3) = 9 and S(2,3) = 38 has been reversed since there is "no published proof". However, in Pascal Michel's website there is a reference to Lafitte and Papazian 2007 as a proof accessible at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.3021&rep=rep1&type=pdf#page=231 Is this considered as unconvincing or not published ? Thanks - Yves —Preceding unsigned comment added by 193.49.219.185 (talk) 09:35, 3 September 2010 (UTC)[reply]
I have a concrete doubt, and a general problem with the presentation of a proof for some Σ or S value. I'll start with my concrete doubt:
The more general problem I have is the question: How much detail shall be published as to be accepted as a final proof for a special case of Σ and/or S?
Now, am I convinced? Partly, but not completely. Have I checked the proof? Sorry, no. I could not do that, except... I write my own version of the program(s) they have used.
As a matter of fact, I have not (yet) written such a second implementation.
Now, I'm not really sure how to judge the L&P paper. Brady in 1983 gave a lot more detail in order to settle (4,2), but that does not strictly imply, everybody else must do the same. I'm not even sure whether that bulk of detail given by Brady really makes a difference, since I'm not sure, whether any reader really can be sure to have checked all of them. How much of a burden can the author place on his readers?
Any suggestions or insights?
--H.Marxen (talk) 12:51, 4 September 2010 (UTC)[reply]
Following up myself... Obviously I still have to learn a lot. Meanwhile I have learned about the way to construct this encyclopedia, e.g. WP:IRS.I seem to have mixed up the work of a scientist with that of a wikipedia author. The latter is not considered to judge the content of scientific publications, but rather to judge their reliability.
In this case we have a conference paper written by two mathematicians. It looks like a quite normal primary source. No hints for doubt.It is published and as reliable as most other publications.There is only 1 citation by a later work of the first author.According to wikipedia guidelines a secondary source would be preferred,but the topic "busy beavers" is so small (in number of publications), that there does not exist much secondary publications about this topic at all, and waiting for more citations or even for secondary publications would mean to drop the topic from wikipedia, at least in parts.
Up to now other primary sources have been used as base for this article,and following that practice (which I consider to be ok) we should acceptthe claims about (2,3), add the paper to the list of references, and update the result tables.
Since I still feel a bit confused, I'd like some feedback from people with more experience as a wikipedia author, before I go ahead and do the change.
—H.Marxen (talk) 01:25, 6 September 2010 (UTC)[reply]
Hello Heiner,First of all I want to thank you for your expert analysis, I didn't realize the degree of complexity of such proofs. Being much more a reader than an editor in Wikipedia (only occasionally, often for minor changes, I still don't have an account), I can only state my opinion on this particular question. For Σ(2,3) and S(2,3) only this source (L&P) is published, and seeing your analysis, I can guess the likely reason why Sligocki made the revert: according to Pascal Michel's website he found an independent proof but this is yet to be published; thus, he has an expert opinion on the degree of confidence of the proof claimed by LP, and is not convinced until he is able to publish himself as an independent confirmation. Therefore the situation is this: Σ(2,3) and S(2,3) have been claimed to be equal to 9 and 38 according to L&P but community consensus (including yourself) is yet to be reached. I would suggest to change the table, but with this caveat being clearly visible. I would be interested to see Sligocki's opinion on this. - Yves —Preceding unsigned comment added by 193.49.219.185 (talk) 15:11, 6 September 2010 (UTC)[reply]
Assertions like "there exists program PRINT " look very unconvincing for me, because they were derived from unobvious axiomatics. But I guess, that there is another way to prove that integers like are effectively calculable. If I'm wrong, please correct. We should express the sentence " halts" (for any given Turing machine ) in a formal language of arithmetic. I guess, that we don't need the multiplication for this purpose, so the language of Presburger arithmetic should be sufficient. But Presburger arithmetic is complete and decidable theory. The last means, that there exists an algorithm which decides whether the sentence " halts" is true or false. Thus, we can effective calculate for any given .
Eugepros (talk) 12:33, 21 October 2010 (UTC)[reply]
Hmmm, why? As far as I now, there is no a theorem about undecidability of the halting problem for some individual Turing machine. Alan Turing proved in 1936 only that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
Eugepros (talk) 13:50, 28 October 2010 (UTC)[reply]
Yes, there cannot be a general algorithm to convert any sentence "M halts" into formal Presburger arithmetic. But maybe we can prove that "M halts" is convertable into formal language of Presburger arithmetic for any M? Such a proof doesn't mean constructing of general method for the conversion.
Eugepros (talk) 12:37, 11 November 2010 (UTC)[reply]
I understand you. But problem is that proofs like "statement is convertible because it's either true or false" means nothing for me. :( I know, it's classical logic. But I cannot trust inference from nothing but law of excluded middle. The statement " halts" can obviously be translated into something like: "There exists the number , such that ='stop', where are states of the for every -th step". I can't see why the sequence couldn't be defined recursively, using formal language like the one of Presburger arithmetic... Or the conjecture, that functions are recursive for every , implies that , as the function of both and , is also recursive?
Eugepros (talk) 11:57, 13 November 2010 (UTC)[reply]
I've just added this section, but the wording is somewhat tricky. Presently, the conclusion ("in the context of ordinary mathematics, no specific number can be proved to be greater than Σ(10↑↑10)") is somewhat misleading, as it seems to imply that for n = Σ(10↑↑10), not even "n+1 > n" is "provable in ordinary mathematics". But the intended meaning is that in the given formal system, there is a formula φ(<n>) (where <n> is a unary notation for the number n) that expresses "n > Σ(10↑↑10)", and the conclusion is that no sentence of the form φ(<n>) is provable in that system.
— r.e.s. (talk) 19:06, 16 November 2010 (UTC)[reply]
It says this:
"A noteworthy fact is that, theoretically, every finite sequence of Σ values, such as Σ(0), Σ(1), Σ(2), ..., Σ(n) for any given n, is (trivially) computable, even though the infinite sequence Σ is not computable (see computable function examples)."
In my most charitable interpretation of this sentence, it's saying something that's trivially true but perhaps misleading and not too related to the notion of the computability of the actual sequence of Σ. It's kind of like saying that "every digit in the decimal expansion of an uncomputable number is in isolation a computable number, because a 'digit' is a value from 0-9 and hence a natural number and the naturals are computable." This is true, but it's like this random factoid that can easily send someone in the wrong direction. It's misleading because it seems very much like it's saying that one can figure out, even aside from "practicality" restrictions, what the value of Σ(n) is for any n. This is false.
Using our decimal expansion/digit metaphor, it would be like saying that one can figure out WHICH POSITION in the expansion contains which of these computable entities we've called "digits," and that's just not true. If it were true, the number wouldn't be uncomputable at all. Aside from that, the fact that the concept of a "digit" itself, being a value from 0-9, is a computable number is basically irrelevant to what's being discussed here. And in the case of Σ, it's even more irrelevant; if every value of Σ(n) is a finite natural number, then we already know that values of Σ(n) are in the set of all computable numbers by definition. We already went over this when we defined Σ as a function mapping from N -> N. So there's no need to state that because the codomain of Σ is the set of natural numbers, it's also a subset of the set of computable numbers.
But then the next sentence after what's written above is this, which makes it seem like it's saying something that's just plain false (first sentence included again for reference:
"A noteworthy fact is that, theoretically, every finite sequence of Σ values, such as Σ(0), Σ(1), Σ(2), ..., Σ(n) for any given n, is (trivially) computable, even though the infinite sequence Σ is not computable (see computable function examples). Furthermore, for sufficiently small n, it is also practical to compute Σ(n)."
It now seems like it's saying that the problem with computing Σ(n) is that as n increases, the computation involved becomes so complex that it's not really feasible to figure out Σ(100) or something. But that's not really it. It's just not true that we can figure out what Σ(n) is for every choice of n -at all-, independent of any notion of "practicality," on a completely theoretical level, even if we had an infinite amount of time. It's only for some n that we can compute it at all, period.
I see there was some discussion on this before, but it doesn't look like it was resolved. I'm not sure how to change it yet though. I'll post this for now and maybe we can get a discussion on it. I'd like to remove these few sentences because it either seems misleading, unrelated, or false, depending on how I interpret this.
71.230.120.206 (talk) 09:09, 19 January 2012 (UTC)[reply]
Even if we ran a Turing machine until the Heat death of the universe, we will get nowhere near when it halts.
Bubby33 (talk) 21:06, 18 April 2015 (UTC)[reply]
The untitled comments below were taken from the top of the page by User:Negrulio on 28-12-2015 --Negrulio (talk) 16:03, 28 December 2015 (UTC)It would be nice to more specifically describe what the term "n-state machine" means. Whether it is a Turing Machine or an arbitrary n-state machine. marek 19:38, 23 February 2006 (UTC)[reply]
There is an UTM (2,22), so BB(22) would provide an answer to the Halting Problem:Lower bounds for universal Turing machines. So BB(n) can't be calculated for n>=22, which makes the application section useless. —Preceding unsigned comment added by Rantalaiho74 (talk • contribs) 16 October 2010
Proof of the fact "S(n) grows faster than any computable function F(n)" follows from the properties of the composition Create_n0|Double|EvalF|Clear where n0 is the size in states of the machine Double|EvalF|Clear. I think that the current proof in the begining of the article is much complex (it uses log2(n) and UTM properties) and should be changed. Skelet 08:26, 27 Oct 2004 (UTC)
In the same manner proof of "Σ(n) grows faster than any computable function F(n)" follows from the properties of the composition Create_n0|Double|EvalF|Increment. Skelet 08:31, 27 Oct 2004 (UTC)
We can solve the halting problem for TMs up to any fixed size. What's the corresponding principle here in terms of real programming languages? Could we calculate S(n) up to a fixed n by running a particular program (a big TM enumerator perhaps?) of larger size? Do we know how much larger than n the machine to calculate S(n) must be? Lunkwill 29 June 2005 07:28 (UTC)
This edit removed a "non-reliable" source from the article: https://www.search.com.vn/wiki/?lang=en&title=Busy_beaver&diff=756743646
I don't think this is justified. I'm not saying that Wikia is a reliable source. But, what I am saying is that to dismiss this based on the reliability of the source is a genetic fallacy, because the validity of a deductive argument is independent of the reliability of the source of the argument. In other words, a deductive proof is a proof, regardless of where a proof comes from or is published. However, at the same time I do understand that Wikia isn't a WP:RS, and accordingly shouldn't be included in Wikipedia. But, since the removal of this source reduces the quality of the article by adding an uncited non-trivial claim, and it removes a place where people can learn more about what is being said, I think this calls for WP:IAR. IWillBuildTheRoads (talk) 20:07, 8 January 2017 (UTC)[reply]
What is the name of the function that counts the maximum right shift, R(n)? How does it grow proportionally? 91.66.15.241 (talk) 21:08, 13 March 2017 (UTC)[reply]
Very nice article.The 3 state BB in section examples takes 14 steps.The following machine takes 12 steps and always writes a 1.
A | B | C | |
0 | 1RC | 1RA | 1LB |
1 | 1RA | 1LC | 1 H |
Is this worth mentioning?Do with my remark as you wish.
Jacob.Koot (talk) 18:38, 11 April 2017 (UTC)[reply]
Below is the table of moves. ((x ...) (y z ...))represents the tape (x ... y z ...) with the tape-head at y.
.......................................... initial tape: (() (0))
move 1, state A -> C, symbol 0 -> 1, move: R, new tape: ((1) (0))
move 2, state C -> B, symbol 0 -> 1, move: L, new tape: (() (1 1))
move 3, state B -> C, symbol 1 -> 1, move: L, new tape: (() (0 1 1))
move 4, state C -> B, symbol 0 -> 1, move: L, new tape: (() (0 1 1 1))
move 5, state B -> A, symbol 0 -> 1, move: R, new tape: ((1) (1 1 1))
move 6, state A -> A, symbol 1 -> 1, move: R, new tape: ((1 1) (1 1))
move 7, state A -> A, symbol 1 -> 1, move: R, new tape: ((1 1 1) (1))
move 8, state A -> A, symbol 1 -> 1, move: R, new tape: ((1 1 1 1) (0))
move 9, state A -> C, symbol 0 -> 1, move: R, new tape: ((1 1 1 1 1) (0))
move 10, state C -> B, symbol 0 -> 1, move: L, new tape: ((1 1 1 1) (1 1))
move 11, state B -> C, symbol 1 -> 1, move: L, new tape: ((1 1 1) (1 1 1))
move 12, state C -> H, symbol 1 -> 1, move: , new tape: ((1 1 1) (1 1 1))
(I improved the layout --H.Marxen (talk) 18:58, 3 May 2017 (UTC))[reply]
Thanks for improving the layout. I tried it myself, but did not know how to do it.I agree that unpublished work must not be included.Nevertheless, my example is a proof by itself and could be interpreted as a publication via Wikipedia.It seems that Wikipedia does not accept publications made via Wikipedia?Jacob.Koot (talk) 16:20, 12 May 2017 (UTC)[reply]
https://www.search.com.vn/wiki/en/Turing_machine_examples#3-state_Busy_Beavershows a busy beaver that takes 12 steps and always writes a 1.It is not exactly the same as my one, but works all the same.The reference is: "derived from Peterson (1988) page 198, Figure 7.15."I think we can include Peterson's example.Jacob.Koot (talk) 17:24, 21 June 2017 (UTC)[reply]
The article mentions that "a statement of the exact number of steps it takes to reach the Halt state" is necessary because without it "the problem of verifying every potential entry is undecidable", citing the halting problem. However, doesn't the halting problem is that of determining halting of an arbitrary machine on ARBITRARY INPUT, and the latter requirement is key to the proof?
If there is a generalization of the halting theorem that prohibits creating an algorithm that for one specific input would predict whether an arbitrary machine would stop, such a generalization should definitely be mentioned on the corresponding "halting problem" page, and the current article should link specifically to that generalization. Otherwise the current article needs to reflect that the "exact number of steps" is only required because we don't know an algorithm to check, and do not even know WHETHER such an algorithm could exist. — Preceding unsigned comment added by 104.53.222.39 (talk) 01:37, 2 June 2020 (UTC)[reply]
#include <stdio.h>#define STATE_N (4)#define SYMBOL_N (2)#define TAPE_N (16)int move_tb[SYMBOL_N][STATE_N] = { { +1, -1, +1, +1 }, { -1, -1, -1, +1 } };int state_tb[SYMBOL_N][STATE_N] = { { 1, 0, -1, 3 }, { 1, 2, 3, 0 } };int write_tb[SYMBOL_N][STATE_N] = { { 1, 1, 1, 1 }, { 1, 0, 1, 0 } };int tape[TAPE_N];int main(void){ int header = 11; int state = 0; int step = 0; while (1) { printf("%4d ", step); for (int i = 0; i < TAPE_N; ++i) printf("%c%c ", i == header ? "hABCD"[1 + state] : ' ', "_1"[tape[i]]); printf("\n"); if (state == -1) break; int read = tape[header]; tape[header] = write_tb[read][state]; header += move_tb[read][state]; state = state_tb[read][state]; if (header == -1 || header == TAPE_N) { printf("ERROR: out of tape (header=%d)\n", header); break; } step++; } return 0;}
--MkMkMod (talk) 07:53, 17 July 2020 (UTC)[reply]
I suspect, that S(n) was formerly noncomputable, but in 2013 when the first-order set theory (which is Rayo(n)) was defined, S(n) became computable.
In this video, Carbrickscity said the reason, why Rayo's number is noncomputable. The reason was: "No one will ever define a number with a googol symbols.". The problem seems to be the number of symbols. There is not enough space in the observable universe for a googol symbols. Emk has shown, that Rayo(7901) > S(265536−1), where S(n) is the maximum shifts function. Only 7901 symbols (which can be easily written down) and already 265536−1 states. This is why I suspect, that S(n) became computable, after Rayo(n) was defined.
The same symbol-problem appears on proving TREE(3) in strictly finite mathematics. This would need 2^^1000 symbols. No one can ever finish such a prove, because there is not enough space in the observable universe for this many symbols. This reason was originally written in this video. So, User:84.154.72.51 wrote this idea for the exact value (or at least a really good bound) of TREE(3). The idea is the first-order set theory for TREE(3) in symbols. The first-order set theory is Rayo(n), where n is the number of symbols. Here, it has been shown, that Σ(2000) > Loader's number ≫ TREE(3). Here, it has been shown, that S(n) ≥ Σ(n) for all n. And of course, 265536−1 ≫ 2000. So, the first-order set theory would reduce the "required number of symbols for TREE(3)" from 2^^1000 to less than 7901. — Preceding unsigned comment added by 80.142.18.145 (talk) 20:41, 25 October 2020 (UTC)[reply]
It has been shown, that Σ(17) > Graham's number.
What kind of Σ(n) would be about as big as TREE(3), SSCG(3), SCG(13), Loader's number, Rayo's number and Fish number 7?
The 4-state, 2-symbol busy beaver Examples and Visualizations do not agree. The Examples has 1RH for state C symbol 0, and the Visualizations has 0RH for state C symbol 0. The Example states that the 4-state, 2-symbol busy beaver produces 13 ones in 107 steps and it says "see image." The Visualizations only produces 12 ones when it halts. This should be corrected. — Preceding unsigned comment added by 50.206.176.154 (talk) 04:17, 3 February 2021 (UTC)[reply]
Carbrickscity's reason, why Rayo's number is uncomputable: “No one will ever define a number with a googol symbols.”
Using the latest bounds, it can be determined, that Rayo(7339) > S(265536 - 1).
Only 7340 symbols in the first-order set theory and already 265536 - 1 states in the maximum shifts function, so I guess, Σ(n) and S(n) became computable. Also, Rayo(n) became 84.154.72.51's idea for TREE(3) in symbols.
The first-order set theory only needs a few thousand symbols for TREE(3). So, if we use the first-order set theory for TREE(3) in symbols, we can find out the actual exact value of TREE(3). 84.154.65.218 (talk) 09:43, 10 February 2023 (UTC)[reply]
What this article calls Σ(N) (aka "Rado's sigma function") seems to be called BB(N) in many sources: see for example [1], [2], [3], [4]. "BB" seems to be easier to remember than "Σ"; if I'm right that they are the same thing, I propose we change the usage here to replace it. — The Anome (talk) 20:54, 19 October 2023 (UTC)[reply]
I was the editor who changed it, based on the then current version of the article Graham's number. I don't have a dog in this fight, I just wanted things to be consistent.
Since then, there is an ongoing dispute there over whether to zero index or not. Seems to me that the best approach for the editors at this page to wait for that dispute to be resolved and accept that verdict. If anybody here wants to get involved, the talk page for Graham's number is easy to find.
For now, I support the current revision that reverts my edit from two months ago. Pending whatever the editors at the topic article decide. Mr. Swordfish (talk) 02:03, 13 November 2023 (UTC)[reply]
In 1964 Milton Green developed ...
Likewise, we know that and S(17) > Σ(17) > G, where G is Graham's number.
https://www.sligocki.com//2024/05/22/bb-3-4-a14.html
describes a Busy Beaver candidate which puts more than Ackermann(14) symbols on the tape, in fact exactly non-zero symbols on the tape NadVolum (talk) 11:41, 31 May 2024 (UTC)[reply]