Oracle Pointer Machine

Multiplying two n-bit integers using the Schönhage-Strassen algorithm requires a Turing machine to perform O(n log(n) log(log(n))) operations. In 1980, Schönhage demonstrated that a Storage Modification Machine (SMM) could significantly reduce the number of operations required to multiply two integers of n bits to O(n). Moreover, it was established that the SMM could simulate the Turing machine in real-time. In the domain of computational processes incorporating Oracle machines, Turing machines encounter a bottleneck in computation due to the time demands associated with formulating queries to an Oracle and interpreting its results. Prolonged queries and responses inherently require extended processing time by the Turing machine. This study introduces the concept of Oracle pointer machines, focusing on Oracle storage modification machines that reduce computational time for Oracle machines and overcome existing bottlenecks. The study expands on the efficiency of SMMs and the novel construction of Oracle SMMs by applying them to recursive function theory, specifically focusing on the complexity of computing real functions. The complexity analysis of computing real functions within a bounded domain using Oracle SMMs builds upon the work of Ko and Friedman published in 1982. Their paper established an upper bound for computing real functions with a modulus of continuity m(n) using an Oracle Turing Machine, which was O(n) + O(m(n + 1)), where n denotes the precision parameter. This thesis explores the use of Oracle SMMs in this context, leading to an improvement in the bound to O(n)+O(⌈log m(n)⌉) when Oracle SMMs are utilized instead.

Committee: Dr. Jack Lutz (major professor), Dr. James Lathrop, and Dr. Ruoyu Wu