Mathematical Sciences: Frequency Approach to Approximating Algorithms

点击翻译按钮获取中文摘要

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.