Assistance in showing computational equivalence between software and hardware computing systems

Question

I'm in the middle of a discussion regarding the equivalence of software and hardware computing systems, and I would like some comment. Any arguments and/or documentation (supporting or dissenting) would be appreciated.

My position is that the implementation of a computational processing system can be separated from the act of logical computation, i.e. the agent performing logical processing (i.e., computation) can be distinctly separated from the process. My line of reasoning is more observational at the moment. For example,

• A PID controller may be implementing in pure (analog or digital) hardware or software.
• It is now routine to compile a C program into VHDL, then write the resulting "hardware" configuration into an FPGA.
• Computational systems have been constructed from fluidics and other mechanical systems.
• Computations systems have been constructed from molecular biology (i.e., DNA computing.)

From these observations, one might conclude that hardware computational systems, from simple collections of basic gates to FPGAs, are functionally equivalent to software programs.

The question is not entirely academic: the US FDA places dramatically different validation and verification (V&V) requirements on a medical device depending upon its use of hardware or software for logical operations. Software systems are subject to a number of standards and regulations, and the resulting testing procedure and documentation burden is heavy. On the other hand, simple hardware-only implementations, such as a PID controller, are subject to much less federal regulation.

As a result, a bias is introduced into the design process. A system designer is inherently pushed toward a hardware solution - simply due to the regulatory burden. The assertion that "computational hardware and software do the fundamental same things" is rendered heretical. It implies that hardware solutions are challenged with the issues of software development, and that hardware solutions should be subject to the same V&V processes applied to software. (Note that the US FDA is slowly coming around to this viewpoint - some of their more recent guidelines sound like early software guidelines.)

Can someone suggest a theoretical strategy for establishing this equivalence or a logical argument for divorcing the process of computation from the agent of computation?

Answer 1

These issues are clearly and accessibly covered in Sanjeev Arora and Boaz Barak's Computational Complexity: A Modern Approach, specifically in the chapters "The computational model and why it doesn't matter", "NP and NP completeness", and "Boolean circuits" (respectively chs. 1,2,6).

Very generously, an on-line draft of this book has been provided by the authors ... this has been a big help to me in my own researches!

From the viewpoint of complexity theory, the various theorems and proof technologies in Arora and Barak's exposition provide little grounds for "divorcing the process of computation from the agent of computation" (in the phrasing of the question).

From a regulatory perspective, however, it is well to keep in mind the legal maxim:

"Justice is the tolerable accommodation of the conflicting interests of society, and I don't believe there is any royal road to attain such accommodation concretely."

-- Judge Learned Hand

In real-world medical practice, and in many other regulatory contexts such as aircraft safety, commonly it is legally and practically necessary to distinguish between hardware and software, even though all parties recognize that the mathematical foundations for this distinction are highly imperfect.