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 [11]. 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 [15] [14] [7] [20] [2] [17] [3] [21] [5] [6] [12] [13] [18] [1] [8] [16] [9] [10] [4] [19]

Contents (PDF format)

Bibliography

[1] Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.
[2] Grzegorz Bancerek. The ordinal numbers. Journal of Formalized Mathematics, 1, 1989.
[3] Grzegorz Bancerek. K\"onig's theorem. Journal of Formalized Mathematics, 2, 1990.
[4] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.
[5] Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.
[6] Czeslaw Bylinski. Functions from a set to a set. Journal of Formalized Mathematics, 1, 1989.
[7] Czeslaw Bylinski. Some basic properties of sets. Journal of Formalized Mathematics, 1, 1989.
[8] Czeslaw Bylinski. A classical first order language. Journal of Formalized Mathematics, 2, 1990.
[9] 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.
[10] Czeslaw Bylinski. Subcategories and products of categories. Journal of Formalized Mathematics, 2, 1990.
[11] Yatsuka Nakamura and Andrzej Trybulec. A mathematical model of CPU. Journal of Formalized Mathematics, 4, 1992.
[12] Dariusz Surowik. Cyclic groups and some of their properties --- part I. Journal of Formalized Mathematics, 3, 1991.
[13] Andrzej Trybulec. Domains and their Cartesian products. Journal of Formalized Mathematics, 1, 1989.
[14] Andrzej Trybulec. Enumerated sets. Journal of Formalized Mathematics, 1, 1989.
[15] Andrzej Trybulec. Tarski Grothendieck set theory. Journal of Formalized Mathematics, Axiomatics, 1989.
[16] Andrzej Trybulec. Function domains and Fr\aenkel operator. Journal of Formalized Mathematics, 2, 1990.
[17] Andrzej Trybulec. Subsets of real numbers. Journal of Formalized Mathematics, Addenda, 2003.
[18] Michal J. Trybulec. Integers. Journal of Formalized Mathematics, 2, 1990.
[19] Wojciech A. Trybulec. Pigeon hole principle. Journal of Formalized Mathematics, 2, 1990.
[20] Zinaida Trybulec. Properties of subsets. Journal of Formalized Mathematics, 1, 1989.
[21] Edmund Woronowicz. Relations and their basic properties. Journal of Formalized Mathematics, 1, 1989.