Quasi-Delay-Insensitive Circuits are Turing-Complete

Abstract

Quasi-delay-insensitives (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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 17, 1995
Accession Number
ADA444284

Entities

People

  • Alain J. Martin
  • Rajit Manohar

Organizations

  • California Institute of Technology

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Automata
  • Availability
  • Classification
  • Computations
  • Confluence
  • Contracts
  • High Voltage
  • Information Operations
  • Instructions
  • Low Voltage
  • Machines
  • Monitoring
  • Security
  • Voltage

Fields of Study

  • Mathematics

Readers

  • Computational Linguistics
  • Mathematical Modeling and Probability Theory.