Mathematical Sciences: Frequency Approach to Approximating Algorithms

提出的研究围绕两个一般性问题：1)根据频率算法对问题进行完全分类；2)完全理解频率可计算问题的递归理论性质。计算，正如它今天的实践，是一个互动的本质。20年前的模式是给计算机一个程序，然后运行直到它得到答案，而现在的模式不同了，程序在继续之前经常暂停并要求输入。因此，真正的计算模型，正如它被实践的那样，是带有神谕的图灵机。

The proposed research revolves around two general questions: 1) Complete classification of problems according to which frequency algorithms they are amenable; and 2) Complete understanding of the of the recursion-theoretic properties of frequency computable problems. Computing, as it is practiced today, is of an interactive nature. Rather than the model of twenty years ago, where the computer was presented with a program and ran until it obtained an answer, the programs of today pause frequently and ask for input before continuing. Thus the true model of computing, as it is practiced, is the Turing machine with an oracle.