TITLE

Non-degenerate 2-State Reversible Logic Elements with Three or More Symbols Are All Universal

AUTHOR(S)
MORITA, KENICHI; OGIRO, TSUYOSHI; ALHAZOV, ARTIOM; TANIZAWA, TSUYOSHI
PUB. DATE
January 2012
SOURCE
Journal of Multiple-Valued Logic & Soft Computing;2012, p37
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
A reversible logic element is a primitive from which reversible computing systems can be constructed. A rotary element is a typical one with 1-bit memory (hence it has 2 states) and with 4 input/output symbols. It is known that we can construct any reversible Turing machine by using only rotary elements very simply. In this sense it is a universal reversible logic element. There are alsomany other reversible elements with 1-bitmemory. So far, it has been shown that all the 14 kinds of non-degenerate 2-state 3- symbol reversible elements can simulate a rotary element, and hence they are universal. In this paper, we generalize this result by showing that every non-degenerate 2-state k-symbol reversible logic element can simulate a rotary element if k > 2.
ACCESSION #
69753516

 

Related Articles

  • P Systems with Global Rules. Paun, Andrei // Theory of Computing Systems;2002, Vol. 35 Issue 5, p471 

    We contribute to the vivid area of membrane computing (P systems) by considering the case when the same evolution rules are valid in all regions of a system. Such a P system is called with global rules. We consider the case of string-objects, with the evolution rules based on splicing and by...

  • Non-degenerate 2-State Reversible Logic Elements with Three or More Symbols Are All Universal. MORITA, KENICHI; OGIRO, TSUYOSHI; ALHAZOV, ARTIOM; TANIZAWA, TSUYOSHI // Journal of Multiple-Valued Logic & Soft Computing;2012, Vol. 18 Issue 1, p37 

    A reversible logic element is a primitive from which reversible computing systems can be constructed. A rotary element is a typical one with 1-bit memory (hence it has 2 states) and with 4 input/output symbols. It is known that we can construct any reversible Turing machine by using only rotary...

  • halting problem Mathematics.  // Dictionary of Theories;2002, p243 

    A definition of the term "Halting problem" in mathematics is presented. It refers to the Turing machine, which consists typically of an infinitely long tape which is divided up into cells, in each of which may possibly be written one of a finite number of possible symbols. The halting problem is...

  • Polynomial Time Introreducibility. Cintioli, Patrizio; Silvestri, Riccardo // Theory of Computing Systems;Jan2003, Vol. 36 Issue 1, p1 

    Introduces the polynomial time version of the notion of introreducibility studied in Recursion Theory. More tractable notion of uniform introreducibility where uniform means that there is a single Turing machine that witnesses the introreducibility; Separation that results between...

  • Introduction to What is Computation. Denning, Peter J.; Wegner, Peter // Computer Journal;Jul2012, Vol. 55 Issue 7, p803 

    An introduction is presented in which the editor discusses various reports within the issue on topics including definition of computation, applicability of the Turing machine model and biological computation.

  • On a singularly perturbed first-order partial differential equation in the case of intersecting roots of the degenerate equation. Butuzov, V. F.; Derkunova, E. A. // Differential Equations;Feb2009, Vol. 45 Issue 2, p186 

    For a singularly perturbed first-order partial differential equation, we prove a theorem on the passage to the limit for the case in which the roots of the degenerate equation intersect and the root intersection line meets the initial segment on which the initial condition is posed.

  • A Brief Critique of Pure Hypercomputation. Cotogno, Paolo // Minds & Machines;Aug2009, Vol. 19 Issue 3, p391 

    Hypercomputation—the hypothesis that Turing-incomputable objects can be computed through infinitary means—is ineffective, as the unsolvability of the halting problem for Turing machines depends just on the absence of a definite value for some paradoxical construction; nature and...

  • Revision Sequences and Computers with an Infinite Amount of Time. Löwe, Benedikt // Journal of Logic & Computation;Feb2001, Vol. 11 Issue 1, p25 

    The author establishes a connection between Revision Theory of Truth and Infinite Time Turing Machines as developed by Hamkins and Kidder. The ideas from this paper have incited Welch to solve the limit rule problem of revision theory.

  • Paraconsistent Machines and their Relation to Quantum Computing. AGUDELO, JUAN C.; CARNIELLI, WALTER // Journal of Logic & Computation;Apr2010, Vol. 20 Issue 2, p573 

    We describe a method to axiomatize computations in deterministic Turing machines (TMs). When applied to computations in non-deterministic TMs, this method may produce contradictory (and therefore trivial) theories, considering classical logic as the underlying logic. By substituting in such...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics