13.4. HARDPROBLEMS 241
ina program,typeinthecontentsofgoofy.py? Putmorespecifically, doesgoofy.pyhaltwhengiven
itselfasitsinput?
Let’s thinkit through.We arerunninggoofy.pyandprovidinggoofy.pyasitsinput.Inthecallto
terminates, boththeprogramandthedatawillbea copy ofgoofy.py, soifgoofy.pyhaltswhen
givenitselfasinput,terminateswillreturntrue.Butifterminatesreturnstrue,goofy.pythengoes
intoaninfiniteloop,soitdoesn’thalt!That’s a contradiction;goofy.pycan’t bothhaltandnothalt.It’s
gottobeoneortheother.
Let’s tryit theotherwayaround. Supposethatterminatesreturnsa falsevalue.Thatmeansthat
goofy.py, whengivenitselfasinputgoesintoaninfiniteloop.Butassoonasterminatesreturnsfalse,
goofy.pyquits,soit doeshalt!It’s stilla contradiction.
If you’ve gottenyourheadaroundtheprevioustwo paragraphs,youshouldbeconvincedthatgoofy.py
representsanimpossibleprogram.Theexistenceofa functionmeetingthespecificationforterminates
leadstoa logicalimpossibility. Therefore,wecansafelyconcludethatnosuchfunctionexists.Thatmeans
thattherecannotbeanalgorithmforsolvingthehaltingproblem!
Thereyouhave it. Yourbosshasassignedyouanimpossibletask. Fortunately, yourknowledgeof
computerscienceissufficienttorecognizethis. Youcanexplaintoyourbosswhytheproblemcan’t be
solvedandthenmove ontomoreproductive pursuits.
13.4.3 Conclusion
I hopethischapterhasgivenyoua tasteofwhatcomputerscienceis allabout.Astheexamplesin thischapter
have shown,computerscienceis muchmorethan“just”programming.Themostimportantcomputerforany
computingprofessionalis stilltheonebetweentheears.
Hopefullythisbookhashelpedyoualongtheroadtobecominga computerprogrammer. Alongtheway,
I have triedtoit haspiqueyourcuriousityaboutthescienceofcomputing.If youhave masteredtheconcepts
inthistext,youcanalreadywriteinterestingandusefulprograms.Youshouldalsohave a firmfoundationof
thefundamentalideasofcomputerscienceandsoftwareengineering.Shouldyoubeinterestedinstudying
thesefieldsinmoredepth,I canonlysay“goforit.” Perhapsonedayyouwillalsoconsideryourselfa
computerscientist;I wouldbedelightedif mybookplayedevena verysmallpartinthatprocess.