Skip to main content

Questions tagged [busy-beaver]

The Busy Beaver problem is about finding the sequence of n-state Turing Machines writing the most 1's on a tape.

Filter by
Sorted by
Tagged with
6 votes
1 answer
1k views

Is a secondary TM sufficient to detect all loops?

Procedure: Start a secondary TM in parallel with the first, but have the second perform exactly 1 step each 2 steps the first TM performs (i.e. it runs at half speed). If the second machine ever ...
mafu's user avatar
  • 339
4 votes
1 answer
1k views

Busy Beaver problem - Proof by contradiction

I am trying to understand a proof regarding the Busy Beaver problem that uses a proof by contradiction approach to show $\sum(n)$ is Turing-uncomputable: Find $\sum(n) = max \{\sum(M) | M \in M(n) \...
Nubcake's user avatar
  • 249
4 votes
4 answers
11k views

Understanding proof for Busy Beaver being uncomputable

I found this proof on http://jeremykun.com/2012/02/08/busy-beavers-and-the-quest-for-big-numbers/ and have highlighted the part I don't understand in bold. (BB(n) is defined as the number of steps ...
x squared's user avatar
  • 185