Essentials of Theoretical Computer Science - F. D. Lewis

《Essentials of Theoretical Computer Science - F. D. Lewis》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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