Algebraic Characterization of Computable and Complexity Theoretic Analysis

Walid Gomaa

Description

Algebraic Characterization of Computable and Complexity-Theoretic Analysis Walid Gomaa INRIA Nancy Grand-Est Research Centre CARTE team January 12, 2009 Walid Gomaa Algebraic Char. of Comp. and Complexity-Theoretic Analysis

• finite binary representation


• problem-oriented approach


• real numbers


• ?x ?n ?


• investigates real


• cauchy sequence

Sujets

• Real number
• Cauchy sequence

Informations

• Publié par: pefav
• Nombre de lectures: 33
• Langue: English

Extrait

AlgebraicCharacterizationofComputableand Complexity-TheoreticAnalysis WalidGomaa INRIANancyGrand-EstResearchCentre CARTEteam January12,2009 aWildGoamalAgebraciCha.rofCopm.andCopmelxtiy-hTeoretcinAaylsis

.IeRlaoCmupatitno Twoindependentapproaches:RecursiveAnalysis& NumericalAnalysis Recursiveanalysisinvestigatesrealcomputationusing classicalrecursiontheoryanditstechnologies Numericalanalysisisanalgorithmicproblem-oriented approach Comparewithclassicalrecursiontheoryvs.analysisand designofalgorithms Recursiveanalysisisthefocusofthispresentation.Itwas introducedbyTuring[1936],Grzegorczyk[1955],and Lacombe[1955]. aWildGoamalAgebraciCha.rofCopm.andCopmelxtiy-hTeoretcinAaylsis

eRrpseneatitnofoeRlauNmebr Givenx,severalrepresentations: s Binaryexpansion:BE x ∶ N →{ 0 , 1 } Leftcut:LC x ={ r ∈ Q ∶ r < x } CauchySequence:CF N →∶ x Q Recursively-wisetheyareequivalent However,theydifferonthesub-recursiveaswellasthe complexity-theoreticlevel aWildGoamalAgebraciCha.rofCopm.andCopmelxtiy-hTeoretcinAaylsis