Questions tagged [turing-machines]
The Turing machine is a fundamental model of computation, especially in theoretical work.
1 questions from the last 7 days
2
votes
1
answer
70
views
Alternating Polynomial Space with Linear Number of Alternations
Consider alternating TMs with polynomial space and at a linear number of alternations. Is the halting problem for this class EXPTIME-complete, or does the linear alternation bound place it somewhere ...
- 1,514