240 CHAPTER13. ALGORITHMANALYSISANDDESIGN

Thesecondthingyounoticeisthatthisdescriptionsoundssimilartosomethingyou’ve heardabout
before.Hmmm...a programthatdetermineswhetheranotherprogramwillhaltornot.Suddenlyit dawnson
you:thisis knownastheHaltingProblem, andit’s unsolvable.Thereis nopossiblealgorithmthatcanmeet
thisspecification!
How doweknow thatthereis nosolutiontothisproblem?Thisis a questionthatallthedesignskillsin
theworldwillnotanswerforyou.Designcanshow thatproblemsaresolvable,butit canneverprove thata
problemis notsolvable.To dothat,weneedtouseouranalyticalskills.
Onewayto prove thatsomethingis impossibleis to firstassumethatit is possibleandshow thatthisleads
toa contradiction.Mathematicianscallthisproofbycontradiction.We’ll usethistechniquetoshow thatthe
haltingproblemcannotbesolved.
We beginbyassumingthatthereissomealgorithmthatcandetermineif a programterminateswhen
executedona particularinput.If suchanalgorithmcouldbewritten,wecouldpackageit upina function.

def terminates(program, inputData):

program and inputDataare both strings

RETURNS trueif program would halt when run with inputData

as its input.

Ofcourse,I can’t actuallywritethefunction,butlet’s justassumethatthisfunctionexists.
Usingtheterminatesfunction,wecanwritea goofyprogram.

goofy.py

import string

def terminates(program, inputData):

program and inputDataare both strings

RETURNS trueif program would halt when run with inputData

as its input.

def main():

Read a programfrom standard input

lines = []
print "Type in a program(type ’done’ to quit)."
line = raw_input("")
while line != "done":
lines.append(line)
line = raw_input("")
testProg = string.join(lines, "\n")

# If program haltson itself as input, go into an infiniteloop

if terminates(testProg,testProg):

while 1: pass

main()

Thefirstthinggoofy.pydoesis readina programtypedbytheuser. Thisis accomplishedwitha sentinel
loopthataccumulateslinesina listoneata time. Thestring.joinfunctionthenconcatenatesthe
linestogetherusinga newlinecharacter("

n") betweenthem. Thiseffectivelycreatesa multi-linestring
representingtheprogramthatwastyped.
Goofy.pythencallstheterminatesfunctionandsendstheinputprogramasboththeprogramto
testandtheinputdatafortheprogram.Essentially, thisis a testtoseeif theprogramreadfromtheinput
terminateswhengivenitselfasinput. Thepassstatementactuallydoesnothing;if theterminates
functionreturnstrue,goofy.pywillgointoaninfiniteloop.
OK,thisseemslike a sillyprogram,but thereis nothingin principlethatkeepsusfromwritingit,provided
thattheterminatesfunctionexists.Goofy.pyis constructedinthispeculiarwaysimplytoillustratea
point.Here’s themilliondollarquestion:Whathappensif werungoofy.pyand,whenpromptedtotype