Quasi-delay-insensitive circuits are Turing-complete
The work
| Authors | Rajit Manohar; Alain J. Martin |
|---|---|
| Editors | |
| Type | techreport |
| Year | 1995 |
| Citekey | manohar1995quasidelayinsensitive |
Where it appeared
| Publisher | California Institute of Technology |
|---|
Identifiers
| DOI | 10.7907/z9h70cv1 |
|---|---|
| OpenAlex | W6940169822 |
| report_number | Caltech-CS-TR-95-11 |
Related
| Distinct from | bouzafour2018modelchecking |
|---|---|
| Distinct from | bozga2002verification |
| Distinct from | ebergen1989translating |
| Distinct from | karri2026softerror |
| Distinct from | marino1981general |
| Distinct from | martin1985delayinsensitive |
| Distinct from | martin1990limitations |
| Distinct from | martin1993tomorrows |
| Distinct from | sayle1996automated |
| Distinct from | snepscheut1983trace |
| Distinct from | taylor1998micropipeline |
| Distinct from | yan2010formal |
From OpenAlex, which stores abstracts as an index of words and their positions: what is shown is rebuilt from that, and reads fluently whether or not it is what the author wrote.
Abstract
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.
A copy is held
pdf, 175.8 kB. Not published — it may be under copyright. The facts and links here are.
How it got here
| How it got here | agent via openalex |
|---|---|
| Added | 2026-09-16 11:34 UTC |
| Approved by | a person 2026-10-02 09:58 UTC |
Cite it as
@techreport{manohar1995quasidelayinsensitive,
title = {Quasi-delay-insensitive circuits are Turing-complete},
author = {Rajit Manohar and Alain J. Martin},
year = {1995},
publisher = {California Institute of Technology},
doi = {10.7907/z9h70cv1},
}
This record lives at https://refs.drheap.org/manohar1995quasidelayinsensitive/ and will keep doing so.