資源描述:
《Essentials of Theoretical Computer Science - F. D. Lewis》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。
1、winxos11-01-28winxos11-01-28EssentialssofTheoreticalheoreticComputerterSciencencF.D.LewisUniversityofKentuckyHowtoNavigateTableofThisTextContentsCONTENTSOTitlePageCopyrightNoticePrefaceCOMPUTABILITYIntroductionTheNICEProgrammingLanguageTuringMachinesASmallerProgrammingLanguageEquiva
2、lenceoftheModelsMachineEnhancementTheThesesofChurchandTuringHistoricalNotesandReferencesProblemsUNSOLVABILITYIntroductionArithmetizationPropertiesoftheEnumerationUniversalMachinesandSimulationSolvabilityandtheHaltingProblemReducibilityandUnsolvabilityEnumerableandRecursiveSetsHistor
3、icalNotesandReferencesProblemsCOMPLEXITYIntroductionMeasuresandResourceBoundsComplexityClassesReducibilitiesandCompletenessTheClassesPandNPIntractableProblemsHistoricalNotesandReferencesProblemsAUTOMATAIntroductionFiniteAutomataClosurePropertiesNondeterministicOperationRegularSetsan
4、dExpressionsDecisionProblemsforFiniteAutomataPushdownAutomataUnsolvableProblemsforPushdownAutomataLinearBoundedAutomataHistoricalNotesandReferencesProblemsLANGUAGESIntroductionGrammarsLanguagePropertiesRegularLanguagesContextFreeLanguagesContextFreeLanguagePropertiesParsingandDeterm
5、inisticLanguagesSummaryHistoricalNotesandReferencesProblemsCOMPUTABILITYCPBYBeforeexaminingtheintrinsicnatureofcomputationwemusthaveapreciseideaofwhatcomputationmeans.Inotherwords,weneedtoknowwhatwe’retalkingabout!Todothis,weshallbeginwithintuitivenotionsoftermssuchascalculation,com
6、putingprocedure,andalgorithm.Thenweshallbeabletodevelopaprecise,formalcharacterizationofcomputationwhichcapturesallofthemodernaspectsandconceptsofthisimportantactivity.Partofthisdefinitionalprocessshallinvolvedevelopingmodelsofcomputation.Theywillbepresentedwithemphasisupontheirfini
7、tenatureandtheircomputationaltechiques,thatis,theirmethodsoftransforminginputsintooutputs.Inclosing,weshallcompareourvariousmodelsanddiscusstheirrelativepower.Thesectionsareentitled:TheNICEProgrammingLanguageTuringMachinesASmallerProgrammingLanguageEquivalenceoftheModelsMachineEnhan
8、cementTheThesesofCh