Back to Search
Start Over
Three-dimensional alternating Turing machines with only universal states
- Source :
- Information Sciences. 95:155-190
- Publication Year :
- 1996
- Publisher :
- Elsevier BV, 1996.
-
Abstract
- We investigate several properties of three-dimensional alternating Turing machines whose input tapes are restricted to cubic ones. We first investigate the relationship between the classes of sets accepted by space-bounded and finitely leaf-size bounded five-way three-dimensional alternating Turing machines and the classes of sets which are finite intersections of sets accepted by space-bounded five-way three-dimensional nondeterministic Turing machines. Then, we investigate the accepting powers of three-dimensional alternating Turing machines with only universal states.
- Subjects :
- Discrete mathematics
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Information Systems and Management
Super-recursive algorithm
Turing machine examples
NSPACE
Description number
Computer Science::Computational Complexity
Computer Science Applications
Theoretical Computer Science
law.invention
Turing machine
symbols.namesake
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Artificial Intelligence
Control and Systems Engineering
law
symbols
Universal Turing machine
Time hierarchy theorem
Alternating Turing machine
Computer Science::Formal Languages and Automata Theory
Software
Mathematics
Subjects
Details
- ISSN :
- 00200255
- Volume :
- 95
- Database :
- OpenAIRE
- Journal :
- Information Sciences
- Accession number :
- edsair.doi...........2e48e751c6981661f29be5812b8ab5d7
- Full Text :
- https://doi.org/10.1016/s0020-0255(96)00124-7