Journal of Formalized Mathematics
Volume 11, 1999
University of Bialystok
Copyright (c) 1999 Association of Mizar Users

## A Small Computer Model with Push-Down Stack

Jing-Chao Chen
Shanghai Jiaotong University

### Summary.

The SCMFSA computer can prove the correctness of many algorithms. Unfortunately, it cannot prove the correctness of recursive algorithms. For this reason, this article improves the SCMFSA computer and presents a Small Computer Model with Push-Down Stack (called SCMPDS for short). In addition to conventional arithmetic and "goto" instructions, we increase two new instructions such as "return" and "save instruction-counter" in order to be able to design recursive programs.

This work was done while the author visited Shinshu University March--April 1999.

#### MML Identifier: SCMPDS_1

The terminology and notation used in this paper have been introduced in the following articles [13] [12] [6] [20] [21] [4] [5] [11] [14] [16] [2] [17] [1] [3] [15] [19] [7] [8] [9] [10] [18]

#### Contents (PDF format)

1. Preliminaries
2. The Construction of SCM with Push-Down Stack

#### Acknowledgments

We wish to thank Prof. Y. Nakamura for many helpful suggestions.

#### Bibliography

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

Received June 15, 1999