Quasi-Delay-Insensitive Circuits are Turing-Complete

Manohar, Rajit and Martin, Alain J. (1995) Quasi-Delay-Insensitive Circuits are Turing-Complete. Technical Report. California Institute of Technology. [CaltechCSTR:1995.cs-tr-95-11]

Full text available as:

	Postscript - Requires a viewer, such as GhostView
	Other (Adobe PDF (180KB))

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.

EPrint Type:	Monograph (Technical Report)
Subjects:	All Records
ID Code:	240
Deposited By:	Caltech Library System
Deposited On:	14 May 2001
Record Number:	CaltechCSTR:1995.cs-tr-95-11
Official 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.

Archive Staff Only: edit this record