Manohar, Rajit and Martin, Alain J. (1995) Quasi-Delay-Insensitive Circuits are Turing-Complete. Computer Science Technical Reports, California Institute of Technology , Pasadena, CA. (Unpublished) https://resolver.caltech.edu/CaltechCSTR:1995.cs-tr-95-11
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_postscript.png)
|
Postscript
- Submitted Version
See Usage Policy. 352kB | |
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Submitted Version
See Usage Policy. 180kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechCSTR:1995.cs-tr-95-11
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.
| Item Type: | Report or Paper (Technical Report) | ||||||
|---|---|---|---|---|---|---|---|
| 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. | ||||||
| Group: | Computer Science Technical Reports | ||||||
| Funders: |
| ||||||
| Series Name: | Computer Science Technical Reports | ||||||
| DOI: | 10.7907/Z9H70CV1 | ||||||
| Record Number: | CaltechCSTR:1995.cs-tr-95-11 | ||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechCSTR:1995.cs-tr-95-11 | ||||||
| Usage Policy: | You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format. | ||||||
| ID Code: | 26884 | ||||||
| Collection: | CaltechCSTR | ||||||
| Deposited By: | Imported from CaltechCSTR | ||||||
| Deposited On: | 14 May 2001 | ||||||
| Last Modified: | 03 Oct 2019 03:18 |
Repository Staff Only: item control page
