Im folgenden wird eine algebraische Theorie interpretierter algorithmischer Graphen in Anlehnung an die algebraische Logik entwicke1t.l) Die Arbeit gliedert sich in drei Abschnitte. Im ersten Abschnitt fuhren wir die kanonischen Funktionen ein. Der zweite Abschnitt ist dem Studium des Begriffs der Maschinenform gewidmet. Das Ziel des dritten Abschnitts ist eine Charakterisierung der kanonischen h k t i o n e n durch Maschinenformen. Wir vereinbaren nun die folgenden Bezeichnungsweisen. a, B, y , . . . (evtl. mit Unterscheidungszeichen) seien im folgenden stets Ordinalzahlen, die wir uns so erklart denken, daI3 jede von ihnen die Menge aller kleineren ist. ,,o" bezeichne die kleinste unendliche Ordinalzahl. Es sei A eine nichtleere Menge. Ferner sei x E A". Schliealich seien 5, to, . . . , [,, qo, . . . , qa endlich viele natiirliche Zahlen mit c0 < --a < ca. Wir fuhren dann das Element ~[ { ~/ q ~, ..., Ca/qa] E Am durch die Festsetzung ein, daB fur alle < (o die Beziehung x(qp), falls 5 = [a fur ein gewisses 0 2 ,fI 5 a I 4% falls 5 E w \ KO, . -. , Ll ~[ t o l q o , * * * 9 C a / r a l (t) := gelten soll. Fur X 5 A" x A" sei Vb X der Vorbereich und Nb X der Nuchbereich von X .
1. Kanonische Funktionen2)
I n diesem Abschnitt fuhren wir den Begriff der kanonischen Funktion ein. Wir fassen dann die wichtigsten Tatsachen zusammen, auf denen das Rechnen mit kanonischen Funktionen beruht. Die folgende Begriffsbildung ist der Ausgangspunkt unserer Uberlegungen. 1) Die vorliegende Untersuchung, die an eine friihere Arbeit des Verfassers anschlieSt (vgl' SCRWARTZ [12]), behandelt eine Verallgemeinerung der Rekursionstheorie auf den Fall, daI3 beliebige Relationalsysteme in Betracht gezogen werden. Zur algebraischen und modelltheoretischen Rekursionstheorie sei grundsatzlich auf die Darstellungen von BARWISE [l], BLIKLE [2], DE BAKKER-DE ROEVER [3], EILENBERQ [4], EILENBERQ-ELOOT [5], ENQELER [6], [7], Mos-CHOVAKIS [lo], SALWICKI [ll], SCOTT [13], SRORDEV [15] und THIELE [17] sowie auf die dort angegebene weitere Literatur verwiesen. 2, Vgl. die grundlegende Abhandlung von TARSKI [IS] iiber die algebraische Darstellung der klassischen Pradikatenlogik der ersten Stufe mit Identitit. Siehe auch die von H E N K I N -M O ~-TARSKI [8] vorgelegte umfassende Darlegung der Theorie der Zylinderalgebren.