Journal of Formalized Mathematics
Volume 4, 1992
University of Bialystok
Copyright (c) 1992 Association of Mizar Users

## On a Mathematical Model of Programs

Yatsuka Nakamura
Shinshu University, Nagano
Andrzej Trybulec
Warsaw University, Bialystok

### Summary.

We continue the work on mathematical modeling of hardware and software started in . The main objective of this paper is the definition of a program. We start with the concept of partial product, i.e. the set of all partial functions $f$ from $I$ to $\bigcup_{i\in I} A_i$, fulfilling the condition $f.i \in A_i$ for $i \in dom f$. The computation and the result of a computation are defined in usual way. A finite partial state is called autonomic if the result of a computation starting with it does not depend on the remaining memory and an AMI is called programmable if it has a non empty autonomic partial finite state. We prove the consistency of the following set of properties of an AMI: data-oriented, halting, steady-programmed, realistic and programmable. For this purpose we define a trivial AMI. It has only the instruction counter and one instruction location. The only instruction of it is the halt instruction. A preprogram is a finite partial state that halts. We conclude with the definition of a program of a partial function $F$ mapping the set of the finite partial states into itself. It is a finite partial state $s$ such that for every finite partial state $s' \in dom F$ the result of any computation starting with $s+s'$ includes $F.s'$.

#### MML Identifier: AMI_2

The terminology and notation used in this paper have been introduced in the following articles                    

Contents (PDF format)

#### Bibliography

 Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.
 Grzegorz Bancerek. The ordinal numbers. Journal of Formalized Mathematics, 1, 1989.
 Grzegorz Bancerek. K\"onig's theorem. Journal of Formalized Mathematics, 2, 1990.
 Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.
 Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.
 Czeslaw Bylinski. Functions from a set to a set. Journal of Formalized Mathematics, 1, 1989.
 Czeslaw Bylinski. Some basic properties of sets. Journal of Formalized Mathematics, 1, 1989.
 Czeslaw Bylinski. A classical first order language. Journal of Formalized Mathematics, 2, 1990.
 Czeslaw Bylinski. The modification of a function by a function and the iteration of the composition of a function. Journal of Formalized Mathematics, 2, 1990.
 Czeslaw Bylinski. Subcategories and products of categories. Journal of Formalized Mathematics, 2, 1990.
 Yatsuka Nakamura and Andrzej Trybulec. A mathematical model of CPU. Journal of Formalized Mathematics, 4, 1992.
 Dariusz Surowik. Cyclic groups and some of their properties --- part I. Journal of Formalized Mathematics, 3, 1991.
 Andrzej Trybulec. Domains and their Cartesian products. Journal of Formalized Mathematics, 1, 1989.
 Andrzej Trybulec. Enumerated sets. Journal of Formalized Mathematics, 1, 1989.
 Andrzej Trybulec. Tarski Grothendieck set theory. Journal of Formalized Mathematics, Axiomatics, 1989.
 Andrzej Trybulec. Function domains and Fr\aenkel operator. Journal of Formalized Mathematics, 2, 1990.
 Andrzej Trybulec. Subsets of real numbers. Journal of Formalized Mathematics, Addenda, 2003.
 Michal J. Trybulec. Integers. Journal of Formalized Mathematics, 2, 1990.
 Wojciech A. Trybulec. Pigeon hole principle. Journal of Formalized Mathematics, 2, 1990.
 Zinaida Trybulec. Properties of subsets. Journal of Formalized Mathematics, 1, 1989.
 Edmund Woronowicz. Relations and their basic properties. Journal of Formalized Mathematics, 1, 1989.

Received December 29, 1992

[ Download a postscript version, MML identifier index, Mizar home page]