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

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.