版權資訊
計算理論基礎可計算性複雜性和語言書 名: 計算理論基礎可計算性複雜性和語言
作 者：(美國)MaritinD.Davis(美國)ElaineJ.Weyuker
出版社：人民郵電出版社
出版時間： 2009
ISBN: 9787115196576
開本： 16
定價: 79.00 元
內容簡介
《計算理論基礎可計算性複雜性和語言(英文版·第2版)》是理論計算機科學領域的名作。《計算理論基礎可計算性複雜性和語言(英文版·第2版)》是計算機及相關專業高年級本科生和研究生的理想教學參考書，對於計算機領域的專業人士也是很好的技術參考書。
作者簡介
MartinD．Davis，著名計算機科學家和數學家。1950年在普林斯頓大學獲得博士學位，與圖靈同門(導師均為計算科學大師AlonzoChurch)。後長期任教於紐約大學柯朗數學研究所。他是自動演繹理論先驅，還是DPLL算法的發明人之一，Post-Turing機更使其聲名遠播。除本書外，他還著有經典名著ComputabilityandUnsolvability。
RonSigal，資深軟體工程師。1983年在紐約大學獲得計算機科學博士學位。曾先後任教於紐約城市大學、義大利卡塔尼亞大學、耶魯大學、Hofstra大學。他參與的軟體項目有NASA的火星探路者、JBoss等。
ElaineJ．Weyuker，著名女計算機科學家。美國國家工程院院士、IEEE和ACM會士、AT&T院士、ACM婦女委員會主席、ACM執行委員，現任AT&T實驗室研究員。她的主要研究領域是軟體測試與可靠性。此前曾任紐約大學柯朗數學研究所計算機科學教授近20年。
編輯推薦
《計算理論基礎可計算性複雜性和語言(英文版·第2版)》是理論計算機科學領域不朽的名作之一，它成功地將該領域所涵蓋的可計算性理論、形式語言理論、複雜性理論和邏輯學這幾個分散主題完美地融為一體進行闡述，展示了它們之間的內在關聯，深刻地體現出理論計算機科學之美。
《計算理論基礎可計算性複雜性和語言(英文版·第2版)》內容嚴謹，可讀性強，配有豐富的習題，適合作為計算機和數學專業高年級本科生及研究生相關課程的教材，對於從事理論研究和軟體開發的專業技術人員也是不可多得的參考書。
目錄
Contents
IPreliminaries1
1.Setsandn-tuples1
2.Functions3
3.AlphabetsandStrings4
4.Predicates5
5.Quantifiers6
6.ProofbyContradiction8
7.MathematicalInduction9
Part1Computability15
2ProgramsandComputableFunctions17
1.AProgrammingLanguage17
2.SomeExamplesofPrograms18
3.Syntax25
4.ComputableFunctions28
5.MoreaboutMacros32
3PrimitiveRecursiveFunctions39
1.Composition39
2.Recursion40
3.PRCClasses42
4.SomePrimitiveRecursiveFunctions44
5.PrimitiveRecursivePredicates49
6.IteratedOperationsandBoundedQuantifiers52
7.Minimalization55
8.PairingFunctionsandG6delNumbers59
4AUniversalProgram65
1.CodingProgramsbyNumbers65
2.TheHaltingProblem68
3.Universality70
4.RecursivelyEnumerableSets78
5.TheParameterTheorem85
6.DiagonalizationandReducibility88
7.RicesTheorem95
*8.TheRecursionTheorem97
*9.AComputableFunctionThatIsNotPrimitiveRecursive105
5CalculationsonStrings113
1.NumericalRepresentationofStrings113
2.AProgrammingLanguageforStringComputations121
3.TheLanguagesandn126
4.Post-TuringPrograms129
5.Simulationofnin135
6.Simulationofin140
6TuringMachines145
1.InternalStates145
2.AUniversalTuringMachine152
3.TheLanguagesAcceptedbyTuringMachines153
4.TheHaltingProblemforTuringMachines157
5.NondeterministicTuringMachines159
6.VariationsontheTuringMachineTheme162
7ProcessesandGrammars169
1.Semi-ThueProcesses169
2.SimulationofNondeterministicTuringMachinesbySemi-ThueProcesses171
3.UnsolvableWordProblems176
4.Post'sCorrespondenceProblem181
5.Grammars186
6.SomeUnsolvableProblemsConcerningGrammars191
7.NormalProcesses192
8ClassifyingUnsolvableProblems197
1.UsingOracles197
2.RelativizationofUniversality201
3.Reducibility207
4.Setsr.e.RelativetoanOracle211
5.TheArithmeticHierarchy215
6.Post'sTheorem217
7.ClassifyingSomeUnsolvableProblems224
8.Rice'sTheoremRevisited230
9.RecursivePermutations231
Part2GrammarsandAutomata235
9RegularLanguages237
1.FiniteAutomata237
2.NondeterministicFiniteAutomata242
3.AdditionalExamples247
4.ClosureProperties249
5.Kleene'sTheorem253
6.ThePumpingLemmaandItsApplications260
7.TheMyhill-NerodeTheorem263
10Context-FreeLanguages269
1.Context-FreeGrammarsandTheirDerivationTrees269
2.RegularGrammars280
3.ChomskyNormalForm285
4.Bar-Hillel'sPumpingLemma287
5.ClosureProperties291
*6.SolvableandUnsolvableProblems297
7.BracketLanguages301
8.PushdownAutomata308
9.CompilersandFormalLanguages323
11Context-SensitiveLanguages327
1.TheChomskyHierarchy327
2.LinearBoundedAutomata330
3.ClosureProperties337
Part3Logic345
12PropositionalCalculus347
1.FormulasandAssignments347
2.TautologicalInference352
3.NormalForms353
4.TheDavis-PutnamRules360
5.MinimalUnsatisfiabilityandSubsumption366
6.Resolution367
7.TheCompactnessTheorem370
13QuantificationTheory375
1.TheLanguageofPredicateLogic375
2.Semantics377
3.LogicalConsequence382
4.Herbrand'sTheorem388
5.Unification399
6.CompactnessandCountability404
*7.G6del'sIncompletenessTheorem407
*8.UnsolvabilityoftheSatisfiabilityProbleminPredicateLogic410
Part4Complexity417
14AbstractComplexity419
1.TheBlumAxioms419
2.TheGapTheorem425
3.PreliminaryFormoftheSpeedupTheorem428
4.TheSpeedupTheoremConcluded435
15Polynomial-TimeComputability439
1.RatesofGrowth439
2.PversusNP443
3.Cook'sTheorem451
4.OtherNP-CompleteProblems457
Part5Semantics465
16ApproximationOrderings467
1.ProgrammingLanguageSemantics467
2.PartialOrders472
3.CompletePartialOrders475
4.ContinuousFunctions486
5.FixedPoints494
17DenotationalSemanticsofRecursionEquations505
1.Syntax505
2.SemanticsofTerms511
3.SolutionstoW-Programs520
4.DenotationalSemanticsofW-Programs530
5.SimpleDataStructureSystems539
6.InfinitaryDataStructureSystems544
18OperationalSemanticsofRecursionEquations557
1.OperationalSemanticsforSimpleDataStructureSystems557
2.ComputableFunctions575
3.OperationalSemanticsforlnfinitaryDataStructureSystems584
SuggestionsforFurtherReading593
NotationIndex595
Index599
……
