Published November 17, 1995
| Submitted
Technical Report
Open
Quasi-Delay-Insensitive Circuits are Turing-Complete
- Creators
- Manohar, Rajit
- Martin, Alain J.
Chicago
An error occurred while generating the citation.
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 noninterference, 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.
Additional Information
© 1995 California Institute of Technology. November 17, 1995. The research described in this report was sponsored by the Advanced Research Projects Agency and monitored by the Office of Army Research.Attached Files
Submitted - 95-11.pdf
Submitted - 95-11.ps
Files
95-11.pdf
Additional details
- Eprint ID
- 26884
- Resolver ID
- CaltechCSTR:1995.cs-tr-95-11
- Advanced Research Projects Agency (ARPA)
- Army Research Office (ARO)
- Created
-
2001-05-14Created from EPrint's datestamp field
- Updated
-
2019-10-03Created from EPrint's last_modified field
- Caltech groups
- Computer Science Technical Reports
- Series Name
- Computer Science Technical Reports