Loading...
Please wait, while we are loading the content...
Similar Documents
Quasi-delay-insensitive circuits are Turing-complete (1995)
| Content Provider | CiteSeerX |
|---|---|
| Author | Manohar, Rajit Martin, Alain J. |
| Description | : Quasi-delay-insensitive (QDI) circuits are those whose correct operation does not depend on the delays of operators or wires, except for certain wires that form isochronic forks. In this paper we show that quasi-delay-insensitivity, stability and non-interference, and strong confluence are equivalent properties of a computation. In particular, this shows that QDI computations are deterministic. We show that the class of Turing-computable functions have QDI implementations by constructing a QDI Turing machine. Keywords: Quasi-delay-insensitive circuits; Turing machines; Determinism; Confluence; Stability 1. Introduction There has been a renewal of interest in the design of asynchronous circuits, motivated by the potential benefits of designing circuits in an asynchronous fashion. Asynchronous circuits exhibit average case behavior and can therefore be optimized in a data-dependent fashion. Another benefit is that the portion of the circuit involved in the computation is the only par... |
| File Format | |
| Language | English |
| Publisher Date | 1995-01-01 |
| Publisher Institution | Second International Symposium on Advanced Research in Asynchronous Circuits and Systems |
| Access Restriction | Open |
| Subject Keyword | Isochronic Fork Asynchronous Fashion Qdi Computation Turing Machine Quasi-delay-insensitive Circuit Potential Benefit Certain Wire Strong Confluence Turing-computable Function Equivalent Property Asynchronous Circuit Qdi Turing Machine Correct Operation Data-dependent Fashion |
| Content Type | Text |
| Resource Type | Article |
