Assignment 12: Proofs of Uncomputability!
Due Tuesday, December 1 at 11:59 PM

What to submit

Setup: Millisoft!

You have been hired by Millisoft, a large software company with numerous famous products that include Millisoft Sentence (word processing software), Succeed (a spreadsheet program), Energydot (presentation software), among others.

Your boss, Gill Bates, drops by your spacious cubicle sipping a refreshing and stimulating Jolt Cola ("All the sugar, and twice the caffeine!"). Gill begins by reminding you that a decider is a program that takes an input and eventually halts and accepts (says "yes" to its inputs) or rejects (says "no" to its input). For example, a decider for the prime numbers would take a number, perhaps encoded in binary, as input and would eventually halt saying "yes" (it's prime) or "no" (it's not prime).

• Problem 1 (INDIVIDUAL OR PAIR) [25 points]: "OK, so here's your first task," says Gill. "We have decided to change our interview process -- we're going to ask all of our job candidates to see if they can write a decider which takes as input a string of 0's and determines whether the number of 0's present is a power of 2. Here's what I need from you," continues Gill. "I need a program which we'll call a Power of Two Decider Tester (POTDT). The POTDT takes as input a program. The POTDT then decides whether P is a legitimate decider for strings whose length is a power of 2. That is, the POTDT eventually halts and says yes if the program it received was a correct submission for this competition and otherwise the POTDT halts and says no. I need this POTDT program written by tomorrow at 6 AM." Prove to Gill that this cannot be done, not by 6 AM and not EVER! You may use diagrams to help explain your proof, but your proof must be clear, precise, and rigorous. Your submission on this and the following problem will be graded on clarity and precision of explanation.  Please name your file problem1.pdf.
  
  
• Problem 2 (INDIVIDUAL) [25 points]: "Drat!" says Gill upon hearing the news. "OK, then, in that case, I'd like you to write a program called a Regularity Checker (RC). The Regularity Checker takes as input a program P (e.g., a Turing Machine) and it needs to determine whether or not the set of strings accepted by P is a regular language. The RC must always halt with an answer of yes or no!" Prove to Gill that this too is impossible. Again, you may use pictures to help you explain your proof, but your proof must be clear, precise, and rigorous.  Please name your file problem2.pdf.
  
  Note that if a turing machine runs forever on an input, that input is considered REJECTED for the purposes of defining the language that the TM accepts. This might help!