You have been hired by Nanosoft. 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
"True" to its inputs) or rejects (says "False" 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 True (it's prime) or False (it's not prime). For
the purposes of this problem, the terms "program," "function,"
and "turing machine" are used interchangeably.
"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."
You sigh,
realizing that this would have made for a much less stressful
interview than yours: they had asked
you to do a complete rewrite of the
company's recent operating system!
"Here's what I need from you," continues Gill. "I
need a program which we'll call a Power of Two Decider Tester
(POTDT) in order to evaluate our interviewees' solutions.
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 True if the program it received was a correct
power-of-two-decider; otherwise the POTDT halts
and says False. We have a bunch of candidates arriving tomorrow, so I need this POTDT program written today by 5 PM."
Prove to Gill that this cannot be
done, not by 5 PM and not EVER! That is, prove that the POTDT
is undecidable by reduction from Halting.
As a guide to writing up uncomputability proofs, Here is a link to example write-ups of the proofs we did in class, that the functions "NIHC", "AIHC", and "EQ" are undecidable.
Note: the idea in this problems is similar to the
examples we did in which we reached a contradiction by creating a
halt-checker out of the program that we hope to prove
undecidable. In this case, you'll want to create a halt-checker
from a POTDT. Keep in mind that you can build any
function/program/machine you like in order to coax the POTDT into deciding whether a function P halts on an input w.
For this reason, simply citing Rice's theorem isn't allowed for
this problem! (It applies, but would be too easy!)
Submission:
Submit your proof in a plain-text file named
a12.txt .