edited by
615 views
0 0 votes

Let $\Gamma = \{0, 1, \sqcup\}$ be the tape alphabet for all TMs in this problem. Define the busy beaver function $BB: N \rightarrow N$ as follows. For each value of $k$, consider all $k-$state TMs that halt when started with a blank tape. Let $BB(k)$ be the maximum number of $1s$ that remain on the tape among all of these machines. Show that $BB$ is not a computable function.

Please log in or register to answer this question.

Position:
Show:

Related questions

0 0 votes
0 0 answers
580
580 views
admin asked Oct 20, 2019
580 views
Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the in...
0 0 votes
0 0 answers
521
521 views
admin asked Oct 19, 2019
521 views
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
0 0 votes
0 0 answers
379
379 views
admin asked Oct 19, 2019
379 views
Let $J = \{w \mid \text{either $w = 0x$ for some $x \in A_{TM},$ or $w = 1y\:$ for some $y \in \overline{A_{TM}}\:\:$}\}$. Show that neither $J$ nor $\overline{J}$ is Tur...
1 1 vote
0 0 answers
2.8k
2.8k views
admin asked Oct 19, 2019
2,849 views
Consider the problem of determining whether a Turing machine $M$ on an input w ever attempts to move its head left at any point during its computation on $w$. Formulate t...