Uber den Plankalkul

Over the Plankalkül*

Of K. Zuse, bath Hersfeld

Electron. Rechenanl. 1 (1959) 2 Manuscript entrance: 18.3.1959

• ZIA 0084. ZuP 040/004. Are missing to version 1, illustrations. Examined by R. Rojas, G. Wagner, L. sharp

That plan calculation developed in the year 1945 with the goal of creating a uniform Formelsprache for all computational problem definitions.

The used data or information units are composed on the basis of logistic criteria strictly of elementary units. As large a support at formalisms of logistics as possible is aimed at thereby.

Special symbols like the resulting in character and the indication of conditioned planning hurry etc. are stated and described. Different sample applications are mentioned and picked out from the area of the formulation of tasks of the game of chess a special example and discussed in detail.

The „plan calculation “(program calculus) originated in 1945 with the aim ton provide A uniformly LANGUAGE OF formulae adapted ton all child OF calculating problem.

The DATA or information unit used acres assembled from elementary units according tons strictly logistic view POINTs with the intention ton of refer tons the logistic formalisms as far as possible.

Special signs OF formulae as for instance the „results in “- sign and the sign for conditioned sub routines and so on, have been introduced and wants discussed. Several of examples OF application acres mentioned. A special example is selected out OF the field OF the formulation OF of problem of OF chess and discussed in detail.

Introduction

The author was led by theoretical investigations and practical work with program controlled Rechengeräten approximately in the years 1937 to 1945 to the realization that the term is expandable „counting the “substantially beyond number counting. From the perspective at that time it appeared meaningfully to build different types from program controlled Rechengeräten to e.g. predominantly numeric, predominantly logistic and such, which should predominantly serve the program manufacturing. We know today that such an organization is not necessarily appropriate. Modern electronic devices are able to master all such tasks. So the equipment Z22 can e.g. implement both programs of purely numeric kind with different variations of the arithmetic unit operations and logistic departments in the broadest sense and finally transfer the task of the program manufacturing, which runs today under the name „compilers “or „Superprogramm “or such a thing. Working with such devices requires „calculating machine-fair “formulation of the most different problems. The formalisms at that time the available were not sufficient for this. The author considered it necessary to create first of all a Formelsprache which is suitable, such connections of most general kind into all details accurately to express. The later development went something other way. One built first different devices with special Formelsprachen (program code).

With the time then similar tendencies of the formulation of a general Formelsprache showed up as it e.g. today in form „ALGOL “are suggested from practice.

On the other hand that developed for plan calculation at a time as a theoretical work on the paper, when still few experiences were present. That resulted in generally accepted and accurate solutions, with which in principle each problem is formulatable, however was the basis this first attempt still another certain ponderousness, which makes practical working more difficult with the calculation.

A goal of this essay is it not to publicise the plan calculation in the form created at that time to give but a discussion contribution for the refinement and addition today Formelsprachen already used. Certain indications, like e.g. the resulting in character, could become generally accepted already to a large extent.

The representation method of the plan calculation

That plan calculation proceeds from the following definition of counting:

„Counting is called, from given Angaben1 according to a regulation new data forms “[1].

The simplest indication is the Yes-No value. All other information units can be developed by Yes-No values in more or less complicated form. Likewise all arithmetic operations are detachable in elementary operations between elementary data.

Accordingly that contains plan calculation strict formulations first of the kinds of data and their structures.

It is differentiated:

1. The data structure

That is the kind of the structure of the data concerned from elementary data. The data structures are built up by strictly developed structural formulas from the simplest data, e.g.: S0 Yes-No value S1 . n = n × S0 n-digit consequence of Yes-No values S1 . 4 Tetrad s general indication of indication of arbitrary structure 2s Few of values m × 2s Pair list

In this way e.g. arbitrary technical structures, like networks, can be represented Stabwerke, constructions etc..

Example: Stabwerk

4 _________

? ? ?? 5

? ? ?? 1 _________ 2 _________ 3 Pair list 1 - 2 2 - 3 1 - 4 2 - 4 2 - 5 4 - 5 3 - 5

2. Restrictions of data

The marking of the structures is strictly not always sufficient, since in certain cases for a certain kind of data all structures are not defined (e.g. during the representation of the decimal digits by tetrads: from 16 possibilities only 10 is defined). There is then restriction formulas necessarily.

3. Type of data

Data of same structure can have different meanings (for instance x and Y-coordinates). For this the term of the type of data is introduced.

4. Kind of data

The different characteristics for an instruction (structure, restriction, type) can be summarized under one „characters of kind of data “.

The character of kind of data can more or less state depending upon situation as the structure character. Thus numbers in calculating machines can be e.g. represented by different structures (purely binarily, by tetrads, sliding comma, different sign representation etc.).

This does not interest however in the context of an algebraic formula. One can introduce therefore a general character of kind of data of „number “at all.

Then several structures can be assigned to this indication. Turned around the same structures can be assigned different data instructions and thus also kinds of data, e.g. regarding their meaning (physical dimensions etc.).

In the context of a formula the data are marked by indices in different lines.

Beside the main line, which essentially contains the formula in the traditional form, a second line (V) for the variable index, third for the component index (K) and fourth for the structure index (s) is introduced. The latter needs, strict-taken, always to be filled out serves however substantially for the easement of the understanding a formula. The lines are marked by setting the assigned letters (V forward, K, S).

Examples:

V K S V 3 m × 2 × 1 . n The variable V 3 is a pair list of m pairs of the structure 2 . 1 . n and is as a whole into the calculation in to go.

V K S V 3 i 2 × 1 . n By the pair list V 3 is to be taken i.Paar (structure 2 . 1 . n). (i can be thereby a current index.)

V K S V 3 i . 0 1 . 0 By i.Paar the pair list V 3 the front member (first element of the pair) is to be taken (structure 1 . n).

V K S V 3 i . 0 . 7 0 By the front member of the i.Paares of the pair list V 3 the Yes-No value No. 7 is to be taken (structure S0 = Yes-No value).

With the example of the Stabwerkes means for i = 4: V 3 the entire pair list of the Stabwerkes V 3 4 the marking of the staff 2 - 4 (4. The few given list) V 3 i . 0 the 1. Junction of the staff 2 - 4, thus junction 2 V 3 i . 0 . 7 the 7. Yes-No value from the indication, which marks the junction 2

Turned around to the process of the component formation data can be summarized:

V K S (

V 5 s ,

V 6 s ) ==>

V 7 2s 2 instructions V 5 and V 6 of the general structure s are combined into a pair of the structures 2.

The structure formalism gives only information over the component-moderate structure of the information units. It can be extended, as mentions already above, by restriction formulas and summary of different structures to kinds of information of same meaning.

The computing plans receive a strict marking likewise as whole by indices, which possibly disintegrate into several components; so P3.7 is e.g. the program 7 of the group of programs or the area 3.

Further the kinds of information arising within a computing plan are differentiated with respect to their relation to the computing plan:

  1. Input values (variable) V with index,
  2. Intermediate values Z with index,
  3. Result values R with index,
  4. Constant C with index. 

All arising information can be from most diverse structure. The initially and result values belong to „the boundary values “, which form the connection of the computing plan concerned with other parts of the entire calculation specification.

The edge excerpt

Number and structure of these boundary values are shown in one „edge excerpt “, which in all other respects does not state anything over contents of the computing plan.

V S R (

V 0 m.s ,

V 0 n.s ) ==> (

R 0 (m + n)s ,

R 1 1.n ,

R 2 0 )

This edge excerpt means:

2 variable V 0 and V 1 of the structure one list each (m × and/or s n ×) senters calculation. From these 3 result values are formed:

  1. a new list R0, structure (m + n) × s (e.g. the mixture of the two given lists according to a certain regulation),
  2. a dual number g 1 (e.g. sum of all individual values),
  3. a statement R2, which marks e.g. any characteristic of the given list or the total list („the list does not contain repeating members “). 

Result values of a computing plan, which in another plan-hurry to be re-used are, can be marked with the help of the edge excerpt clearly. If the edge excerpt mentioned above is e.g. assigned to the computing plan P3.7, then the expression 4 has the following meaning:

V S R3.7 1 1.n (

Z 9 m.s ,

Z 11 n.s ) ==>

Z 12 1.n i.e.:

„Turn on the intermediate values (lists) Z9 and Z11 straight of the treated upper plan the calculation specification P3.7 on. The result g 1 of this plan results in the intermediate value Z12, with which can be further operated. “

Each computing plan locked in itself is terminated by a disconnect signal FIN.

The introduction of disconnect signals of different degree (Fin2) means a shifting back to higher expiration operational sequence of the total plan; however the use of connectors is generally clearer.

The resulting in character

Special attention earns the use of the resulting in character. Computing plans are formed by individual explicit computing plan equations. In these left an expression, in which the input values or intermediate values already defined are contained, stands and on the right of that intermediate value and/or result value which can be determined again from the resulting in character. The resulting in character can be equivalent in special cases to the equals sign of mathematics or the equivalence character of the statement calculation, however the following rules apply:

  1. The resulting in character always suggests that right the value standing of it is to be calculated. It is thus never even an arithmetic operation. Equals signs in the context of a plan equation mean the arithmetic operation „comparisons “with the result of a logistic statement (Yes-No value).
  2. If the same indications arise on the right of and on the left of the resulting in character, then are assigned this not to same values.

     Example: Z + 1 ==> Z.
  3. If the same indication in several plan equations arises on the right of the resulting in character, then the latter determination of the value always applies. 

Conditioned planning hurry by the symbol -->. are marked. For the distinction of the indication --> of the implication in the statement calculation the condition arrow is supplemented by one point. The indication set between the beginning for the condition which can be fulfilled and in case of applying the condition the one which can be calculated plan-hurry.

Left of the causing character thus a Yes-No value and/or a Boolean expression must stand, on the right of a calculation specification.

Example: V 3 =

V 5 -->. (

V 6 +

V 8 ==>

V 9 )

.

The use of the resulting in character and the condition character was in the meantime in-patriated to a large extent. However the rules of application are not always strictly kept so, how it prescribes plan calculation for that. With the help of the condition character the representation of cyclic programs is easily possible, whereby in the meantime the generally introduced rules with the counting of indices etc. in the plan calculation can be formulated easy.

Logistic terms in the plan calculation

That plan calculation follows in formal regard as to a large extent as possible terms, which proved in logistics as useful:

„Everything “, „it gives “, „that which “, „those which “, „the next “, „number of “with the symbols (x)(x (- V0 --> R(x)) (Ex)(x (- V0 /\ R(x)) ´x(x (- V0 /\ R(x)) ^x(x (- V0 /\ R(x)) ^^x(x (- V0 /\ R(x)) mx(x (- V0 /\ R(x)) N (x)(x (- V0 /\ R(x)) Herein the expression x V (- 0 means that the current variable is to belong to x by the list of the V 0 marked quantity of members and that by R (x) a certain characteristic R, which would be to be marked in detail case more near is demanded.

The application of the operator ´x causes that there is exactly one member with the characteristic R (x) in the quantity of V 0.

The operator ^x requires a variation in the plan calculation ^^x, according to whether from the given quantity an excerpt is to be made, which the elements with the characteristic R (x) ever only once contains, or in the same number of repetitions as in the given quantity of V 0.

The operator mx has large advantages with the systematic investigation itself possibly of a list on members of a certain characteristic and processing the same, changing constantly to their extent. Against the rule however the rule applies for logistics (Hilbert): Look for the next member of the characteristic R. gives it none such, then go to the next plan-hurry over.

Furthermore with advantage different terms of the relational calculus can be used: e.g. „field of a relation “, „Vorbereich “, „Nachbereich “.

Prepared programs of the plan calculation

However the areas are still briefly mentioned, for which programs in the plan calculation were prepared at that time:

  1. General one concerning computing plan counting on structures of general kind, like consequences of Yes-No values, lists, pair lists, relations etc.
  2. Computing plans of the Zahlenrechnung, list of strictly detailed programs for different arithmetic operations with and without sliding comma.
  3. Operations with algebraic expressions. By this the treatment about formalisms and working on, transforming etc. are understood about formula expressions.
  4. Problems of the chess theory. The treatment of this problem proved as particularly suitable, in order to test the developed calculation regarding its versatility. The complete program of play control was developed. 

An example from the chess theory

As example with the chess theory dealt briefly. First the structure of the arising kinds of data is interesting. S0 Yes-No value S1 . n n-digit consequence of Yes-No values A1 S1 . 3 = coordinate A2 2 × A1 = point (e.g.: L00, 00L corresponds to point e2 in usual representation) A3 (S1.4) B3 = indication of occupying (e.g.: 00L0, white king) A4 (a2, A3) = indication of point occupying (e.g.: L00, 00L; 00L0 „point e2 with white king occupies “) A5 64 × A3 = field occupation: C5 start position (Enumerating the occupation of the 64 points in firm order) A6 64 × A4 = field occupation with indication of point, C6 start position A7 12 × S1 . 4 = number list of stones; C7 start position (It indicates how much stones of each sort on the field are, e.g. for evaluation calculations importantly). A9 (A5, S0, S1 . 4, a2) = game situation; C9 initial situation (Field occupation [A5]; Indication whether white or black at the course [S0]; Data concerning castling possibilities [4 Yes-No values] indication of the points with the possibilities of striking „EN passant “). A10 (A6, S0, S1 . 4, a2) = game situation with indication of point; C10 start position A11 (a2, a2, S0) = indication of course (for two point data, set of… after… a Yes-No value „one strikes “).

Further constants: C 0.1 Priority table of the stones C 0.2 Stone enumerating A3 is limited on 13 possibilities (12 stone places and 0 for vacant).

The structure of the programs is developed as follows:

  1. Geometry of the playing field;
     Organization into zones, statements about situation of one point etc., statements about situation of two points to each other (e.g. Springer relation).
  2. Programs with consideration of the occupation of the points with stones due to field occupation (A4).
  3. General statements about field occupation, e.g. „occupation is possible “(valuation formulas); Statements about course possibilities for individual stones with consideration of the uncovering of chess etc.
  4. Chess matt and Patt conditions.
  5. Introduction of the game situation (A5); Addition of field occupation by data over
        1. knows or black at the course,
        2. indicated over castlings,
        3. To strike data concerning the possibilities „EN passant “. 

     List of the conditions for the possibility of the castlings etc.
  6. Introduction of the indication of course and the play process; Education of the new situation from the old and indication of course.
  7. Complete play control; Input values: List of the courses of a play process, result: „Play corresponds to the rules. “ 

The structure of the programs for the game of chess was here broken off at that time. Actually here the actually interesting chess problems (regulations for the determination of favorable courses) begin. However it concerned to the author not a special „chess theory “, but the structure of a formalism, which was up to to all arising situations.

From the abundance of the programs of the game of chess a typical example is brought, the program for: „The white king can make a course, without coming thereby into chess. “

P 148 | | R( V ) ==> R148 V | 0 0 (1) A | 5 0 | |_ _ | |´x (x (- V ) /\ (x = L0) ==> Z V | 0 0 (2) K | |_ 1 _| A |4 5 3 4 | |_ _| |(Ex) (x (- V ) /\ R17( Z ,x ) /\ (x = 0) \/ x V | 0 0 K | 0 0 1 1.3 (3) A | 4 4 5 2 2 3 0 | --- |_ _| | /\ Ey (y (- V ) /\ y /\ R128( v ,y,x ) V | 0 0 K | |_ |_ 1.3 0 0 _| _| (4) A | 4 5 0 5 2 2 The subroutines here used are: | | R17( V ,V ) V | 0 1 die Punkte V0 und V1 sind benachbart.“ A | 2 2 | | R128( V ,V ,V ) Bei der gegebenen Feldbesetzung V0 ist V | 0 1 2 der Zug von Punkt V1 nach Punkt V2 er- A | 5 2 2 laubt.“ | The program R128 is relatively to be complicated, there examined must, which stone stands on point V 1, furthermore whether the point V 2 stands to V1 in for such a a geometrical relation that the stone standing on V 1 can set there, and finally must be examined whether between them lying points are present and whether these are free.

Explanation of the formula P148 in words:

  1. is the edge excerpt, which means that over a field occupation (A5) a statement is to be made.
  2. That indication of point occupying (x), which is contained of the play occupation (V 0) in the list, whose component is No. 1 = L0 (indications of king in the numbering of the stone types), results in the intermediate value Z0.
  3. It gives in the list to play occupation (V 0) one point (x) to Z0 (point, on which the king stands) neighbouring is and which is occupied with a black stone vacantly (= 0) or (x1.3) (that means Yes-No value No. 3 of the indication of occupying x1; this characterizes black stones).
  4. There is no further point, which is occupied with a black stone, which to point x can be set. 

Literature

[1] K. Zuse, „beginnings of a general theory of counting “. (1943). Unpublished.

[2] K. Zuse, „plan calculation “, theory of applied logistics. (1945). Unpublished.

[3] K. Zuse, „over the general plan calculation as means for the formulation of schematic-combination-native tasks “. Archives of the Math. 1 (1948/49), number 6, P. 441 - 449.

[4] K. Zuse, „the mathematical conditions for the development of logistic-combination-native calculating machines “. Magazine f. angew. Mathematics and mechanics (ZAMM). 29 (1949), number 1/2, P. 36 - 37.