13.4. HARDPROBLEMS 239
stepsit requiresto solve a givensizeproblem.Inthiscase,thedifficultyis determinedbythenumberofdisks
inthetower. Thequestionwewanttoanswerishowmanystepsdoesit take tomovea towerofsizen?
Justlookingatthestructureofouralgorithm,youcanseethatmovinga towerofsizenrequiresusto
move a towerofsizen 1 twice,oncetomove it off thelargestdisk,andagaintoputit backontop.If we
addanotherdisktothetower, weessentiallydoublethenumberofstepsrequiredtosolve it.Therelationship
becomesclearif yousimplytryouttheprogramonincreasingpuzzlesizes.
NumerofDisks StepsinSolution
1 1
2 3
3 7
4 15
5 31Ingeneral,solvinga puzzleofsizenwillrequire 2 n 1 steps.
Computerscientistscallthisanexponentialtimealgorithm,sincethemeasureofthesizeoftheproblem,
n, appearsintheexponentofthisformula.Exponentialalgorithmsblowupveryquicklyandcanonlybe
practicallysolvedforrelativelysmallsizes,evenonthefastestcomputers.Justtoillustratethepoint,if our
monksreallystartedwitha towerofjust 64 disksandmovedonediskeverysecond, 24 hoursa day, everyday,
withoutmakinga mistake, it wouldstilltake themover 580 billionyearstocompletetheirtask.Considering
thattheuniverseis roughly 15 billionyearsoldnow, I’mnottooworriedaboutturningtodustjustyet.
EventhoughthealgorithmforTowersofHanoiiseasytoexpress,it belongstoa classknownasin-
tractableproblems. Theseareproblemsthatrequiretoomuchcomputingpower(eithertimeormemory)
tobesolvedinpractice,exceptforthesimplestcases.Andinthissense,ourtoy-storepuzzledoesindeed
representa hardproblem.Butsomeproblemsareevenharderthanintractable,andwe’ll meetoneofthose
inthenextsection.
13.4.2 TheHaltingProblem.
Let’s justimaginefora momentthatthisbookhasinspiredyoutopursuea careerasa computerprofessional.
It’s now sixyearslater, andyouarea well-establishedsoftwaredeveloper. Oneday, yourbosscomestoyou
withanimportantnew project,andyouaresupposedtodropeverythingandgetrightonit.
It seemsthatyourbosshashada suddeninspirationonhowyourcompany candoubleitsproductivity.
You’ve recentlyhireda numberofratherinexperiencedprogrammers,anddebuggingtheircodeis takingan
inordinateamountoftime.Apparently, thesewet-behind-the-earsnewbiestendtoaccidentlywritea lotof
programswithinifiniteloops(you’ve beenthere,right?).They spendhalfthedaywaitingfortheircomputers
torebootsothey cantrackdownthebugs.Yourbosswantsyoutodesigna programthatcananalyzesource
codeanddetectwhetherit containsaninfiniteloopbeforeactuallyrunningit ontestdata.Thissoundslike
aninterestingproblem,soyoudecidetogive it a try.
Asusual,youstartbycarefullyconsideringthespecifications.Basically, youwanta programthatcanread
otherprogramsanddeterminewhetherthey containaninfiniteloop.Ofcourse,thebehaviorofa programis
determinednotjustbyitscode,butalsobytheinputit is givenwhenit runs.Inordertodetermineif thereis
aninfiniteloop,youwillhave toknow whattheinputwillbe.Youdecideonthefollowingspecification:
Program:HaltingAnalyzer
Inputs:A Pythonprogramfile.
Theinputfortheprogram.
Outputs:“OK”if theprogramwillevenutallystop.
“FAULTY”if theprogramhasaninfiniteloop.
Rightawayyounoticea coupleinterestingthingsaboutthisprogram.Oneis thatit is a programthat
examinesotherprograms.Youhave notwrittenmany ofthesebefore,butyouknow thatit’s nota problem
inprinciple. Afterall,compilersandinterpretersarecommonexamplesofprogramsthatanalyzeother
programs.Youcanrepresentboththeprogramthatis beinganalyzedandtheproposedinputtotheprogram
asPythonstrings.