Talk:Busy beaver

From Wikipedia, the free encyclopedia

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)

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

[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

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

[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