Founder

• Pioneer of mathematica logic research in Bulgaria
• Creator of united collective of researchers who developed what has became known as “Bulgarian school” in computability theory.
• Creative athmosphere, perfect conditions for scientific work.
• Valuable advises and recommendations to everyone.
• Aura of uncompromising and inspirational moral.

Master theses before 1980

Intuitionistic logic: Slavian Radev (1973), Yordan Zashev (1974) Stochastic computability: Martin Tabakov (1977) Combinatory spaces: Lyubomir Ivanov (1977), Veselin Petrov (1977), Elena Pazova (1978), Rusanka Loukanova (1978), Ognemir Ignatov (1979) Computability in algebraic structures: Angel Dichev (1978), Ivan Soskov (1979), Alexandra Soskova (1979), Solomon Passy (1979)

Pre-History

• 1936: born in Sofia
• After 1945 the Mathematical logic is neglected. Sometime before 1960 the attitude changes due to computer applications
• November 1959 (Skordev at age of 24): decision of the Central committee of the Bulgarian Communist Party: “We need to develop the mathematical logic”.
  • In the Academy: a Sector, initially with zero members.
  • In the University nothing: Skordev is in the Department of Mathematical Analysis, Vakarelov is in the Department of Geometry, Petio Petkov is in the Department of Applied Mathematics. Their research in mathematical logic is additional to their main duties.

First stay in Moscow

In 1961/1962 at age of 26: one year stay at the Department of Mathematical Logic of the Moscow State University. There Skordev is introduced to various advanced fields of the mathematical logic in general and computability theory in particular.

Computable and μ-recursive operators

Uspensky, 1961: at the seminar of algorithmic set theory raises the question of the existence of partial recursive operators that are not μ-recursive. Examples are found by Kuznetsov and Skordev.

Soon Skordev published a characterization of the inclusion μ⊆p.r.

• Д. Скордев. Изчислими и µ-рекурсивни оператори. Изв. на Мат. инст. на БАН, 7, 1963, 5-43.

This was the first non-trivial result in computability theory in Bulgaria.

Return in Sofia

In 1962 Skordev returned to Bulgaria (age 27).

He began giving lectures in mathematical logic. These were the first lectures of mathematical logic in Sofia University (possibly first also in Bulgaria).

For the first time computability theory is being thought in Bulgaria.

Axiomatization of the universal functions

Between 1962 and 1973 (age 27–38) he has mostly non-logical publications.

In most of his logical papers he investigates an axiomatization of his of the universal functions.

Recursively complete functions

Definition. (1963) A partial function f: ℕ² → ℕ is recursively complete iff it is arithmetic and there are constants a, b, c и d, such that for any n, m, k:

• f(a,n) = n + 1
• f(b,n+1) = n
• f(f(f(c,n),m),k) = m, if n = 0,
                          = k, if n ≠ 0.
• f(f(f(d,n),m),k) = f(f(n,k),f(m,k))

Recall that a function f is universal, if it is partially recursive and for any partially recursive function g there exists n, such that

• g(m) ≅ f(n,m)

Skordev proved that

• any universal function is recursively complete;
• any recursively complete function encodes all partially recursive functions;
• therefore, any partially recursive and recursively complete function is an universal function.

Simple universal functions

Many universal functions with simple definitions can be found. For example let p(n,m) = (n+m)(n+m+1) + n − m. Then the following function is universal (1973):

• f(p(m,0),k) = p(m,k)
• f(p(0,n+1),k) = n
• f(p(m+1,n+1),k) = f(f(n,k),f(m,k))

Non-recursive recursively complete functions

Each recursively complete function f encodes a set of partial functions. When f is a partially recursive function, then f is an universal function, so the set of the encoded functions is the set of all partially recursive functions.

A question arises: what sets of functions can be encoded by recursively compete functions which are not necessarily recursive.

The answer: A set M of arithmetic functions is the set of all functions, encoded by some recursively complete function f if and only if M is the set of all functions that are μ-recursive relatively some set of functions.

Subrecursive computability

In 1967 he has a brief interest in subrecursive computability.

He defined a class of functions which I will call elementary by Skordev. Each elementary by Skordev function is also elementary by Skolem. We don’t know whether the opposite is true or not.

Associate professor

In 1968 г. at age of 33 години Skordev became associate professor. His inaugural lecture is published in the Annual of Sofia University:

• Д. Скордев. Върху някои алгебрични аспекти на математичната логика. Год. на Соф. унив., Мат. фак., 62 (1967/1968), 1969, 111-122.

Second stay in Moscow

• 1968/1969 (age of 33): a second stay at the Department of Mathematical Logic of the Moscow State University.
• In 1970 (age 35): Sofia University and the Academy of Sciences formed United center of Mathematics and Mechanics. A Section of Topology and Mathematical Logic was created. Skordev become a member.
• In 1972 (age 37): A.A.Markov visited Bulgaria. He read lectures in recursive mathematical analysis. Markov became indignant that there was no separate Section of Mathematical Logic. A few days after he leaves Bulgaria, a separate Section of Mathematical logic is created. Skordev became its chief. Initially there were six members.

Algebraization of computability theory

In 1969 Moschovakis invented a generalization of the computable functions. Instead of partial functions working with natural numbers his abstraction used functions working in algebraic structure.

Multi-valued functions are needed for this generalization. Skordev became intrigued that in many cases in computability theory one can use multi-valued functions instead of partial single-valued functions. He carried a systematic research of phenomena related to the multi-valued functions.

In 1974 (age 36) Skordev read in Moscow several lectures about his own generalization of the computable function. This generalization was equivalent to the generalization of Moschovakis but it was simpler.

• D. Skordev. A generalization of the theory of recursive functions. Soviet Math. Doklady, 15, № 5, 1974, 1756-1760.

While working with this generalization Skordev noticed that the multi-valued functions satisfy many algebraic identities which are true not only for the multi-valued functions but also for several other types of computability (i.e. stochastic computability).

Compositional system

In autumn, the same year, Skordev defined the notion compositional system. In this definition he axiomatized the laws he noticed.

• Д. Скордев. О многозначных функциях нескольких переменных. Доклады БАН, 28, № 7, 1975, 885-888.

The definition turned out to be too complex. Very few results were proven. The examples satisfying this definition, however, were amazingly many and varied (13 examples are given in the paper).

Specialization in USA

In 1974/1975 (age 39) Skordev was sent for a specialization in the USA – in the Stanford University (2 months) and in the University of Los Angeles (1 month).

There he found the correct formulation of the combinatory spaces. The combinatory spaces were simpler, more powerful and more expressive than the the compositional system he had defined two an year before that.

• D. Skordev. Recursion theory on iterative combinatory spaces. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astr. Phys., 24, No. 1, 1976, 23-31.

Functions without variables

A well-known fact is that any function, definable by a λ-term, can be defined by an expression using only the operation function application and the two combinators S и K:

• Sxyz = xz(yz)
• Kxy = x

In essence, the translation of a λ-term into an expression, using only S и K, can be seen as elimination of the variables.

Usually we need to eliminate the variables when we want to algebraize a certain formal language.

language with variables	algebraization
predicate logic	cylindrical algebras
λ-calculus	combinatory logic with S and K

While the λ-calculus and the combinatory logic are languages for untyped functions of higher order, Skordev needed an algebraization of a language for first order functions only.

Language of the Combinatory Spaces

Skordev used I, L, R, T, F, composition, combination, branching, and iteration. With functions, they can be defined in the following way:

• composition: (fg)x = f(gx)
• combination: ⟨f, g⟩x = ⟨fx, gx⟩
• branching: (f→g,h)x = gx, if fx is true,
                                   = hx, otherwise
• iteration: [f,g]x = fⁿx, if g(fⁿx) is true and
             g(f^n − 1x), g(f^n − 2x), …, g(fx), gx are false
• (T→g,h) = g, (F→g,h) = h
• L⟨x, y⟩ = x, R⟨x, y⟩ = y
• Ix = x

The axioms

• ordered monoid
• ∀x(fx≥gx⟹f≥g)
• ⟨x, y⟩ ∈ 𝒞
• L⟨x, y⟩ = x; R⟨x, y⟩ = y
• ⟨f, g⟩x = ⟨fx, gx⟩
• ⟨I, gx⟩h = ⟨h, gx⟩
• ⟨x, I⟩h = ⟨x, h⟩

• T ≠ F
• T, F ∈ 𝒞
• (T→g,h) = g; (F→g,h) = h
• j(f→g,h) = (f→jg, jh)
• (f→g,h)x = (fx→gx,hx)
• (I→gx,hx)f = (f→gx,hx)
• branch is monotone

Completeness?

Definition. A combinator is computable in B, iff it can be generated from the elements of B ∪ {I, L, R, T, F} by means of composition, combination, branch and iteration.

• Prime computability in an algebraic structure can be characterized by computability in Combinatory spaces: Skordev 1976 in the original paper of the Combinatory spaces
• Search computability in an algebraic structure: Skordev 1979
• Friedman-Shepherdson type computability: Ivan Soskov 1987

Examples

• Partial natural functions: ℕ → ℕ
• Multi-valued natural functions: ℕ → 2^ℕ
• The same in an algebraic structure
• Infinite objects (infinite sequences – Baire and Cantor spaces, real numbers)
• Error messages in case of unsuccessful computation.
• Probabilistic models of computation
• Computation with measurement of the complexity of data processiong
• Computation with side effects

Theorems

First recursion theorem. Each element, recursively definable by composition, combination and branch is explicitely definable by composition, combination, branch and iteration.

Normal form. Each such element is explicitely definable by composition, combination and only one iteration.

Loop detection

7 papers on loop detection (1987–1993).

• An extremal problem concerning the detection of cyclic loops.
• On the detection of periodic loops in computational processes.
• On Van Gelder’s loop detection algorithm.
• On the average delay of the detection of cyclic loops.
• On the detection of some periodic loops during the execution of Prolog programs.
• An abstract approach to some loop detection problems.
• On the detection of some loops in recursive computations.

A variety of other topics

A paper where he constructs λ-algebra.

Algebraization of the flow diagrams.

Proving algebraically the equivalence of programs: multi-valued homomorphisms (2 papers)

A teacher whose work lives

Skordev was a good teacher and mentor. Through us his deed continues to live and grow.