ON SIMILARITY AND DUALITY OF COMPUTATION
Iawei Beijing · 1981
This paper gives a uniform definition of reversal and a uniform definition of computa-tional type (for example, nondeterministic and alternating types). It proves that all knownreasonable computational models of any fixed computational type are similar in the sensethat they can simulate each other in such a way that the reversal and space of the simulatorare bounded simultaneously by a polynomial of the reversal and a polynomial of the spaceused by the machine being simulated, thereby unifying all the computational models. This paper further shows that the reversal is dual to space in the sense that if there isa theorem about reversal and space then it is still true after exchanging the positions ofreversal and space in this theorem. In fact, this paper lists a series of metatheorems in dualform. These metatheorems include most known theorems in a certain field and some resultscompletely new.