Speed-up theorems in type-2 computations using oracle Turing machines

DOI10.1007/s00224-009-9182-xzbMath1185.68331OpenAlexW2169321137MaRDI QIDQ733754

Chung-Chih Li

Publication date: 19 October 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-009-9182-x

zbMATH Keywords

oracle Turing machinespeed-up theoremtype-2 computation

Mathematics Subject Classification ID

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recursion on the countable functionals
• Classical recursion theory. The theory of functions and sets of natural numbers
• Theories of computational complexity
• Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals
• Simple quadratures in the complex plane
• Recursive Functionals and Quantifiers of Finite Types I
• The Mathematical Work of S.C.Kleene
• A new Characterization of Type-2 Feasibility
• On the Computational Complexity of Algorithms
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Turing-Machine Computable Functionals of Finite Types II^†
• On Effective Procedures for Speeding Up Algorithms
• Computational speed-up by effective operators
• Recursive Functionals and Quantifiers of Finite Types II

This page was built for publication: Speed-up theorems in type-2 computations using oracle Turing machines