Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950620 | Information and Computation | 2017 | 16 Pages |
Abstract
(c) ASPACE(s(n))=CO-ASPACE(s(n)), i.e., the alternating space is closed under complement, independently of whether s(n) is above logâ¡n and of whether the original machine can get into an infinite loop. This solves a long-standing open problem. Quite surprisingly, this complementary simulation does not eliminate infinite loops-the new machine itself goes to infinite loops along some computation paths.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Viliam Geffert,