All Questions
Tagged with busy-beaver computability
9 questions
0
votes
2
answers
101
views
Busy-Beaver-like question for WHILE-Programs (Theoretical CS)
So this is exam-task is called "Busy WHILE-Programs"
In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following:
...
1
vote
0
answers
89
views
What do we know about the reciprocal busy beaver series? [closed]
[Cross-posted from Math SE - apologies if this is not appropriate.]
I just read these excellent lecture notes by Scott Aaronson, and I found the second homework problem at the end to be incredibly ...
- 1,146
8
votes
1
answer
264
views
Wanted: Concrete Example of Busy Beaver Holdout
I understand from the Wikipedia page on the Busy Beaver problem that the Busy Beaver values for 5-state 2-symbol (quintuple) Turing-machines have not been determined, because there are 'holdout' ...
- 243
0
votes
0
answers
174
views
Busy Beaver Instruction Generator and Computablity
Question 1
From busy beaver uncomputablity it follows that we cannot design algorithm that for every input N, generate the appropriate set of TM instructions (the bit value of every bit in every card)...
- 101
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 ...
- 185
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) \...
- 249
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 ...
- 339
13
votes
3
answers
1k
views
Computation of busy beaver function
The busy beaver max shifts function, $S(n)$, has known values for $n\leq4$. Is there some basic, structural reason why it's inconceivable that we will ever find $S(n)$ for $n>4$? What is so ...
- 271
3
votes
1
answer
173
views
Given an n-state TM, can we construct an m-state TM (m>n) to determine if it halts?
BB(n) is roughly the maximum number of new states an n-state TM can run into without halting. So for a particular n, if we know BB(n), then we can find out if an arbitrary n-state TM halts by running ...
- 527