The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata

摘要

We discuss the power and limitations of various "advice," when it is given particularly to weak computational models of one-tape two-way linear-time Turing machines and one-way finite (state) automata. Of various advice types, we consider deterministically-chosen advice, which is selected depending only on input size, and randomly-chosen advice, which is chosen according to certain probability distributions. We show that machines can be significantly enhanced in computational power when advice is provided; on the contrary, there are clear limitations on such a power.