A simple and efficient universal reversible Turing machine
HB Axelsen, R Glück - … Conference on Language and Automata Theory …, 2011 - Springer
International Conference on Language and Automata Theory and Applications, 2011•Springer
We construct a universal reversible Turing machine (URTM) from first principles. We take a
strict approach to the semantics of reversible Turing machines (RTMs), under which they can
compute exactly all injective, computable functions, but not non-injective ones. The natural
notion of universality for RTMs is RTM-universality, where programs are considered part of
both input and output of a URTM. The machine described here is the first URTM which does
not depend on reversibilizing any existing universal machine. The interpretive overhead of …
strict approach to the semantics of reversible Turing machines (RTMs), under which they can
compute exactly all injective, computable functions, but not non-injective ones. The natural
notion of universality for RTMs is RTM-universality, where programs are considered part of
both input and output of a URTM. The machine described here is the first URTM which does
not depend on reversibilizing any existing universal machine. The interpretive overhead of …
Abstract
We construct a universal reversible Turing machine (URTM) from first principles. We take a strict approach to the semantics of reversible Turing machines (RTMs), under which they can compute exactly all injective, computable functions, but not non-injective ones. The natural notion of universality for RTMs is RTM-universality, where programs are considered part of both input and output of a URTM.
The machine described here is the first URTM which does not depend on reversibilizing any existing universal machine. The interpretive overhead of the URTM is limited to a (program dependent) constant factor slowdown, with no other complexity-wise cost wrt time and space. The URTM is also able to function as an inverse interpreter for RTMs at no asymptotic cost, simply by reversing the string representing the interpreted machine.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果