A System for the Formal Definition of Digital Systems

Abstract

The structure and meaning of each operating system, and the programming languages it interprets are normally defined only in the context of a specific computer. This makes the recognition of computer independent structures more difficult, and inhibits the development of both general design principles and computer independent language and operating system structures. A formal system for the definition of computer independent structures is required. A formal system for representing general digital systems, based on extensions to Post string manipulation systems, is developed and defined. Very general forms of digital systems, interacting in real time can be represented. The formal system allows definition of equivalent systems at many levels of abstraction without biasing design decisions by a particular way of doing things. Examples of the use of this formal system for defining and comparing circuit elements, automata, and programming language semantics are presented.