Back to Search
Start Over
THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA.
- Source :
- International Journal of Foundations of Computer Science; Dec2010, Vol. 21 Issue 6, p941-962, 22p, 1 Diagram
- Publication Year :
- 2010
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 21
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 55513184
- Full Text :
- https://doi.org/10.1142/S0129054110007659