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

スポンサーリンク

概要

• 論文の詳細を見る

• We discuss the power and limitation of various "advice," when it is given particularly to weak computational models of one-tape linear-time Turing machines and one-way finite (state) automata. Of various advice types, we consider two types of advice: standard (deterministically-chosen) advice and randomly-chosen advice (according to certain probability distributions). Toward a better handling of languages with advice, we present new machine-independent characterizations of them. Consequently, we show that underlying machines can be significantly enhanced in computational power when randomized advice is provided, instead of (deterministic) advice. However, there are also clear limitations, in power, of one-tape linear-time computations even with randomized advice.

• 2009-09-07

著者

• YAMAKAMI Tomoyuki

  Department of Information Science, University of Fukui

• Yamakami Tomoyuki

  Department Of Information Science University Of Fukui

関連論文

• The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata : Preliminary Version

スポンサーリンク