中文摘要：

本项目研究计算理论中关于扩充的计算模型、广义计算模型、可计算性、算法随机性和计算复杂性中的归约、结构和层谱理论的新方向及重要国际前沿问题，该研究是计算机科学的数学和逻辑基础的重要组成部分，而且其中的随机性研究还在密码学中有应用；我们研究可计算函数逼近论及算子理论及其在连续数学中的作用，以建立数值计算的理论基础；我们还将研究算法学习理论；这种研究是计算理论应用的新领域，它在逻辑程序设计及人工智能有潜

结论摘要：

本项目从归约、近似和算子作用的途径出发，用构造性方法、代数方法和概率工具研究了可计算性和算法理论的若干前沿课题。这些研究涉及到包括Turing计算的极限、新的计算模型、以及关于计算和算法研究的新方法特别是下界方法等计算理论当前的重大科学问题，和以蛋白质计算为背景的multiple sequence alignment这一基本应用问题。主要成果有提出在差层谱Turing度中Jump插值的研究；提出了有界Turing归约结构中连续性和可定义性的研究；极小公共整数分解问题的网络途径研究；发展了Valiant多项式插值归约和全息归约的理论；证明了对一切k，k-bit match circuits的非奇异特征矩阵构成一个乘法群，以及1和2-bit match gates在match circuits中是通用的；证明了2-bit quantum matchcircuits的通用性及给出quantum matchcircuits的一个范式定理；部分实现了生物信息中multiple sequence alignment计算问题的代数化，为研究这一重大应用问题算法复杂性下界奠定了基础。