资源描述：
《计算理论导论(英文版)前言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、11HistoryofcomputationandcomputationalmodelsForthousandsofyears,computingwasdonewithpenandpaper,chalkandslate,orevenmentally,sometimeswiththeaidoftables.Thetheoryofcomputationbeganearlyinthetwentiethcentury(the1930s),beforemodernelectroniccomputershadbe
2、eninvented.Atthattime,mathematiciansweretryingtofindwhichmathproblemscouldbesolvedbysimplemethodsandwhichcouldnot.Thefirststepwastodefinewhatwasmeantbya"simplemethod"forsolvingaproblem,implyinganeedforaformalmodelofcomputation.2computationalmodelsSevera
3、ldifferentcomputationalmodelsweredevisedbytheseearlyresearchers.Onemodel,theTuringmachine,storescharactersonaninfinitelylongtape,withonesquareatanygiventimebeingscannedbyaread/writehead.Anothermodel,recursivefunctions,usesfunctionsandfunctioncomposition
4、tooperateonnumbers.Thelambdacalculususesasimilarapproach.Stillothers,includingMarkovalgorithmsandPostsystems,usegrammar-likerulestooperateonstrings.Alloftheseformalismswereshowntobeequivalentincomputationalpower--thatis,anycomputationthatcanbeperformedw
5、ithonecanbeperformedwithanyoftheothers.Theyarealsoequivalentinpowertothefamiliarelectroniccomputer,ifonepretendsthatelectroniccomputershaveunboundedmemory.Indeed,itiswidelybelievedthatall"proper"formalizationsoftheconceptofalgorithmwillbeequivalentinpow
6、ertoTuringmachines;thisisknownastheChurch-Turingthesis.Ingeneral,questionsofwhatcanbecomputedbyvariousmachinesareinvestigatedincomputabilitytheory.3WhatistheoryofcomputationThephrasetheoryofcomputationreferstothestudyofthemathematicalfoundationsofcomput
7、ation:whatisanappropriatemathematicalmodelofacomputer,whattypesofcomputationsarepossibleinthemodel,whattypesarenot,theinherentcomplexityofcertaincomputations,soonandsoforth.Perhapssurprisingly,manyconceptsfromthetheoryofcomputationareoffundamentalimport
8、anceinotherareasofcomputerscience,suchascomputationallinguistics,compilerdesign,hardwaredesign,object-orienteddesign,cryptography,andeventhesyntaxofsomeUNIXcommands.42WhatthecourseisaboutInthiscoursewewillinvestigatevariousmodels
