Reversal Research Technical Report (Classic Reprint) - Softcover

Excerpt from Reversal Research Technical Report

The number of reversals made by tape heads during a Turing machine computation has assumed new importance as a complexity measure in complexity theory. This is because reversal complexity is intimately connected with uniform circuit depth and parallel time. For example, Hong [7] showed that reversal in sequential machine models (including the standard Turing machines) corresponds to parallel time in parallel machine models. Also Pippenger [9] show that simultaneous time and reversal in Turing machines are polynomially related to simultaneous size and depth in uniform circuits. However, reversal complexity has some unexpected properties which, until recently, made researchers treat it as a curiosity rather than as a fundamental computational resource. Baker and Book [1] showed the surprising fact that every recursively enumerable set can be recognized by a nondeterministic Turing machine making at most two tape reversals. Moreover, unlike time complexity and space complexity which have nice properties such as 'linear speedup' and 'tape reduction', reversal complexity has defied attempts at finding similar theorems in the multitape Turing machine model.

About the Publisher

Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com

This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.