Chapter 13.5, Problem 30E

Which of the following problems is a decision problem?

a) Is the sequence $a_1,a_2,\mathrm{...},a_n$ , of positive integers in increasing order?

b) Can the vertices of a simple graph G be colored using three colors so that no two adjacent vertices are the same color?

c) What is the vertex of highest degree in a graph G?

d) Given two finite-state machines, do these machines recognize the same language?

Let $B\left(n\right)$ be the maximum number of 1s that a Turing machine with n states with the alphabet $\left\{1,B\right\}$ may print on a tape that is initially blank. The problem of determining $B\left(n\right)$ for particular values of n is known as the busy beaver problem. This problem was first studied by Tibor Rado in 1962. Currently it is know that $B\left(2\right)=4,B\left(3\right)=6$ , and $B\left(4\right)=13$ , but $B\left(n\right)$ is not known for $n\ge 5$ grows rapidly; it is known that $B\left(5\right)\ge 4098$ and $B\left(6\right)\ge 3.5\times {10}^{18267}$ .