On reversible Turing machines and their function universality

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

On reversible Turing machines and their function universality. / Axelsen, Holger Bock; Glück, Robert.

In: Acta Informatica, Vol. 53, No. 5, 2016, p. 509-543.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Axelsen, HB & Glück, R 2016, 'On reversible Turing machines and their function universality', Acta Informatica, vol. 53, no. 5, pp. 509-543. https://doi.org/10.1007/s00236-015-0253-y

APA

Axelsen, H. B., & Glück, R. (2016). On reversible Turing machines and their function universality. Acta Informatica, 53(5), 509-543. https://doi.org/10.1007/s00236-015-0253-y

Vancouver

Axelsen HB, Glück R. On reversible Turing machines and their function universality. Acta Informatica. 2016;53(5):509-543. https://doi.org/10.1007/s00236-015-0253-y

Author

Axelsen, Holger Bock ; Glück, Robert. / On reversible Turing machines and their function universality. In: Acta Informatica. 2016 ; Vol. 53, No. 5. pp. 509-543.

Bibtex

@article{54f911d52ac44aa2a81ddc93a89c0ebe,
title = "On reversible Turing machines and their function universality",
abstract = "We provide a treatment of the reversible Turing machines (RTMs) under a strict function semantics. Unlike many existing reversible computation models, we distinguish strictly between computing the function backslashlambda x.f(x) $ x . f ( x ) and computing the function backslashlambda x. (x, f(x)) $ x . ( x , f ( x ) ) , or other injective embeddings of f. We reinterpret and adapt a number of important foundational reversible computing results under this semantics. Unifying the results in a single model shows that, as expected (and previously claimed), the RTMs are robust and can compute exactly all injective computable functions. Because injectivity entails that the RTMs are not strictly Turing-complete w.r.t. functions, we use an appropriate alternative universality definition, and show how to derive universal RTMs (URTMs) from existing irreversible universal machines. We then proceed to construct a URTM from the ground up. This resulting machine is the first URTM which does not depend on a reversible simulation of an existing universal machine. The new construction has the advantage that the interpretive overhead of the URTM is limited to a (program dependent) constant factor. Another novelty is that the URTM can function as an inverse interpreter at no asymptotic cost.",
author = "Axelsen, {Holger Bock} and Robert Gl{\"u}ck",
year = "2016",
doi = "10.1007/s00236-015-0253-y",
language = "English",
volume = "53",
pages = "509--543",
journal = "Acta Informatica",
issn = "0001-5903",
publisher = "Springer",
number = "5",

}

RIS

TY - JOUR

T1 - On reversible Turing machines and their function universality

AU - Axelsen, Holger Bock

AU - Glück, Robert

PY - 2016

Y1 - 2016

N2 - We provide a treatment of the reversible Turing machines (RTMs) under a strict function semantics. Unlike many existing reversible computation models, we distinguish strictly between computing the function backslashlambda x.f(x) $ x . f ( x ) and computing the function backslashlambda x. (x, f(x)) $ x . ( x , f ( x ) ) , or other injective embeddings of f. We reinterpret and adapt a number of important foundational reversible computing results under this semantics. Unifying the results in a single model shows that, as expected (and previously claimed), the RTMs are robust and can compute exactly all injective computable functions. Because injectivity entails that the RTMs are not strictly Turing-complete w.r.t. functions, we use an appropriate alternative universality definition, and show how to derive universal RTMs (URTMs) from existing irreversible universal machines. We then proceed to construct a URTM from the ground up. This resulting machine is the first URTM which does not depend on a reversible simulation of an existing universal machine. The new construction has the advantage that the interpretive overhead of the URTM is limited to a (program dependent) constant factor. Another novelty is that the URTM can function as an inverse interpreter at no asymptotic cost.

AB - We provide a treatment of the reversible Turing machines (RTMs) under a strict function semantics. Unlike many existing reversible computation models, we distinguish strictly between computing the function backslashlambda x.f(x) $ x . f ( x ) and computing the function backslashlambda x. (x, f(x)) $ x . ( x , f ( x ) ) , or other injective embeddings of f. We reinterpret and adapt a number of important foundational reversible computing results under this semantics. Unifying the results in a single model shows that, as expected (and previously claimed), the RTMs are robust and can compute exactly all injective computable functions. Because injectivity entails that the RTMs are not strictly Turing-complete w.r.t. functions, we use an appropriate alternative universality definition, and show how to derive universal RTMs (URTMs) from existing irreversible universal machines. We then proceed to construct a URTM from the ground up. This resulting machine is the first URTM which does not depend on a reversible simulation of an existing universal machine. The new construction has the advantage that the interpretive overhead of the URTM is limited to a (program dependent) constant factor. Another novelty is that the URTM can function as an inverse interpreter at no asymptotic cost.

U2 - 10.1007/s00236-015-0253-y

DO - 10.1007/s00236-015-0253-y

M3 - Journal article

VL - 53

SP - 509

EP - 543

JO - Acta Informatica

JF - Acta Informatica

SN - 0001-5903

IS - 5

ER -

ID: 154363816