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

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

2010-07-18

arxiv.org/abs/1007.3021v1

International Journal of Foundations of Computer Science, Vol.21, pp.941-962, 2010

Computer Science

Formal Languages and Automata Theory

A4, 10 pt, 16 pages, 1 figure. This is a complete version of the extended abstract, published in the Proceedings of the 20th I

Scientific paper

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 deterministically-chosen advice (not necessarily algorithmically determined) and randomly-chosen advice (according to certain probability distributions). In particular, we show that certain weak machines can be significantly enhanced in computational power when randomized advice is provided in place of deterministic advice.

Affiliated with

Also associated with

No associations

Rating

The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-523261