Talk:Busy beaver

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	B Class	Mid Priority	Field: Foundations, logic, and set theory
Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.

This article may be too technical for a general audience. Please help improve this article by providing more context and better explanations of technical details to make it more accessible, without removing technical details.

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)

Proof of the fact "S(n) grows faster than any computable function F(n)" follows from the properties of the composition Create_n₀|Double|EvalF|Clear where n₀ 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 log₂(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_n₀|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)

Nope. Put simply, if we knew how big a Turing machine we needed to calculate S(n), then we'd be able to calculate S(n). --Ihope127 16:59, 2 April 2006 (UTC)

[edit] Busy beaver functions

At the moment, only Σ (number of nonzeros in result) and S (number of steps taken) are mentioned. There are others that could be investigated:

• number of symbol toggles
• number of toggles from 0 to 1 (or 1 to 0, 0 to non-0, to higher-index symbol, etc.)
• number of tape positions that are ever toggled
• final distance from starting point
• greatest distance reached from starting point
• greatest distance from starting point at which a non-0 is ever set
• greatest distance from starting point at which a non-0 is present at the end
• overall explored range
• overall range of non-0s ever set
• overall range of non-0s at the end

.... -- Smjg 15:11, 27 September 2005 (UTC)

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

[edit] References

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)

[edit] Notation

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 "S_RTM(n)"? Pmdboi 14:24, 8 March 2006 (UTC)

Unless Wikipedia has a standard contrary to my opinion I vote for "1's" when the 1's are the plural of symbol "1" from the binary collection of symbols { 0, 1 }. Standard American prose/literature wants/uses/expects "one" and "ones". Interesting that the international symbol for OFF is O and ON is | (vertical-slash, not ordinal "1": per the IEC-- can't remember the exact specication number IEC-317, Symbols? ). Emil Post specified "mark" = { | } and "blank" = { } in his models. It probably should be "|", both plural and singular, but I'd stick with "1's" per the argument: "If Bill likes it, it must be good." (Hope this helps). wvbaileyWvbailey 00:45, 9 March 2006 (UTC)

[edit] Error?

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?

No. If there was a Turing machine M which could create EvalS based upon n0, then we could run M on n0 to create EvalS and then run EvalS, thus having a machine with fixed size which runs EvalS. This is some justification for our definition of computability as Turing machine computability. - Sligocki 03:14, 9 December 2006 (UTC)

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)

[edit] Accessibility

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)

Is there a category where we can put requests for accessibility? Im looking at this, and it seems that unless you have a background in whatever this article is talking about, you wont be able to understand it. for example, that sequence "1, 4, 6, 13, ≥ 4098 doesnt make any sense at all. It should definately be made more clear to the average person what the reasons are for not knowing what the fifth number is when it is known that it can't be bigger than 4098. Also, whats the point of all this? The article doesnt seem to make it clear why any of this is of any importance to anything, such as why anyone would ever want to know what the fifth value that is less than 4098 is, and how knowing that number would make any difference to anything. Definately not user friendyly Carterhawk 08:23, 26 August 2006 (UTC)

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)

[edit] The game of Busy Beavers: a simple explanation

This is a two-symbol three-state Busy Beaver. It is working on a tape intially printed with 0/blanks. The robot has looked at the symbol in the window (symbol 0), has read the instruction ("state") C and is about to PRINT a 1. Then it will push the tape-LEFT button. Lastly it will look toward instruction ("state") B. (The print/erase mechanism is out of sight, beneath the window.)

"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:

> Your mission as a "busy beaver" (should you choose to accept it):

>> At the start you will be given a list of instructions. (Thereafter either you or your handlers will change the instructions in Part II). Follow the instructions precisely, and print as many 1's as your instructions tell you to do before halting. To succeed you must print some ones and HALT, eventually!

> Your "Turing tape" is ready -- it is blank. Your instruction is #1. There is no time limit, no one cares (too much) how long you take. Just follow the rules and print the 1's on your blank tape.

> Robots, are you ready?

> Go!

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.

> Your new mission (should you chose to accept it):

Change the instructions you were given, so they are still a true "busy beaver Turing program" and they have the same number of instructions. For example: if your mission is to find the best 6 instructions, you must have 6 instructions. But if in instruction #3 you see ERASE, you might change this to PRINT and where you might see LEFT you might change this to RIGHT).

do part I again.

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.

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

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:

PRINT (mark the square with a 1)

RIGHT (move the tape to the right)

GO TO INSTRUCTION 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:

PRINT (mark the square)

LEFT (tape to the left)

GO TO INSTRUCTION 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:

PRINT

LEFT

GO TO INSTRUCTION B

We continue this, when finally we hit the HALT instruction. We're done!:

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?

The end.

>>>>>> <<<<<<<<

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)

[edit] 4-state busy beaver example

Run on Excel. Transposed sideways to fit on page. A. Brady's machine.

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)

[edit] wvbailey

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!

[edit] Too technical

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:

• Make it clear that busy beavers is "a game" (albeit a weird mathematical game) that anyone can play. It has no apparent "use" -- see next bullet-point.
• Historical context: Why was busy beavers proposed by Rado? Brady hints that it has to do with questions around "the halting problem", instances of tiny machines should be amenable to solution of "the problem" but even these tiny ones are virtually "intractable".
• Who works on busy beavers? The only name I know is Allen H. Brady; cf his paper referenced.
• A brief description of the algorithm(s) used to find the busiest beaver.

• How do we know that a particular busy beaver under test (e.g. a 6-state one) is not locked in a loop? How do we know when to "give up" and "call it a day"?
• Heuristics: are they used? Can a casual reader figure out which b-b's won't work, and why? (certainly some are trivial, such as any accessible state with both 0 and 1 reverting back to itself (to make a circle)
• Genetic algorithms used in any way? Parallel algorithms used to sift through the possibles?

• Examples of the simplest cases. For example Post-Turing machine and Turing machine examples where I've used 2- and 3-state two-symbol busy beavers as examples (thus avoiding "original research"). But really those should be repeated here, or especially the busy beaver on Turing machine examples should actually be here, and the Turing machine article refer here.
• Why does the problem "explode?" It seems to explode in two ways: both in the number of possible b-b's per number of states, and (ii) the number of states a particular instance under test might go through.

• Provide a simple explanation of the number of possible busy beaver machines per number of states N (it looks to me like it is (8*N)^N). But many are silly, hence the need for heuristics.

• Better (more) print references, in-line references too. Any books out there specifically on busy beavers?

Suggestions? Comments? wvbaileyWvbailey 14:47, 15 September 2006 (UTC)

[edit] Content Update

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)

I very much appreciate what you've done here. I scoured the Dartmouth library for a a cc of Rado's original paper but was unable to find one. I do have a second paper -- the Lin-Rado paper -- but not the very original one. I see someone has added yet another tag at the bottom. But without the original Rado paper I feel unprepared to do an effective review/edit. Where does one find a cc of the original paper? Lemme know, thanks. wvbaileyWvbailey 21:39, 27 January 2007 (UTC)

[edit] Non-computability of Σ : emphasizing a possible pitfall

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. [User:Dabsent|Dabsent]] (talk) 11:12, 31 May 2008 (UTC)

Thanks for pointing out the room for improved wording, but that's not what I wrote; what I wrote was

Although Σ is a non-computable function, nevertheless for each natural number n, the finite sequence Σ(0), Σ(1), Σ(2), ..., Σ(n) is computable.

That statement is correct and unambiguous, imo, but to put more emphasis on the pitfall that arises for anyone prone to "quantifier dyslexia", I've reworded it. This is, after all, exactly the issue I was originally wanting to emphasize. I also replaced your explanation with a link to explanatory examples at computable function#Examples (see the first & last examples given there).--r.e.s. (talk) 21:32, 31 May 2008 (UTC)

I agreed it was perfectly true, and shouldn't have said 'amibguous', because it technically isn't. My wording here was less precise than the original, but my point -- I'm afraid I didn't explain myself properly -- wasn't that the presence of the quantifier wasn't clear enough : the difficulty, I believe, lies in the idea that, for every finite sequence, there exists an algorithm to compute it, or more precisely, that with our definition of "algorithmically solvable", every particular instance of a problem can trivially be "algorithmically solvable" without the problem itself being "algorithmically solvable". The formal definition of e.g. a Turing machine makes this obvious, but from the point of view of intuition, this is a subtelty and not a triviality, as long as one isn't fully accustomed to it : an algorithm, in the usual sense, is a procedure for solving a class of problems.

I'm ok with he current wording and link, it's better that way.

Dabsent (talk) 18:29, 1 June 2008 (UTC)

Actually, the possibility of developing a concept of "effective calculability/noncalculability" that would apply to the calculation of a single individual integer — and therefore quite different from the now-standard notion of (non-)computability — was a major motivation for Rádo and Lin. Here's a quote from their 1965 paper:

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.

(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?

--r.e.s. (talk) 01:17, 2 June 2008 (UTC)

Hmm, if I understand this correctly, does this imply that e.g. there is a deterministic, although long-running, algorithm to determine the truth of any particular universal statement over a countable set with a computable predicate, such as Goldbach's conjecture? If so, this would appear to be in opposition to some of the argument at halting problem for why undecidability of the halting problem is "unsurprising" or "intuitive." Dcoetzee 08:19, 2 June 2008 (UTC)

Since "countable" doesn't mean "finite", I would say the answer to your question is "no". But when restricted to finitely many cases, an otherwise-unsolvable decision problem necessarily becomes solvable, because solvability, like computability, technically refers to the mere existence of the required algorithm — not to anyone actually "producing" the algorithm. Rado was evidently exploring the possibility that such an algorithm, though technically existing to compute a single finite instance (e.g. the single integer Σ(n₀) for some individual integer n₀), might nevertheless be logically unproduceable (my term), as distinct from merely being overwhelmingly impractical to produce and/or execute. As far as I know, this is still an open question.

--r.e.s. (talk) 13:35, 2 June 2008 (UTC)

Thanks R.e.s. for the link and information ; this is very interesting. I'll think about it.

If you wish to write more about this, by any means do : it certainly would be a valuable contribution to the article. However, I do not regard myself qualified for now and have no idea about the current state of research on this topic.

Regardind Dcoetzee's question : the idea of the procedure based on the busy-beaver is to produce a Turing machine (or some kind of program in a broader sense) able to test the validity of the conjecture for any given n. Let's say this program is of size s. You compute S(s), then run S(s) operations of your program. Now, if you consider a set of problems of the kind you described, all of whom can be described by programs of size less than s, you have indeed an algorithm able to solve them all, which embeds the value S(s) or equivalently an algorithm computing it : the same procedure applies to all of them. On the other hand, if you consider all the problems you mention, the size of the programs needed to test the conjectures on some values of n will not be bounded. A similar procedure would thus need the values of S for infinitely many s, that is, would need to embed an algorithm computing S, which doesn't exist. So : there needn't exist such a general procedure. I hope I understood the question correctly ?

Dabsent (talk) 15:56, 2 June 2008 (UTC)

Yes, but I was unclear - I meant to say that for any fixed Turing machine T, there is an algorithm (depending on T) to decide its halting problem; but now that I look at it again, this is actually rather obvious, since the constant algorithm returning either true or false would suffice (depending on T). The fact that once T is fixed you can solve its halting problem by first solving the busy beaver function for its state size is a rather roundabout way of doing it. Dcoetzee 16:53, 2 June 2008 (UTC)

I was apparently too hasty in replying "no" to Dcoetzee, according to Chaiten's article "Computing the Busy Beaver Function". There it's asserted that on information-theoretical grounds, for a conjecture with predicate P of the type Dcoetzee asked about, there exists a natural number m such that if P is verified for the finitely-many natural numbers n < m, then P must hold for all n:

"...it would suffice to have a bound on how far it is necessary to test P before settling the conjecture in the affirmative if no counterexample has been found, and of course rejecting it if one was discovered. Σ provides this bound, for if P has program-size complexity or algorithmic information content k, then it suffices to examine the first Σ(k +O(1)) natural numbers to decide whether or not P is always true." (p. 3)

However surprising this may be, it seems to answer Dcoetzee's question in the affirmative.

--r.e.s. (talk) 19:11, 2 June 2008 (UTC)

It seems to me that this is precisely what stands in the present article in the particular case of the Goldbach's conjecture (section Applications) ; it is easily generalized. But as I said the algorithm depends on the problem : it cannot become a general algorithm precisely because the busy beaver function is non-computable. So there is no algorithm capable of determining the truth "of any particular..." but "For every particular ..." there exists an algorithm. Quantifiers expressed in natural language are an infinite source of misunderstanding -- I apologize.

Dabsent (talk) 21:01, 2 June 2008 (UTC)

The Applications section does already nicely address such a result directly in terms of Rado's S function, rather than Σ, and without reference to algorithmic information theory. Actually, a (weaker) result in terms of Σ follows easily from the result in terms of S by using any of various inequalities established by Julstrom, et al., (e.g., S(n) ≤ Σ(3n+6)). I doubt that it's worth introducing any of these twists into that section, though, as it reads very well as is.

--r.e.s. (talk) 08:03, 3 June 2008 (UTC)

[edit] Article Cleanup Co-Ordination Point

Cleanup Co-ordination
	This article has recently been tagged as requiring cleanup to meet Wikipedia's quality standards. The article may have been flagged as needing cleanup because it has been suggested that: the article needs formatting, proofreading, or rephrasing in comprehensible English. the article has multiple overlapping problems. the article is very short and might need expanding, removal or merging with a broader article For a full list of possible problems see Wikipedia:Manual of Style. You can use this section to discuss possible resolution of the problem and achieve consensus for action. When there is a consensus that the article is cleaned up please remove the cleanup tag from the article
[edit] Discussion