This study introduces the Stochastic-Oracle Turing Machine (SOTM) framework, which models AI-augmented computation as the interaction between a probabilistic Turing machine and an oracle that provides responses drawn from context-dependent distributions. The paper investigates the capabilities of SOTM under two oracle-response schemes:
- Cached-response oracle: Each distinct query receives one response, which is reused in later calls.
- Fresh-response oracle: Each call returns an independent response.
In both schemes, the SOTM first computes from its input and internal random source to generate the first query, then adaptively generates subsequent queries or produces a final output based on the query-response transcript (the record of issued queries and received responses).
Cached responses impose two transcript-based ceilings on achievable performance:
- Correct-identification ceiling: Determined by the total variation distance between the transcript distributions induced by the oracle's hidden states.
- Output quality ceiling: Equal to the expected score of the best output the SOTM can compute from the transcript.
Fresh responses can elevate these ceilings by allowing repeated calls to accumulate independent evidence toward correct or high-quality outputs. In the binary single-informative-query case, the error probability decreases exponentially with the number of calls to the same query at the Chernoff rate. For output quality, query-count bounds characterize threshold stopping when the score function is part of the SOTM, and majority-based amplification bounds characterize the binary candidate-output model when it is not. Together, the findings identify how response reuse, transcript information, and access to the score function determine what an SOTM can compute and at what token cost.
Blogger's Review: This paper delves into the application of stochastic oracles in AI-augmented computing, offering a clear understanding of performance limits and providing a significant theoretical foundation for future computational model design.