We invite one and all to compete in ByteCode 2007 which is an online programming contest.
Please check our page out for further info:
pragyan.org/bytecode/
created
last reply
- 7
replies
- 263
views
- 5
users
- 2
links
We invite one and all to compete in ByteCode 2007 which is an online programming contest.
Please check our page out for further info:
pragyan.org/bytecode/
Here's a suggestion:
Problem code: BUSYBVR
<- insert a short description of Turing machines ripped from Wikipedia or something ->
Despite their apparent simplicity, Turing machines are the yardstick by which computability is judged: if something is computable by a Turing machine, it's considered computable; otherwise, it's not computable at all.
In this problem, we want you to find out the maximum number of ones that any Turing machine with k states will leave on an initially blank tape (all zeroes) before halting.
Input
The first line of the input file is the number of test cases T (about 100).
It's then followed by T lines consisting of a single number k, 1 <= k <= 100.
Output
For each integer k, your program should output the maximum number of ones that any Turing machine with k states will leave on a blank tape.
Sample Input
2
2
4
Sample Output
4
13
Sorry, that was meant to be a joke. The rate of growth of that function may look modest for k <= 4, but for k = 5 it's still an open problem, and for k = 6 it's known to be more than 10^865! See http://en.wikipedia.org/wiki/Busy_beaver.
Topic | Category | Replies | Views | Activity |
---|---|---|---|---|
Hosting a competition on SPOJ | Off-topic | 1 | 148 | Apr 9 |
How do I change my profile picture? | Off-topic | 1 | 12 | 1d |