IJUC HomeIssue Contents

A Direct Proof of Turing Universality of Delay-Insensitive Circuits
Jia Lee and Qing-Sheng Zhu

Delay-insensitive (DI) circuits are a special type of asynchronous circuits whose correct operation is robust to arbitrary delays involved in modules or interconnection lines. In this paper, we present a useful scheme for realization of Turing machines based on simple DI modules which exhibit strictly serial input and output behavior, thereby providing a direct proof of the computational universality of DI-circuits.

Keywords: Turing machine, delay-insensitive circuit, universality

Full Text (IP)