《信息科學(xué)類專業(yè)英語(yǔ)》課件第1章

Lesson1TowardsaMathematicalScienceofComputation(第一課數(shù)學(xué)化的計(jì)算科學(xué)的前景)

Vocabulary(詞匯)ImportantSentences(重點(diǎn)句)QuestionsandAnswers(問(wèn)答)Problems(問(wèn)題)1Introduction

InthispaperIshalldiscusstheprospectsforamathematicalscienceofcomputation.Inamathematicalscience,Itispossibletodeducefromthebasicassumptions,theimportantpropertiesoftheentitiestreatedbythescience.Thus,fromNewton’slawofgravitationandhislawsofmotion,onecandeducethattheplanetaryorbitsobeyKepler’slaws.

Whataretheentitieswithwhichthescienceofcomputationdeals?

Whatkindsoffactsabouttheseentitieswouldweliketoderive?

Whatarethebasicassumptionsfromwhichweshouldstart?

Whatimportantresultshavealreadybeenobtained?

Howcanthemathematicalsciencehelpinthesolutionofpracticalproblems?

Iwouldliketoproposesomepartialanswerstothesequestions.Thesepartialanswerssuggestsomeproblemsforfuturework.First,Ishallgivesomeverysketchygeneralanswerstothequestions.Then,Ishallpresentsomerecentresultsonthreespecificquestions.Finally,Ishalltrytodrawsomeconclusionsaboutpracticalapplicationsandproblemsforfuturework.2WhataretheEntitieswithWhichComputerScienceDeals?

Theseareproblems,procedures,dataspaces,programsrepresentingproceduresinparticularprogramminglanguages,andcomputers.

Aproblemisdefinedbythecriterionwhichdetermineswhetheraproposedsolutionisaccepted.Onecanunderstandaproblemcompletelywithouthavinganymethodofsolution.Proceduresareusuallybuiltupfromelementaryprocedures.Whattheseelementaryproceduresmaybe,andhowmorecomplexproceduresareconstructedfromthem,isoneofthefirsttopicsincomputerscience.Thissubjectisnothardtounderstandsincethereisaprecisenotionofacomputablefunctiontoguideus,andcomputabilityrelativetoagivencollectionofinitialfunctionsiseasytodefine.

Proceduresoperateonmembersofcertaindataspacesandproducemembersofotherdataspaces,usingingeneralstillotherdataspacesasintermediates.Anumberofoperationsareknownforconstructingnewdataspacesfromsimplerones,butthereisasyetnogeneraltheoryofrepresentabledataspacescomparabletothetheoryofcomputablefunctions.

Programsaresymbolicexpressionsrepresentingprocedures.Thesameproceduremayberepresentedbydifferentprogramsindifferentprogramminglanguages.Weshalldiscusstheproblemofdefiningaprogramminglanguagesemanticallybystatingwhatprocedurestheprogramsrepresent.Asforthesyntaxofprogramminglanguages,theruleswhichallowustodeterminewhetheranexpressionbelongstothelanguagehavebeenformalized,butthepartsofthesyntaxwhichrelatecloselytothesemanticshavenotbeensowellstudied.Theproblemoftranslatingproceduresfromoneprogramminglanguagetoanotherhasbeenmuchstudied,andweshalltrytogiveadefinitionofthecorrectnessofthetranslation.

Computersarefiniteautomata.Fromourpointofview,acomputerisdefinedbytheeffectofexecutingaprogramwithgiveninputonthestateofitsmemoryandonitsoutputs.Computersciencemuststudythevariouswayselementsofdataspacesarerepresentedinthememoryofthecomputerandhowproceduresarerepresentedbycomputerprograms.Fromthispointofview,mostofthecurrentworkonautomatatheoryisbesidethepoint.3WhatKindsofFactsaboutProblems,Procedures,DataSpaces,Programs,andComputersWouldWeLiketoDerive?

Primarily,wewouldliketobeabletoprovethatgivenproceduressolvegivenproblems.However,provingthismayinvolveprovingawholehostofotherkindsofstatementsuchas:

1.Twoproceduresareequivalent,i.e.computethesamefunction.

2.Anumberofcomputablefunctionssatisfyacertainrelationship,suchasanalgebraicidentityoraformulaofthefunctionalcalculus.

3.Acertainprocedureterminatesforcertaininitialdata,orforallinitialdata.

4.Acertaintranslationprocedurecorrectlytranslatesproceduresbetweenoneprogramminglanguageandanother.

5.Oneprocedureismoreefficientthananotherequivalentprocedureinthesenseoftakingfewerstepsorrequiringlessmemory.

6.Acertaintransformationofprogramspreservesthefunctionexpressedbutincreasestheefficiency.

7.Acertainclassofproblemsisunsolvablebyanyprocedure,orrequiresproceduresofacertaintypeforitssolution.4WhataretheAxiomsandRulesofInferenceofAMathematicalScienceofComputation?

Ideallywewouldlikeamathematicaltheoryinwhicheverytruestatementaboutprocedureswouldhaveaproof,andpreferablyaproofthatiseasytofind,nottoolong,andeasytocheck.In1931,G?delprovedaresult,oneofwhoseimmediateconsequencesisthatthereisnocompletemathematicaltheoryofcomputation.Givenanymathematicaltheoryofcomputationtherearetruestatementsexpressibleinitwhichdonothaveproofs.[1]Nevertheless,wecanhopeforatheorywhichisadequateforpracticalpurposes,likeprovingthatcompilerswork;theunprovablestatementstendtobeofarathersweepingcharacter,suchasthatthesystemitselfisconsistent.

ItisalmostpossibletotakeoveroneofthesystemsofelementarynumbertheorysuchasthatgiveninMostowski’sbookSentencesUndecidableinFormalizedArithmetic,sincethecontentofatheoryofcomputationisquitesimilar.Unfortunately,thisandsimilarsystemsweredesignedtomakeiteasytoprovemeta-theoremsaboutthesystem,ratherthantoprovetheoremsinthesystem.Asaresult,theintegersaregivensuchaspecialrolethattheproofsofquiteeasystatementsaboutsimpleprocedureswouldbeextremelylong.

Thereforeitisnecessarytoconstructanew,thoughsimilar,theoryinwhichneithertheintegersnoranyotherdomain(e.g.stringsofsymbols)aregivenaspecialrole.Somepartialresultsinthisdirectionaredescribedinthispaper.Namely,aninteger-freeformalismfordescribingcomputationshasbeendevelopedandshowntobeadequateinthecaseswhereitcanbecomparedwithotherformalisms.Somemethodsofproofhavebeendeveloped,butthereisstillagapwhenitcomestomethodsofprovingthataprocedureterminates.Thetheoryalsorequiresextensioninordertotreatthepropertiesofdataspaces.5WhatImportantResultshavebeenObtainedRelevanttoaMathematicalScienceofComputation?

In1936,thenotionofacomputablefunctionwasclarifiedbyTuring,andheshowedtheexistenceofuniversalcomputersthat,withanappropriateprogram,couldcomputeanythingcomputedbyanyothercomputer.[2]Allourstoredprogramcomputers,whenprovidedwithunlimitedauxiliarystorage,areuniversalinTuring’ssense.Insomesubconscioussenseeventhesalesdepartmentsofcomputermanufacturersareawareofthis,andtheydonotadvertisemagicinstructionsthatcannotbesimulatedoncompetitorsmachines,butonlythattheirmachinesarefaster,cheaper,havemorememory,orareeasiertoprogram.

Thesecondmajorresultwastheexistenceofclassesofunsolvableproblems.ThiskeepsallbutthemostignorantofusoutofcertainQuixoticenterprisessuchastryingtoinventadebuggingprocedurethatcaninfalliblytellifaprogrambeingexaminedwillgetintoaloop.[3]Laterinthispaperweshalldiscusstherelevanceoftheresultsofmathematicallogiconcreativesetstotheproblemofwhetheritispossibleforamachinetobeasintelligentasahuman.Inmyopinionitisveryimportanttobuildafirmerbridgebetweenlogicandrecursivefunctiontheoryontheoneside,andthepracticeofcomputationontheother.

Muchoftheworkonthetheoryoffiniteautomatahasbeenmotivatedbythehopeofapplyingittocomputation.Ithinkthishopeismostlyinvainbecausethefactoffinitenessisusedtoshowthattheautomatonwilleventuallyrepeatastate.However,anyonewhowaitsforanIBM7090torepeatastate,solelybecauseitisafiniteautomatonisinforaverylongwait.6HowCanaMathematicalScienceofComputationHelpintheSolutionofPracticalProblems?

Naturally,themostimportantapplicationsofasciencecannotbeforeseenwhenitisjustbeginning.However,thefollowingapplicationscanbeforeseen.

1.Atpresent,programminglanguagesareconstructedinaveryunsystematicway.Anumberofproposedfeaturesareinvented,andthenweargueaboutwhethereachfeatureisworthitscost.Abetterunderstandingofthestructureofcomputationsandofdataspaceswillmakeiteasiertoseewhatfeaturesarereallydesirable.

2.Itshouldbepossiblealmosttoeliminatedebugging.Debuggingisthetestingofaprogramoncasesonehopesaretypical,untilitseemstowork.Thishopeisfrequentlyvain.Insteadofdebuggingaprogram,oneshouldprovethatitmeetsitsspecifications,andthisproofshouldbecheckedbyacomputerprogram.Forthistobepossible,formalsystemsarerequiredinwhichitiseasytowriteproofs.Thereisagoodprospectofdoingthis,becausewecanrequirethecomputertodomuchmoreworkincheckingeachstepthanahumaniswillingtodo.Therefore,thestepscanbebiggerthanwithpresentformalsystems.

Vocabulary1．mathematicalscienceofcomputation這里mathematical應(yīng)當(dāng)是限定scienceofcomputation的,可以翻譯成數(shù)學(xué)(化)的計(jì)算科學(xué)，意指在計(jì)算科學(xué)中利用數(shù)學(xué)方法。2．sketchyadj.粗略的。3．prospectn.景象，景色，前景，前途視野；展望；眺望；預(yù)期；指望vt.勘探，勘察，找礦；對(duì)……進(jìn)行仔細(xì)調(diào)查。4．deducevt.推論,演繹出。5．semanticsn.語(yǔ)義學(xué)。6．a(chǎn)utomatan.自動(dòng)操作,自動(dòng)控制。7．subconsciousadj.下意識(shí)的;潛意識(shí)的。8．infallibleadj.不會(huì)犯錯(cuò)誤的,無(wú)過(guò)失的;極準(zhǔn)確的,極精確的;絕對(duì)可靠的;萬(wàn)無(wú)一失的；永遠(yuǎn)有效的。9．quixoticadj.堂吉柯德式的,空想的,不切實(shí)際的。10．sweepingadj.包羅萬(wàn)象的,一掃而光的;籠統(tǒng)的,泛泛的,一概而論的;影響廣泛的；大范圍的。

[1]In1931,G?delprovedaresult,oneofwhoseimmediateconsequencesisthatthereisnocompletemathematicaltheoryofcomputation.Givenanymathematicaltheoryofcomputationtherearetruestatementsexpressibleinitwhichdonothaveproofs.

在1913年，歌德爾證明了一個(gè)結(jié)果，這個(gè)結(jié)果的一個(gè)直接推論就是不存在完備的計(jì)算數(shù)學(xué)理論。給定的任何計(jì)算數(shù)字理論中必定存在可以表達(dá)為真的語(yǔ)句，但不存在它的證明。ImportantSentences

[2]In1936,thenotionofacomputablefunctionwasclarifiedbyTuring,andheshowedtheexistenceofuniversalcomputersthat,withanappropriateprogram,couldcomputeanythingcomputedbyanyothercomputer.

在1936年,圖靈澄清了可計(jì)算函數(shù)的概念，并且證明了通用計(jì)算機(jī)的存在，通過(guò)適當(dāng)?shù)某绦?，可以做任何其他?jì)算機(jī)能夠做的計(jì)算。

[3]Thesecondmajorresultwastheexistenceofclassesofunsolvableproblems.ThiskeepsallbutthemostignorantofusoutofcertainQuixoticenterprisessuchastryingtoinventadebuggingprocedurethatcaninfalliblytellifaprogrambeingexaminedwillgetintoaloop.

第二個(gè)主要結(jié)果是存在一類不可解的問(wèn)題。這個(gè)結(jié)果就使得我們大多數(shù)人，除了那些最無(wú)知的人之外，不幻想那些唐吉柯德式的事業(yè)，例如試圖發(fā)明能夠絕對(duì)無(wú)誤地檢驗(yàn)一個(gè)程序是否會(huì)陷入死循環(huán)的查錯(cuò)過(guò)程。themostignorantofus，我們當(dāng)中最無(wú)知的人。

(1)?Accordingtothetext,theentitiesthatComputerSciencedealswithmaynotinclude().

A.?problems

B.?procedures

C.?programminglanguages

D.?computersQuestionsandAnswers

(2)?Accordingtothetext,whatisoneofthefirsttopicsincomputerscience?()

A.?Whattheseelementaryproceduresmaybe?

B.?Howmorecomplexproceduresareconstructedfromelementaryprocedures?

C.?Howtounderstandaproblemcompletely?

D.?Whatelementaryproceduresmaybe,andhowmorecomplexproceduresareconstructedfromthem?

(3)?Whichofthefollowingstatementsdescribestherelationshipbetweenproceduresandprogramminglanguages.()

A.?Thesameproceduremayberepresentedbydifferentprogramsindifferentprogramminglanguages.

B.?Theproblemoftranslatingproceduresfromoneprogramminglanguagetoanotheriseasy.

C.Theproblemofdefiningaprogramminglanguagesemanticallycanbesolvedbystatingwhatprocedurestheprogramsrepresent.

D.?Computersciencemuststudyhowproceduresarerepresentedbycomputerprograms.

(4)?Whichofthefollowingstatementsiswrongfordescribingtherelationshipofproceduretodataspaceandprogramminglanguages?()

A.?Proceduresoperateonmembersofcertaindataspacesandproducemembersofotherdataspaces.

B.?Programsaresymbolicexpressionsrepresentingprocedures.

C.?Thesameproceduremayberepresentedbydifferentprogramsindifferentprogramminglanguages.

D.?Programminglanguagesareconstructedfromdifferentprocedure.

(5)Accordingtothetext,whichofthefollowingstatementsiswrongaboutcomputer?()

A.?Computersarefiniteautomata.

B.?Acomputerisdefinedbytheeffectofexecutingaprogramwithgiveninputonthestateofitsmemoryandonitsoutputs.

C.?Muchoftheworkonthetheoryoffiniteautomataisfruitfulwhenitisappliedtocomputa