Computer Science 42
Principles and Practice of Computer Science
Fall 2011
Assignment 13 "lite": Proofs of Uncomputability!
Due Friday, December 9 at 11:59 PM
What to submit
Please submit your two proofs electronically. You can use plain
text, .pdf or .doc format, whichever is easiest
If you choose to use a non-text format (I'm told the graders prefer PDF), you'll have to submit your
files as "support files" in the submission system.
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 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 will be graded on clarity and precision of explanation. Please name your file problem1.txt (or
problem1.pdf or problem1.doc, depending on your type of file)
- Problem 2 (INDIVIDUAL) [25 points]: "Drat!" says Gill upon hearing the news. "OK, then, in that case,
maybe we still save time and screen out the real duds by having the computer check whether their program can give at least one correct yes answer. I'd like you to
write an Accepts-Some-Power-of-Two Tester (ASPOTT). Given their program, ASPOTT should eventually halt and say yes if their program will correctly say yes for at least one string of 0's whose length is a power of two, and ASPOTT should eventually halt and say no if there's no power-of-two input for which their program says yes. 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.txt (or problem2.pdf or problem2.doc, as appropriate).
Note: The idea in both of these problems is similar to the examples
we did in class, where we created a contradiction by building a
halt-checker out of the program that we hope to prove uncomputable. In this case, you'll
want to create a halt-checker from a POTDT and a halt-checker from ASPOTT. Keep in mind that a halt checker given program P and input w, can use these build any other function/program/code it likes and use that to coax POTDT and
ASPOTT into deciding whether a program P halts on an input w.