CaltechAUTHORS
  A Caltech Library Service

Quasi-Delay-Insensitive Circuits are Turing-Complete

Manohar, Rajit and Martin, Alain J. (1995) Quasi-Delay-Insensitive Circuits are Turing-Complete. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1995.cs-tr-95-11

[img]
Preview
Postscript
See Usage Policy.

344Kb
[img]
Preview
Other (Adobe PDF (180KB))
See Usage Policy.

175Kb

Use this Persistent URL to link to this item: http://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)
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1995.cs-tr-95-11
Persistent URL:http://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:26 Dec 2012 14:08

Repository Staff Only: item control page