display | more...
The Busy Beaver Problem is an Example for Turing machines. The Object is to find B(n), the maximum number of 1s that a Turing machine with n states with the alphabet {1,B} may print on a tape that is initially blank. It has to terminate.

In English: We search the number of 1's a Turing machine with n states can write. "This story starts around 1960. Tibor Rado, a professor at the Ohio State University, thought of a simple non-computable function besides the standard halting problem for Turing machines." from http://grail.cba.csuohio.edu/~somos/bb.html

Currently known values are B(1) = 1, B(2) = 4, B(3) = 6, and B(4) = 13. This, again, means a Turing Machine with 4 states can write a maximum of 13 "ones" on the tape. Values for n > 4 are currently unknown, but new Algorithms are created daily (there are still contests on it). You can look for Examples for n=6 and n=5 at http://www-csli.stanford.edu/hp/Beaver.html
Turing Machines can easily be simulated on most Windows- and Unix-Devices and you can download examples like B(5) 47,176,870 .

Log in or register to write something here or to contact authors.