Overview / Logistics

In this homework we'll explore functions that are at the edge of computability.

There are no JFLAP problems on this homework. You should submit a single typed document with the answers to each question. You can use Microsoft Word, LaTeX, or anything else you're comfortable with.

---

Problem 1 (3 Points)

We'll explore something called the Collatz conjecture in this problem. This is a seemingly innocuous math problem that's very easy to state, but it has served as a "black hole" that has sucked in many an aspiring mathematician, because it still eludes a proof after almost a century from when it was first posed. The conjecture is as follows: given the following piecewise function

It is thought that it is always possible to iterate this function and end up at a 1, starting at any natural number. Take the following examples, which all end at a 1 (in fact, it's been exhaustively verified that every natural number up to 2⁶⁸ eventually ends up at 1)

Hence, the problem is sometimes referred to as the "3x + 1" problem

The author of this popular math article on the conjecture recommends that we do not try to solve this math problem.. However, let's cheat for a moment and suppose that Halt_TM is decidable (it most certainly is not, but we can go into a parallel universe where it is for a moment and see what happens). Provide a high level description of a machine that outputs whether the Collatz conjecture is true or not, using this hypothetical decidable Halt_TM decider to help you.

Hint: To nail this, you'll have to use Halt_TM more than once!

---

Problem 2 (5 Points)

We're going to think about some very large numbers now. Consider a function over the natural numbers known as the Busy Beaver Function BB(N), whose output value at N is the maximum number of steps^[1] that any Turing machine of a special form with N states can take before halting, if it halts. The Turing machines used in the Busy Beavers have the following properties

Busy Beaver Format

• The tape alphabet Γ is {0, 1}
• The tape starts off with all 0's stretching to infinity on the right and left side (there is otherwise no input)
• The machine can only move left or right (there is no stay)
• There is a single accept state that does not count towards the N states that are used.

^[1] Technically I'm referring here to something called the "Radó shift function," but it's related and makes our proofs slightly easier

1. (1 Point) What input/output pair of the Busy Beaver function can you bound from below by the following Turing machine? What value is the lower bound? (This value actually turns out to achieve the maximum for this number of states)

   

   Click here to download the JFLAP file, which you can use to help answer this question. Note that JFLAP does not have the capability to start the tape with all 0s, so blanks are treated as 0s in this machine and are redundant with all of the 0 rules.

2. (2 Points) A function from the natural numbers to the natural numbers is computable if, starting with the input to the function, the machine halts with just the output to the function on the tape. Prove that the busy beaver function is not computable, supposing by contradiction that it is computable and using it as a subroutine to decide something undecidable.
3. (2 Points) Suppose for a moment that the halting problem is decidable. Then, it would be theoretically possible to compute BB(N) by the following very slow but simple algorithm
   • Start BB(N) at 0
   • For each machine M with N states in busy beaver format
     • If M halts, run M and record the number of steps s that it takes. If s > BB(N), then update BB(N) to be s
   How many Turing machines would you have to check in the outer loop for BB(N)?

   Hint: How many possible arrows can you draw when you're at a particular state and you see a 0? How about if you see a 1? How would you multiply these possibilities across all states? (Go back and think about the fundamental counting principle if you're rusty)

---