Summary: "To what mathematical models do digital computer circuits belong? In particular: (i) (Feedback reliability.) Which cyclic circuits should be accepted? In other words, under which conditions is the propagation of signals along closed cycles of the circuit causally faithful? (ii) (Comparative power and completeness.) What are the appropriate primitives upon which circuits may be (or should be) assembled?
   "There are well-known answers to these questions for circuits operating in discrete time, and they point to the exclusive role of the unit-delay primitive. For example: (i) If every cycle in the circuit N passes through a delay, then N is feedback reliable. (ii) Every finite-memory operator F is implementable in a circuit over unit-delay and pointwise Boolean gates.
   "In what form, if any, can such phenomena and results be extended to circuits operating in continuous time? This is the main problem considered (and, hopefully, solved to some extent) in this paper.
   "In order to tackle the problems one needs more insight into specific properties of continuous time signals and operators that are not visible when time is viewed as being discrete.''

Summary: "Paradigms in which continuous time is involved in cooperation with, or instead of, discrete time now appear in different areas related to automata, logic and interaction. Unfortunately, they are accompanied by a plethora of definitions, terminology and notation which are not free from ad-hoc and ambiguous decisions. The overuse of definitions from scratch of intricate notions without a previous, explicit core of basic generic notions engenders further models and formalisms, and it is not clear where to stop. Hence (quoting J. Hartmanis), the challenge is `to isolate the right concepts, to formulate the right models, and to discard many others that do not capture the reality we want to understand…'.
   "We undertake this challenge with respect to some automata-theoretic concepts and issues that appear in the literature on continuous-time circuits and hybrid automata, by keeping to the following guidelines:

1.

Building on basic automata theory.

2.

Coherence with original or potential discrete-time paradigms, whose continuous-time analogues and/or mutants we would like to understand.

3.

Functions, notably input/output behavior of devices, should not be ignored in favor of sets (languages) accepted by them.

   "The paper outlines the approach which emerged in previous research [D. Pardo, A. Rabinovich and B. A. Trakhtenbrot, Fund. Inform. 62 (2004), no. 1, 123–137; MR2086896; A. Rabinovich and B. A. Trakhtenbrot, in Fundamentals of computation theory (Kraków, 1997), 411–422, Lecture Notes in Comput. Sci., 1279, Springer, Berlin, 1997; MR1611874; B. A. Trakhtenbrot, in Fundamentals of computation theory (Iaşi, 1999), 54–89, Lecture Notes in Comput. Sci., 1684, Springer, Berlin, 1999; MR1850220; in Automata, languages and programming, 4–23, Lecture Notes in Comput. Sci., 2076, Springer, Berlin, 2001; MR2065849; A. Rabinovich, Theoret. Comput. Sci. 300 (2003), no. 1-3, 331–363; MR1976185] and in teaching experience [B. A. Trakhtenbrot, lecture notes, Tel-Aviv Univ., Tel-Aviv, 1994; per bibl.; "Automata and hybrid systems'', lecture notes, Uppsala Univ., Uppsala, 1997; per bibl.]. As an illustration we offer a precise explanation of the evasive relationship between hybrid automata, constrained automata and control circuits.''

Summary: "There is a growing feeling in the community that the current literature on reactive and hybrid systems is plagued by a Babel of models, constructs and formalisms, and by an amazing discord of terminology and notation. Further models and formalisms are engendered, and it is not clear where to stop.
   "Hence, the urge toward a pithy conceptual/notational setting, supported by a consistent and comprehensive taxonomy for a wide range of formalisms and models.
   "The paper outlines an automata-based approach to this challenge, which emerged in previous research [D. Pardo, A. Rabinovich and B. A. Trakhtenbrot, "On synchronous circuits over continuous time'', tech. rep., Tel Aviv Univ., Tel Aviv, 1997; per bibl.; A. Rabinovich and B. A. Trakhtenbrot, in Fundamentals of computation theory (Kraków, 1997), 411–422, Lecture Notes in Comput. Sci., 1279, Springer, Berlin, 1997; see MR1611900 MR1611874 ] and in teaching experience [B. A. Trakhtenbrot, lecture notes on a course on verification of software and hardware systems, Tel Aviv. Univ., Tel Aviv, 1994; per bibl.; "Automata and hybrid systems'', lecture notes, Uppsala Univ., Uppsala, 1997; per bibl.]. We compare our definitional suggestions with similar background in the current literature, where the subject is sometimes complicated by a premature mixture of semantics, syntax and pragmatics.''

In connection with the centenary of the birth of S. A. Yanovskaya, the author relates some of his own experience as a mathematical logician interested in the work of Church and others during the Stalin period, and his interactions with Yanovskaya. In 1951 the author was accused of idealism for having a paper that seemed "Carnapian'' to certain critics, who are identified only by initials. Two letters from Yanovskaya to the author that year show that she defended the author, and very likely saved his career and his freedom.

Another version of this paper has been reviewed [Fund. Inform. 28 (1996), no. 1-2, 183–195; MR1432321].

Compositional proof systems allow the establishment of a specification of a system on the basis of specifications of its components without knowledge of their internal structure. Compositionality of a proof system is a purely syntactic notion, whereas soundness and completeness are defined as usual with respect to semantics. Modularity states that two subsystems with the same meaning are replaceable in every context without changing the meaning of the full system. The aim of the article is to clarify the relationship between these notions and to provide a guide on how to construct compositional proof systems.
   The abstract framework employed is a set of agents, which may be interpreted as programs or systems, and operators, which are used to compose agents. Moreover, we have a set of specifications and a satisfaction relation between agents and specifications. Operations on agents may be associated with conjugated operations on specifications, an example being the operator of parallel composition and the logical conjunction. After an abstract definition of compositionality, two major classes of compositional proof systems are introduced. A characterization of completeness is given for one of these classes, and a sufficient condition for completeness is given based on the operation of denesting, which converts a structured system into a flat one.
   Whereas the first part uses agents without assuming a concrete syntax, the second part employs Petri nets as a syntactical representation of agents, the operations on agents being refinement of places by nets. Moreover, a semantics is given interpreting agents as port processes (communication strings) and specifications as port relations (communication strings assigned to ports). Finally, the general results are applied to this specific model.

In order to verify properties of formal systems, inference rules are needed. Networks of processes are compositions of processes. Therefore, for the verification of networks, inference rules stating that if the components Pi of a network satisfy certain properties Si then the whole network satisfies a property S are especially of interest. Of course, the property S, also called a specification, depends on the properties Si and this dependence can be expressed by a connection relation C(S1,⋯,Sn,S). In order to avoid nontrivial cases the connection relation has to be compositionally complete; that is, roughly speaking, C must be sound, in the sense that it captures the meaning described above, and at the same time powerful enough that if the network satisfies S, then the components must satisfy suitable Si related to S by C.
   The paper deals with the problem: For which kind of networks do compositionally complete connection relations exist. In Section 1, a scenario of compositional completeness is discussed. Here, the considerations are abstract in the sense that nothing is said about what the processes and specifications are. This is done in Section 2, where processes are defined on the basis of action traces and state traces. Two kinds of processes are considered: communication processes where an action is a communication, i.e. a transmission of a message through a port, and snapshot processes where a state is represented by all streams of messages transmitted through the ports until the current time. Hiding and composition are the two basic operations discussed in this section. Section 2 investigates complete rules for these kinds of processes, where the specifications are, in principle, generalized communication processes, called communication archives and snapshot archives, respectively. If a communication process is specified, however, by a snapshot archive then the situation becomes more complicated. In Section 4, some results are presented for this case and remaining anomalies are explained in Section 5. Finally, an appendix is dedicated to some special networks.
   The paper contains new interesting results and gives a very good overview of related work. Therefore, it may be used even in order to start with one's own investigations in this topic.

The authors present string and multiset languages as description languages for concurrent systems. Then the connected multiset languages (multitrees) are presented as another possible model of semantical domains for concurrency. The port relations, connected relations, and processes over F-domains (= cpo's which satisfy two finiteness conditions) are defined. For all situations, the considered operations of synchronization, union, and hiding obey laws and relations like those for conjunction, disjunction, and the existential quantifier in logic.
   Processes over F-domains can cover various formalisms for distributed systems and asynchronous networks (processing streams with "holes''). "Actually, what remains to be done is to apply more or less routine domain theory.''
   For the entire collection see MR1150316.

The concept of behaviour structures, which integrate both causality and branching, is introduced and developed. It is shown that nets of behaviour structures can provide a unifying approach to various net models of concurrency. The paper provides an extension of ideas of A. Mazurkiewicz[in Advances in Petri nets 1984, 353–375, Lecture Notes in Comput. Sci., 188, Springer, Berlin, 1984; MR0807209].

Logical relations, as a conceptual and technical tool, entail interesting applications in the theory of programming, properties of typed programming languages which intuitively amount to representation independence. The paper illustrates the impact of logical relations, revising some previous results of both the author and others.
   Section 2 considers functional frames, models and language construction, using as tools arbitrary infinite Böhm trees (as the natural extension of finite λ-terms augmented with fixed point operators). Section 3 presents a survey on logical relations and their fundamental properties. Section 4 deals with the characterization of schema-topological functionals via logical relations. The formalization is in terms of rank 2 functionals that are invariant with respect to specific logical relations (partial isomorphisms), for complete partially ordered models. In Section 5, the observational equivalence of two models with respect to a given programming language exhibits a typical situation when the usual logical relations do not provide the expected characterization, and more powerful (Statman's class) S-relations are needed. Section 6 is devoted to the problem of invariance with respect to locations for Algol-like language semantics: some memory locations are not relevant for the meaning of a given programming construction. The formal definitions use specific logical relations in reasoning about this type of program. Each section deals with specific open questions. This is a paper in which the technical aspects of program semantics are wonderfully governed by fruitful ideas, and an open-ended discussion containing hints for further valuable research directions is included.

This monograph is one in a series of scholarly studies on facets of work in the Soviet Union not well known or understood by the professional community or academia in the West. As aptly summarized in the foreword by Meyer, Trakhtenbrot's account of mathematical, or theoretical, cybernetics in the Soviet Union tells several stories. The greater part consists of an intellectual history of Soviet automata theory, combinational complexity and computational complexity over three decades, from the early 1950s to the early 1980s, and presents an in-depth survey of important results in these fields. A second story is that of the academic and political disputes which continue to shape the course of Soviet research in these areas. Finally, there is a laconic suggestion of the scientific life of a prolific mathematician and scholar, the author himself, one of the seminal researchers in automata theory and logic, who eventually emigrated (to Israel) in 1980.
   It is the thesis of this monograph that, while in terms of sheer magnitude of research and pioneering efforts the work of Western computer scientists exceeds that of their Soviet colleagues, the West tends to underestimate both Soviet achievements in theoretical computer science and the USSR's scientific potential in this field. The author points out and documents that quite a number of ideas and results in theoretical computer science appeared in the Soviet Union parallel to, independently of, and sometimes prior to similar developments in the West.
   The main body of the monograph is divided into four chapters. In Chapter 1, "The Soviet mathematical establishment and its effects on theoretical computer science'', the author gets the reader acquainted with the organization of the centralized scientific establishment in the Soviet Union, reviews the leadership roles played by powerful personalities who in the period under review dominated the field of theoretical computer science in the USSR, especially V. M. Glushkov(until his death in 1982) and S. V. Yablonskiĭ, and surveys distinct schools, groups and research centers that have been active in theoretical cybernetics research or computer science. The author traces the development of theoretical cybernetics research in the USSR to three "patriarchs'', namely the outstanding mathematician and physicist A. N. Kolmogorov(1903–1987); the founder of the Leningrad school of mathematical logic, Andrei Andreevich Markov, Jr.(1903–1980), who is the son of (and is often confused with) Andreĭ Andreevich Markov, Sr.(1856–1922), the famous scholar of probability theory; and P. S. Novikov(born 1901), the renowned worker in mathematical logic and algorithm theory (the author was one of his students).
   Chapter 2, "Finite automata'', describes original research in this field, whose systematic beginnings in the USSR coincided more or less with the prompt translation into Russian of the collection Automata studies [edited by C. E. Shannon and J. McCarthy, Ann. of Math. Stud., 34, Princeton Univ. Press, Princeton, NJ, 1956; Russian translation, with additions by Shannon and McCarthy, Moscow, 1956; per bibl.]. The scope of this chapter is best described by listing the headings of its sections: Modelling simple behavioral forms aided by finite automata; Finite automata and logic of monadic predicates; Automaton identification; Finite automata and algebra; Growing automata.
   Chapter 3, "Combinational complexity'', is concerned mainly with research in theoretical computer science by the Yablonskiĭ-Lupanov school based at Moscow State University. The principal focus of research there has been the asymptotic laws governing synthesis of optimal control systems. The author states that investigations of the synthesis of combinational circuits which took place there produced results which were not matched by the West in many cases until many years later. Section headings of this chapter are: Yablonskiĭ's control systems; Classes of more easily realizable functions; Lower bounds; The construction of reliable nets of circuits; On the behavior of the Shannon function; Perebor and combinational complexity. Perebor means "brute force'', exhaustive search; more details on this last subject have been provided in a survey article by the author [Ann. Hist. Comput. 6 (1984), no. 4, 384–400; MR0763733].
   Chapter 4, "Algorithmic complexity'', describes research in complexity of computations and complexity of algorithms carried out mainly in the centers of Novosibirsk (with which the author was associated), Moscow and Leningrad. Pioneering work was done by G. S. Tseĭtinalready in the mid-1950s, when he was a brilliant young student of Markov in Leningrad, but he delayed publication until much later. Major contributions came from Kolmogorov's formulation of an algorithmic definition of the complexity of finite objects and the discovery of an optimal coding for finite objects in the framework of algorithms and recursion theory in 1965, and L. Levin'sdiscovery of the so-called NP-complete problems. These advances were independent of similar work performed in the West. Section headings of this chapter are: The contribution of Grigorĭ Tseĭtin; Computations with oracles; Kolmogorov and Markov complexity.
   In the final chapter, "Conclusions'', the author recapitulates the main theme of the monograph, namely, that in spite of the isolation imposed by language barriers and socio-political forces, Soviet scientists have made noteworthy contributions, though on a more modest scale, in a field that has clearly been dominated by the West with respect to both the scope and depth of its research firsts.
   Appendix A (compiled by Meyer) provides a table that compares research topics in theoretical computer science during the period 1950–1980 in the USA and USSR.
   Appendix B presents a schematic diagram of the fields included under the Soviet heading of cybernetics and its subdivisions (the term "cybernetics'' has a different, much broader meaning in Soviet than in Western usage and encompasses all of computer science).
   Appendix C contains a list that provides some biographical information on over one hundred scientists whose contributions to Soviet theoretical cybernetics are mentioned in the monograph.
   The bibliography at the end of the monograph contains 191 entries (of which 18 entries are publications of the author himself or his joint works).
   The author's selective account of the development of mathematical cybernetics in the Soviet Union relies much on his own recollections and is personally flavored. It makes fascinating reading. This monograph is highly recommended for anyone interested in the early development of theoretical cybernetics in the Soviet Union.

Author summary: "Concerns about computational problems requiring brute-force or exhaustive search methods have gained particular attention in recent years because of the widespread research on the `P=NP?' question. The Russian word for `brute-force search' is `perebor'. It has been an active research area in the Soviet Union for several decades. Disputes about approaches to perebor had a certain influence on the development, and developers, of complexity theory in the Soviet Union. This paper is a personal account of some events, ideas, and academic controversies that surrounded this topic and to which the author was a witness and—to some extent—a participant. It covers a period that started in the 1950s and culminated with the discovery and investigation of nondeterministic polynomial (NP)-complete problems independently by S. Cookand R. Karpin the United States and L. Levinin the Soviet Union.''

The paper presents the author's own and original viewpoint on such basic problems of theoretical computer science as algorithmic logic, denotational semantics, and proving correctness of programs. It is an attempt to unify various approaches to the problem of semantics of programming languages. There are three sections. The first is devoted to operational semantics, the second concerns denotational semantics, and the third deals with partial correctness and the problem of halting. The paper is a valuable and unified contribution to the theory of semantics of programming languages.

Die vorliegende Arbeit befaßt sich mit der Zeitkomplexität stochastischer Algorithmen, genauer, von Algorithmen, welche eine binare gedächtnislose Quelle Q zur Verfügung haben und deren Ergebnis mit Hilfe eines Schwellwertes Δ bestimmt wird. Es wird unter anderem gezeigt, daß die Q definierenden Wahrscheinlich-keiten kompliziert sein müssen, wenn man eine Beschleunigung durch die Verwendung von Q erzielen will, und daß zur Auswertung der Ausgabe einer komplizierten Quelle Q ein gewisser Zeitaufwand erforderlich ist, der der Beschleunigung Grenzen setzt. Ferner wird der Einfluß der Veränderung von Δ auf die Komplexität studiert. Das russische Original dieser Arbeit erschien unter dem Titel "Bemerkungen über die Komplexität der Berechnungen auf stochastichen Maschinen'' [Theory of algorithms, and mathematical logic (Russian), pp. 159–176, Vyčisl. Centr Akad. Nauk SSSR, Moscow, 1974; MR0521172].

From the introduction: "In this paper we mainly rely on three references [D. Harel, A. Meyer and V. Pratt, Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977), pp. 261–268, Assoc. Comput. Mach., New York, 1977; MR0495101; Harel, A. Pnueli and J. Stavi, ibid., pp. 249–260; MR0495102; K. R. Apt and J. W. de Bakker, "Exercises in denotational semantics'', Preprint No. IW 57/76, Math. Centrum, Amsterdam, 1976]. An analysis of these papers makes it possible to present a complete axiomatization for a version of algorithmic logic that would represent to a large extent the saturation of the program constructions of Apt and de Bakker [op. cit.], as well as the diversity of properties of the programs formalized by Harel, Meyer and Pratt [op. cit.] and Harel, Pneuli and Stavi [op. cit].''

Earlier translations have appeared [Turkish translation, Türk Matematik Derneği, Istanbul, 1964; MR0228343; German translation, Deutsch. Verlag Wissensch., Berlin, 1977; MR0491083]. The latter review also gives a good description of the contents of the book.

In a famous paper that inspired the work of the author, M. O. Rabin discussed how incorrect computations could overcome the inherent difficulty of combinatorial problems. This issue is today and in the foreseeable future one of the most fascinating ones in the theory of algorithms, especially if we could establish a connection among semantic and complexity properties of algorithms; that is if, for example, we could build incorrect algorithms which perform correctly, or at least with high reliability, on "meaningful'' sets of inputs. This paper is devoted to some aspects of this problem. Among three basic classes of incorrect but approximate algorithms (probabilistic algorithms, "performance guarantee'' approximate algorithms, frequency algorithms) the author discusses the properties and computational power of the last class, that is, of those incorrect algorithms which on sufficiently large vectors of inputs provide the correct answer with sufficiently high frequency. Frequency computations are known to be capable of recognizing (with arbitary frequency p<1) a recursively enumerable nonrecursive set, but, as regards the most interesting question, that is, to what extent frequency computations can reduce the complexity of the recognition of a decidable set, very little is known, and the only result which is cited in the paper concerns the possibility of real time recognition of arbitrarily complex (input-output) sets by frequency algorithms.
   {For the entire collection see MR0451810.}

This book gives a very clear and detailed elementary introduction to the basic notions of the theory of algorithms. The first chapter introduces the concept of algorithms and of calculating machines from the intuitive point of view. It gives many interesting examples, such as algorithmic games, search algorithms, etc. This chapter together with the first parts of the second and third chapters reproduces essentially the author's earlier popular book [Wieso können Automaten rechnen?, Deutsch. Verlag Wissensch., Berlin, 1959; MR0127481]. The second chapter gives the notion of Turing machine, discusses the construction of complex Turing programs out of subprograms, defines recursive functions and shows the equivalence of recursive and Turing computable functions. It concludes with a discussion of variants of Turing machines (semi-infinite tape, many-dimensional tape) and of Church's thesis. The third chapter deals with the universal Turing machine, algorithmically unsolvable problems (halting problems, word problems for (semi-) Thue systems), complexity questions (in particular, J. Bārzdiņš' theorem on Turing machines recognizing symmetric inputs over 0, 1 is given as well as (Cejtin's weaker version of) Rabin's theorem that there are recursive functions with arbitrarily high time complexity) and von Neumann's one-dimensional cellular automata (equivalence of Turing computable and von Neumann computable functions). Throughout the book the examples and motivating discussions are particularly well suited for a beginner in the field of the theory of algorithms.

The four papers have been published in the "Populjarnye Lekcii po Matematike'' Series, Nos. 45, 26, 32 and 48, respectively: I. M. Jaglom [Extraordinary algebra (Russian), Izdat. "Nauka'', Moscow, 1969]; B. A. Trahtenbrot [Algorithms and machine solution of problems (Russian), Gostehizdat, Moscow, 1957; second edition, Fizmatgiz, Moscow, 1960; MR0120149; Turkish translation, Türk Matematik Derneǧi, Istanbul, 1964; MR0228343]; E. S. Ventcelʹ [Elements of game theory (Russian), Fizmatgiz, Moscow, 1959; reprint, 1961; MR0134793; Turkish translation, Türk Matematik Derneǧi, Istanbul, 1965; MR0229459]; A. S Solodovnikov, Systems of nonlinear inequalities (Russian), Izdat. "Nauka'', Moscow, 1969; MR0258457].
   Jaglom's booklet is an introduction, at a very elementary level to Boolean algebra and its applications in propositional calculus and circuit theory. Trahtenbrot's book has been reviewed [MR0120149]. Ventcel's booklet contains a discussion of two-person games, emphasizing solution methods and strategies, finishing with a discussion of the relationship between game theory and linear programming. Solodovnikov provides an introduction to the duality theorem in linear programming, emphasizing geometrical constructions used to solve systems of linear inequalities.

Classes of functions computable in polynomial time by various types of nondeterministic computers are defined, including stochastic computation and nondeterministic computation in which there is a unique halting computation. The basic open question is: Do any of these classes properly contain DPol, the set of functions computable deterministically in polynomial time? Polynomial time analogues of immunity and separation theorems are investigated for subclasses of the functions computable nondeterministically in polynomial time closed under polynomial time Turing reducibility; most questions are open.
   {For the entire collection see MR0381368.}

For a review of this item see Zbl 304 #02014.
   {For the entire collection see MR0387026.}

A set of quite reasonable axioms is given in order to formalize the notions of program schemas and classes of program schemas, and their interpretations. A class of schemas is then called universal [effectively universal] if any other class is translatable [effectively translatable] into it. Finally, it is shown that the class Am= of schemas consisting of flowcharts using arrays, markers and equality tests is effectively universal, while the class A= is just universal. This is a worthwhile paper.
   {For the entire collection see MR0411218.}

Author's summary: "In terms of computational complexity we define notions which seem to be adequate to the following situations, which usually are considered on an intuitive level: (I) The individual questions in a decidability problem (e.g., in determining whether the individual n is in G, where G is a set of integers) are mutually independent. (II) For a function f, defined by the formula f(x)=μy(F(x,y)=1), there is no algorithm for its computation simpler than that of successively examining all possible alternatives: F(x,1)=1? F(x,2)=1?⋯. Using the proposed notions it is proved that such situations really exist. The proofs are based on diagonal constructions.''
   {For the entire collection see MR0434692.}

Für gegebenes n∈N, n>0, sei Dn die Menge aller 0–1-Folgen der Länge n und es sei Dω die Menge aller 0–1-Folgen vom Typ ω. Für p, q∈Dn bezeichnet r(p,q) den Hamming-Abstand der Folgen p und q und es sei ρ∗(p,q)=ρ∗(p,q)=(r(p,q):n). Für p, q∈Dω sei ρ∗(p,q)=limsup(r(p(n),q(n)):n), ρ∗(p,q)=liminf(r(p(n),q(n)):n), wobei p(n) bzw. q(n) der Anfang von p bzw. q der Länge n ist. Es sei ferner Ω eine beliebige Menge von endlichen ober unendlichen wiederholungsfreien Folgen natürlicher Zahlen. Ein Operator T auf Ω ist eine Abbildung, die jeder Folge I∈Ω eine 0–1-Folge TI gleicher Länge wie I zuordnet. Speziell werde für p∈Dω mit pI die Folge (p(i1),p(i2),⋯) bezeichnet, wobei I=(i1,i2,⋯) und p(i) das i-te Glied der Folge p ist. Ein Operator heißt effektiv, wenn er z.B. durch eine Zweiband Turing-Maschine realisierbar ist. Für ε>0 sei K∗(Ω,ε) die Menge aller p∈Dω, für die ein effektiver Operator T auf Ω existiert, so daß ρ∗(pI,TI)<ε für alle I∈Ω, und k∗(Ω,ε) die Menge aller p∈Dω, für die es zu jedem I∈Ω einen effektiven Operator TI mit ρ∗(pI,TII)<ε gibt. Analog werden K∗(Ω,ε) und k∗(Ω,ε) definiert. Die vorliegende Arbeit gibt einen systematischen Überblick über die bisher bekannten Resultate über die Klassen K∗(Ω,ε),⋯ für spezielles Ω.
   {For the entire collection see MR0321684.}

The original has been reviewed [Izdat. "Nauka'', Moscow, 1970; MR0265078].

The author examines some properties of a variant of Turing reducibility. All sets, functions, and predicates are over the natural numbers. A function (set, predicate) f is recursive in a function (set, predicate) g without self-inquiry if there is an algorithm (machine) M that for all n computes f(n) making use only of various g(m), m≠n. A set A is autoreducible if the characteristic function of A is recursive in itself without self-inquiry. Autoreducibility is a recursive invariant, and it follows easily that all creative sets are autoreducible. On the other hand, sets that are random in the sense of A. N. Kolmogorov [Sankhyā Ser. A 25 (1963), 369–376; MR0178484] and D. W. Loveland [Trans. Amer. Math. Soc. 125 (1966), 497–510; MR0207562] are not autoreducible.
   By means of a finite-injury priority argument, the author shows that there are r.e. (recursively enumerable) non-simple, non-autoreducible sets. Contrariwise, he shows that there are non-autoreducible sets A that are simple, and such that there is no function f recursive in cA, the characteristic function of A, without self-inquiry, that picks out an infinite subset of the complement of A.
   The author next undertakes to compare, in a suitable precise sense, the complexity of computation of recursive predicates with their complexity of autoreduction. Given a machine M, SM(n) is the number of cells used by M when applied to n; similarly for SMP(n), where M uses the predicate (set) P as oracle. A capacity function h is a total function for which there is a machine M such that SM(n)=h(n). The author proves (Theorem 3): For each capacity function h there is a predicate P such that: (1) there is a machine M that computes P and (n)(SM(n)=h(n)); for any machine W that computes P using P as oracle without self-inquiry, then for some constant c, (n)(SWP(n)≥ch(n)). Thus, there are effective mass problems of arbitrary complexity h that do not have an autoreduction essentially more simple than their outright computation.
   The author in the last section of the paper proves the existence of examples of nontrivial autoreduction. In this context, he notes in proof that one of his theorems has been improved by Paterson.
   {For more complete bibliographic information about the collection in which this article appears, including the table of contents, see MR0327467.}

The author defines as "strategy of conjecture'' a machine M with oracle, such that, for every natural number n and oracle G, the machine, if started with n as argument, never asks the oracle whether n is in G, although it may ask that question for numbers m≠n. A set G is called autoreducible just when there is a strategy of conjecture which, when provided with an oracle for G, will calculate Γ(n) for every natural number n, where Γ is the characteristic function of G. The author introduces this concept as a natural way of making precise intuitive notions of dependence and independence of particular problems constituting a mass problem. He states some properties of the notion, discusses its relations with some similar concepts, and mentions some unsolved problems. For example: an autoreducible set cannot be a random sequence (collective) of von Mises, as formulated in a somewhat similar way by A. N. Kolmogorov [Sankhyā Ser. A 25 (1963), 369–376; MR0178484] and D. W. Loveland [Trans. Amer. Math. Soc. 125 (1966), 497–510; MR0207562]; there exists a non-autoreducible set which is not immune; etc.
   {This article has appeared in English translation [Soviet Math. Dokl. 11 (1970), 814–817].}

An automaton is a quintuple M=⟨Q,X,Y,ψ,ϕ⟩, where Q is a set of states, X, Y are input and output alphabets, ψ is a transition function, ψ:Q×X→Q, ϕ is an output function, ϕ:Q×X→Y. By a finite automaton we mean an automaton which has a finite set of states. Let q0∈Q be given. We can introduce the operator T(M,q0) mapping words over X into words over Y in the following manner. When x=x(1)⋯x(r), where x(n)∈X, then T(x)=y=y(1)⋯y(r), where y(n)∈Y, y(n)=ϕ(q(n),x(n)) and q(1)=q0, q(n)=ψ(q(n−1),x(n−1)). When one of the sets Q,X,Y consists of exactly one element, then we obtain a particular kind of automaton. For example, when Y consists of one element, we obtain an automaton without output M=⟨Q,X,ψ⟩. When M is an automaton without output, then the triple ⟨M,q0,Q′⟩, where q0 is an initial state and Q′ is a set of final states, defines a language in the same way as Rabin-Scott automata do (by accepting words belonging to the language).
   First, behavior of finite automata without output is described. Languages determined by finite automata without output and operations on them are introduced and discussed. Next, behaviour and various properties of finite automata with output are described. This is done by means of operators T which are connected with these automata. The author discusses problems of synthesis of finite automata. He constructs a metalanguage of regular expressions such that any expression from the meta-language defines a language, which is accepted by some automaton and we must find the automaton. The author constructs a metalanguage of logical formulas such that any formula from the metalanguage determines conditions which define an automaton. We must find the automaton (if it exists). When a "black box'' is given, i.e., we know the output word which we obtain from an input word, then as a matter of fact we known the operator T mentioned before. Then, by some particular assumptions, we must construct (and determine when such a construction exists) the automaton which corresponds to the operator T. We must do this mainly when the upper bound of the number of states is not known. In the book non-deterministic automata also are introduced and discussed. Furthermore, the book contains many examples.

It is known (the first proof was given by A. A. Fridman, see his paper in Dokl. Akad. Nauk SSSR 147 (1962), 805–808 [MR0168632]), that for any recursive enumerated set Π of the natural numbers there exists the finitely presented group G(Π) such that the problem of solvability "n∈Π?'' for the set Π is effectively reduced to the problem of identity "W=1 in G(Π)?'' for the group G(Π) and vice versa. The reduction of these algorithmic problems to each other can be carried out by the Turing machine with oracle and the author is interested in the space complexity function φ(n) of such a reduction (i.e., in the number of φ(n) cells, used by the machine for transforming the words of length n). To construct the group G(Π) the author uses the construction of W. W. Boone [Ann. of Math. (2) 83 (1966), 520–571; MR0201499]. For historical reasons the author calls this construction the Novikov-Boone construction. The main result of the paper is formulated as follows. Let Π be an arbitrary recursive enumerated set and G(Π) the group of Boone constructed for Π. Then the problems (n∈Π?) and (W=1 in G(Π)?) are reduced to each other without extension (i.e., with the space complexity function φ(n)=n). Simultaneously with the work of the author, the analogous result for the construction of G. Higman was obtained by M. K. Valiev [Algebra i Logika 8 (1969), 5–43].
   {This article has appeared in English translation [Algebra and Logic 8 (1969), 50–71].}

The original Russian edition has been reviewed [Fizmatgiz, Moscow, 1962; MR0147349; English translation, North-Holland, Amsterdam, 1965; MR0186454].

Estimates of the growth of signalizer functions for Turing computations are given with accuracy up to the order of this growth, because, at the expense of an increase in the number of internal states and external symbols, it is possible to decrease the capacity signalizer and the time signalizer to a constant once. To eliminate this effect the author proposes the assumption that the states of the Turing machine are coded with binary words in such a way that no code is the origin of any other code but the lengths of the codes are in general not the same. In processing word P, let the machine work t times and pass successively through the states q(1),q(2),⋯,q(t); then the time signalizer τM(P) denotes the total length of the codes of these t states. Furthermore, τM(n)⇌maxτM(P) with respect to all words of length n. The lexical function f(P) has a normed time complexity φ(n) if the following conditions are satisfied: (1) (lower estimate) given any machine M, a computer function f, and an arbitrary ε>0, then, for every sufficiently large n, τM(n)>(1−ε)φ(n); (2) (upper estimate) given any ε>0 one can construct a machine M and a computer f such that, for every sufficiently large n, τM(n)<(1−ε)φ(n). Using these concepts, the author revises the known results as follows: Theorem 1: The discernment of symmetry has a normed time complexity n2/4. Theorem 2: The transfer of unary notation to binary notation has normed time complexity nlogn. Theorem 3: For every function f∈Φ, the predicate Πf has normed time complexity nf(n). The article contains proofs of only the first two theorems.

Correction to the author's article in same Sem. 4 (1965), no. 5, 79–93 [MR0194280].

To define a measure of the complexity of a computation, the author introduces the notion of the signalization capacity function (s.c.f.) φ for the computation by a Turing machine M of a given predicate Γ [or function f] defined on the set N of natural numbers [or on the corresponding binary words]. Roughly, for each n∈N, φ(n) is taken to be the length of tape used by M in computing Γ [or f]. The author notes that if φ is an s.c.f. for Γ (by some computation) and if K is a positive integer, then φ~, defined by φ~(n)=max{|n|,]φ(n)/K[}, is also an s.c.f. for Γ (by some other computation). (Here |n| is the length of the binary word corresponding to n and ]x[ is the least integer not less than x.) He then defines φ to be an optimal s.c.f. for Γ if (1) φ is an s.c.f. for Γ, and (2) for every ψ which is an s.c.f. for Γ there exists a constant C such that Cψ(n)≥φ(n) for all n∈N.
   Let Γ+={n|Γ(n)=1} and Γ−={n|Γ(n)=0}. Denote by rk the ratio of the number of elements n∈Γ+ such that |n|=k to the number of elements n∈N such that |n|=k. If limrk exists (as k becomes infinite) and is equal to r, then Γ+ is said to have density r. If (1) holds, and if (2) holds with "for all n∈N'' replaced by "for all n∈Γ+'', then φ is called an optimal s.c.f. for Γ+.
   Some typical results are as follows: (I) For every s.c.f. φ there exists a predicate Γ such that φ is an optimal s.c.f. for Γ. (II) Let φ be an s.c.f. and let R be a finite-automatonic set of binary words of density 0. Then there exists an effective set of binary words Γ+ for which the following conditions hold: (a) Γ+ has density 1; (b) φ is an optimal s.c.f. for Γ+; (c) Γ−⫆R. The author sees a connection between the latter result and a phenomenon studied by S. V. Jablonskiĭ [Problemy Kibernet. 2 (1959), 75–121; MR0129088]. Jablonskiĭ, investigating the construction of minimal contact circuits, considered a model problem for which he stated the hypothesis that although this problem is with high probability solved by a simple procedure consisting of acts of random choice, there is no algorithm for its solution simpler than that of successively examining all possible alternatives.

This is a translation of a book originally published in Russian [Fizmatgiz, Moscow, 1962; MR0147349].

The first Russian edition appeared in 1957 [Gostehizdat, Moscow, 1957], the second, revised edition in 1960 [Fizmatgiz, Moscow, 1960; MR0120149; French translation, Dunod, Paris, 1963; MR0153560].

A clear review of some aspects of the theory of finite automata.

The author introduces the class of functions computable by a Turing machine with logarithmic delay. This class is shown to be in a sense next in order of simplicity to the class computable without delay by Turing machines, i.e., computable by finite automata. On the other hand, the class contains functions adequate for the T predicate in Kleene's normal form (the U function can be of an even simpler form).
   The author uses a one-way infinite tape, with the convention that when the head moves off the end of the tape it is returned in the next move in an internal state which is a function of the one it was in when it left (but he points out that the results are valid for more general conventions and in a sense also for two-way tapes). If Ω is a set of words and if for all words P in Ω the number of steps the machine, when started on P, takes before it stops is of order ≤nlogn, where n is the length of P, then the machine is said to "process Ω with logarithmic delay''. Similarly, for sublogarithmic delay (order <nlogn), bounded delay (order <n), bounded expansion, extension (maximum distance head travels to the right of order n,<n+const)), bounded behaviour (number of times head passes any given square < const). In the first section, relations between these are established. Theorem 1: If the machine M processes the set of words Ω with bounded behaviour [logarithmic delay], then it processes it with bounded extension [bounded expansion]. Theorem 2: If the machine M processes the set Ω of all words on the alphabet X with sublogarithmic delay, then it processes Ω with bounded behaviour. Corollary: If M processes the set Ω of all words on the alphabet X with sublogarithmic delay, then it processes it with bounded delay and with bounded extension.
   The next theorem is a generalisation of the result of Rabin and Scott [IBM J. Res. Develop. 3 (1959), 114–125; MR0103795] and the reviewer [ibid. 3 (1959), 198–200; MR0103796] that events realisable by a two-way automaton are also realisable by a one-way automaton. Theorem 3: If a function f(P) is computable by M with bounded behaviour, then by a suitable machine M~, it is computable with unit oscillation (i.e., no changes of direction). This is used in the next section, in the proof of Theorem 4: If M enumerates the set of words Ω with sublogarithmic delay, then it enumerates Ω with bounded delay and the set (event) Ω is representable by a finite automaton (i.e., is a regular set). Theorem 5: If M represents the event Ω with sublogarithmic delay, then it represents it with bounded delay and Ω is representable by a finite automaton. Here M is said to enumerate Ω if it computes a function f(P), defined on all words P, which enumerates Ω; it represents Ω if it computes its characteristic function. This shows that in order to represent more functions than finite automata can, it is necessary to use Turing machines with at least logarithmic delay. On the other hand, such machines are an adequate basis for recursion theory, for one has Theorem 6: For every r.e. set and every natural number m there is an enumerating function f for Ω which is computable with logarithmic delay and such that the length |f(P)| of f(P) is of order ≤log(m)|P|. (Ritchie, [Ph.D. Diss., Princeton Univ., Princeton, N.J., 1961] has previously shown that f could be taken to be computable using a tape of length of order exp(m)|P| for suitable m.) Theorem 7: In the Kleene normal form the function U may be taken to be one computable with bounded delay and the predicate T computable with logarithmic delay (but not with sublogarithmic delay). This result holds whether the arguments of T are supposed to be coded in series or parallel. (Using Smullyan's result that U, T can be taken to be rudimentary, Ritchie [op. cit.] and also Myhill [WADC Tech. Note No. 60–165, Report No. 60–22, Univ. Pennsylvania, Philadelphia, Pa., 1960] have shown that they can be computed with bounded expansion.)

Es bezeichne Q(m,n,k) die Klasse aller derjenigen Operatoren, die sich in einem endlichen Automaten (A,X,Y,δ,λ) realisieren lassen, wobei A={0,1}k, X={0,1}m, Y={0,1}n und der zulässige "Parameterbereich'' der Forderung n≤m+k unterworfen wird (d.h. all bei einem Automaten mit 2k inneren Zuständen und 2m Eingabesignalen maximal möglichen 2m+k Ausgabesignale durch Elemente aus Y kodiert sind). Für eine gegebene Basis E von Schaltelementen bezeichne LE(m,n,k) das Minimum der Gewichte der logischen Netze von Elementen aus E, die zur Realisierung sämtlicher Operatoren aus Q(m,n,k) erforderlich sind. (Zur Definition des Gewichts eines Netzes wird zunächst jedem Element E∈E eine positive Zahl ρE als Gewicht zugeordnet; das Gewicht eines Netzes ist dann die Summe der Gewichte der Elemente, die an seinem Aufbau beteiligt sind.) Weiterhin bezeichne H(m,n,k) den Quotienten lg2N/lg2lg2N, wobei N die Anzahl aller Operatoren aus Q(m,n,k) ist. Es ist bekannt [vgl. z.B., N. E. Kobrinskii und der Verfasser, Introduction to the theory of finite automata (Russian), Chapter VII, Fizmatgiz, Moscow, 1962; MR0147349], daß für gewisse Basen E eine Konstante ρ(E) existiert, die nur von der Basis E abhängt, so daß lim(LE/H)=ρ(E), wenn (m,n,k) im Parametergebiet auf irgendeinem Wege ins Unendliche strebt. In der vorliegenden Arbeit wird nun andererseits gezeight, daß es auch sehr einfache Basen E gibt, bei denen das asymptotische Verhalten von LE/H wesentlich vom Wege abhängt. Es wird dazu die Basis E={E1,E2} betrachtet, bei der E1 die Sheffersche Funktion y(t)=x¯¯¯1(t)∨x¯¯¯2(t) und E2 die Funktion y(t)=x1(t)&x2(t−1) realisiert. Bezeichnet ρ1 bzw. ρ2 das Gewicht von E1 bzw. E2, so gilt im Falle ρ1≤ρ2 für jeden Weg die asymptotische Formel L∼ρ1H, während es im Falle ρ2<ρ1 zu jedem ρ mit ρ2≤ρ≤ρ1 einen Weg gibt, längs dessen L∼ρH ist. Als Nebenresultat ergibt sich, daß auch allgemeiner keine rationale Funktion I(m,n,k) existiert, so daß längs jedes Weges L/H∼I(m,n,k) gilt. Es wird ferner die interessante asymptotische Formel bewiesen.

Die Arbeit beschäftigt sich mit solchen endlichen Automaten, die ein beliebiges Wort in ein Wort derselben Länge transformieren. Die Anzahl der Buchstaben des Eintrittsalphabetes sowie des Ausgangsalphabetes ist endlich aber nicht notwendig dieselbe. Die Tätigkeit dieses Automaten kann man ähnlich wie in dem zitierten Buche [N. E. Kobrinskiĭ und B. A. Trahtenbrot, Einführung in die Theorie der endlichen Automaten (Russian), Fizmatgiz, Moscow, 1962; MR0147349] mittels eines Baumes v beschreiben. Die minimale Anzahl der Zustände des endlichen Automaten, der diese Transformation realisiert, ist gleich dem Gewichte k(v) des Baumes v, d.h. sie ist gleich der Anzahl der Knotenpunkte der Basis (im Sinne des zitierten Buches) des Baumes v.
   In der Arbeit werden zwei Sätze bewiesen, die eine asymptotische Beschätzung der Anzahl k(v) für die Länge des Wortes grenzlos wachsende ermöglichen.

Let N stand for the set of natural numbers and let m,n∈N satisfy 0<m≤n. Let T be a function defined on Nn, T(x1,⋯,xn)=(y1,⋯,yn). A function f:N→N is said to compute T with frequency m/n if for every n-tuple (x1,⋯,xn) such that xi≠xj for i≠j at least m of the n equations f(x1)=y1,⋯,f(xn)=yn are true. A function f:N→N is called frequency computable if there exists a recursive function which is computed by f with some frequency. Theorems: (1) For an arbitrary function T, the set of functions f which compute T with frequency m/n>12 is at most countable. (2) There exists a recursive function T0 which is computed with frequency m/n=12 by uncountably many functions f. (3) Each function f which is computable with frequency m/n>12 is recursive. These results answer a question of Myhill and Rose presented by McNaughton [Advances in Computers, Vol. 2, pp. 379–421, Academic Press, New York, 1961; MR0136487]. Proofs depend in part on the introduction of a topology in the set of interpretations of a sequence of propositions, and the paper includes a constructive sharpening of the theorem of Löwenheim.