Beyond the Turing Threshold: Productive Grammars generate Essentially Undecidable Languages
*
Luis M. Augusto September 4, 2026
Independent Researcher https://orcid.org/0000-0001-9097-5722
Abstract Emil Post's productive sets are not even semi-computable, let alone computable, being thus essentially incomputable.
Accordingly, formal languages whose set of words is a (completely)
productive set are essentially undecidable.
In this article, I elaborate on Post productivity
from the viewpoint of formal language theory:
I design formal grammars that emulate the
construction of productive sets of natural numbers and are thus beyond Turing-decidability.
1
Introduction
A core construct in formal language theory is the
(extended) Chomsky hierarchy : It distinguishes
formal languages into Turing-decidable and only Turing-recognizable, leaving us essentially ignorant with respect to the uncountably in nitely many languages that are beyond the grasp of the Turing machine (see Fig. 1), which since Turing (1936) remainsand is bound to remainas the decider of what is or is not computable in the mathematical universe of functions, sets, and relations. This result is well-known in the literature as the
Church-Turing Thesis.1
Regardless of whether one's philosophy of mathematics favors construction over discovery or vice-versa,
productive sets must be taken under the viewpoint of set construction. These in nite
sets, originally constructed in Post (1944), are incomputable; in fact, they are not even semicomputable, being thus essentially incomputable. Thus, one naturally wonders what generation or construction processes yield such sets. If we consider themas I shall do herefrom the viewpoint
* Published as a working paper under the same title in Ω ::=Journal of Formal Languages, 2, 35-65; submitted for standard publication in September 2026.
1 A rather intuitive formulation of this thesis is as follows: A function that is eectively calculable is a function that can be computed by a Turing machine. This formulation goes beyond Church's Thesis, which merely states that any
eectively calculable function is so if and only (abbr.: i ) if it is recursive. Tellingly, the so-far purely hypothetical range of computations beyond the limitations imposed by the Turing machine is called
1
super-computation.
Figure 1: The Chomsky hierarchy and beyond. (Source: Augusto, 2021.)
of the Chomsky hierarchy of formal languages, then productive word sets are wholly outside it, i.e. they are not Turing-recognizable, let alone -decidable, and thus justify our focusing on them for 2
providing an adequate framework to study essentially undecidable languages.
From this viewpoint,
one might wish to nd answers to questions such as: What kind of formal system(s) generate(s) such languages? Is there a class of formal grammars that can be associated with them? I address these questions in this paper. The aim of this study is thus to reduce our ignorance with respect to the uncountably in nitely many languages that are not amenable to the recognition or decision
productive grammars, outside productive languages, i.e. sets of words that
powers of the Turing machine. More speci cally, I shall show that the Chomsky hierarchy and its extensions, generate behave like productive sets of natural numbers.
Except for Dekker (1955), productive sets are typically studied as the complements of creative sets, and thus the literature on these sets is rather scarce. In eect, creativeness is seen as the one property that is shared by all the naturally arising unsolvable problems discovered by Church, Turing, and others in the 1930s and after (Cooper, 2004), but there are uncountably many productive sets without a creative set as their complement, which allows for research on them independently from the larger research on creative sets. Here, I am interested in productive sets per se, namely inasmuch as they provide the adequate framework to approach the questions speci ed above.
I
draw mostly on Post (1944) and Dekker (1955), with the odd bits from standard monographs or textbooks, to wit, Cutland (1980), Rogers (1967), Smullyan (1993), and Soare (2016). The present article is developed within two subjects that are more often than not con ated, to wit, recursiveness and computability. Computability theory is frequently just the name given to recursion theory when we are more interested in practical computing than in the associated mathematical formalisms and structures, but in fact the two are not necessarily one and the same subject.
Take the concepts
computable and recursive all too often seen as synonymous to char-
acterize a set. This synonymy is however not complete. When de ning a computable set in the
2 See Table 1 for the nomenclature used in Figure 1.
2
context of computability theory, we mightand perhaps ought totake physical resources into consideration.
Example 1. Consider the following set: S = {p | p is a polynomial over x with an integral root} We ask whether
S is computable. Given a polynomial p over x such as 2x3 + 6x2 − x + 5, we ask
if p ∈ S . In other words, we want to know if x = n, n ∈ Z. There is indeed an algorithm to test for this decision problem: We evaluate p for the values 0, 1, −1, 2, −2, 3, ... one at a time successively; if for some n ∈ Z it is the case that p = 0, then χS (p) = 1 (cf. Def. 6 below). Nevertheless, we have no guarantee that this algorithm will ever terminate: It will only eventually terminate if indeed
p ∈ S ; otherwise, it is obvious that it will run forever, because Z is an in nite set. Thus, S is in fact incomputable, though it is semi-computable. The physical resource at play in this example is time, but we could consider space instead. When in recursion theory we say that a set is recursively enumerableseen as a synonym for semicomputablebut not recursive, we say basically the same thing, but we prove it by either showing that there is a recursively enumerable (abbr.:
r.e.)
set
A whose complement is not r.e. or by
diagonalization, it being the case that in either case a contradiction is reached; the example given is almost always the set K = {x | x ∈ Dom (φx )}, and as it will be seen below nite time, or any 3
other physical resource or constraint, plays no role whatsoever in the proof.
It seems to me thus that this disparity in perspective is more than a simple nuance; it shows that Church's concept of the two subjects.
eective calculability is taken with fundamentally dierent meanings in
More speci cally, this concept, originally given in Church (1936), is taken in
a practical sense in computability theory and rather intuitively in recursion theory, it being the case that mathematical intuition entails here the notion of
induction, as argued in Soare (1996,
1999). Importantly, a function need not be recursive to be computable, as the zero function and
the projection function show (cf. Def. 3 below). In any case, I shall use the terms computable and recursive dierentially: I shall reserve the latter for functions and the former for sets. To these two terms I shall add a third, to wit, decidable to characterize word sets that are computable. In Section 3, I duly justify this addition to a terminology that often requires clari cation of its synonyms, precisely because
recursion, computability, and decidability are concepts that have emerged and
undergone nuanced developments in three subjects that largely overlap.
2
Post's Productive Sets
2.1
Some Remarks on Functions and Sets from the Viewpoint of Recursion Theory
2.1.1 2.1.1. Recursiveness and computability I begin by recalling some core concepts of recursion theory on functions and sets.
3 To be sure, the proofs by the Complementation Theorem or by diagonalization assume (often implicitly) Church's Thesis, i.e.
a method of eective calculability such as a Turing machine, which in turn assumes an algorithmic
procedure. But the onus of the proofs in recursion theory does not fall on the ine ciency of any such procedure, as in Example 1: They show instead by
reductio ad absurdum that there cannot be any algorithm that computes K.
3
De nition 2. Let N = {0, 1, 2, ...} = ω, |ω| = ∞ = ℵ0 , be the set of the natural numbers.4 N is a well-ordered set, as every subset N ̸= ∅ of N has a least element. An n -ary function f (x1 , ..., xn ) = f n (x) over N s.t. f : Nn −→ N is said to be total if it is de ned for every element in (n) its domain, denoted by Dom (f ) = Wf , and partial if it is de ned only for a subset of its domain. (n) The range of f is here denoted by Range (f ) = Ef . + 5 A function f that is partial is denoted by φ. I shall consider indierently N or Z . As usually, I write f (x) ↓ to denote that the (partial) function f (x) is de ned for all the xi in x, and f (x) ↑
f e f (or φ), i.e. the Gödel P s.t. Pe computes f (respectively φ). (In this article, e will be
otherwise. Instead of the subscript (or φ) we write , the index of number of a given program
employed to identify an arbitrary program, and thus no actual computation of a Gödel number will be carried out.) Indices other than
e will also occur, as any number n is an index of a (partial)
function f (x) if gn (x) = f (x).
De nition 3. A function f is said to be primitive recursive if it can be generated from the functions
z (x) = 0, succ (x) = x + 1, and Uin (x) = xi known as zero function, successor function, and projection function, respectivelyby zero or more applications of the following schemata known as the composition or substitution schema (1) and the primitive recursive schema (2):
(1)
f (x) = g (h1 (x) , ..., hm (x)) (
(2)
f (0, x) = f (x) f (y + 1, x) = f (y, f (y, x) , x)
If
f (x) = µyR (x, y)
(3)
R is a relation symbol, is also applied then the function partial recursive. De nition 4. (Church, 1936) A function f is recursive i it is total and eectively calculable ; it is partial recursive (p.r.) i it is eectively calculable.
known as minimalization schema and where obtained is
The following example introduces two functions that, albeit elementary, will play a major role in the elaboration below on productive sets.
Example 5. The functions f (x) = x, known as the identity function, and fx (x) = x + 1, known as the diagonal function, are recursive. In eect, f (x) = x + 1 is the successor function in De nition 3, and it is obviously total; fx (x) is called diagonal function because it is applied only on the elements in the diagonal of an in nite table or matrix
a0,0 a 1,0 . . . am,0 . . .
4 Recall that ℵ
A
s.t. we have
a0,1 a1,1
a0,2 a1,2
. . .
. . .
am,1
am,2
. . .
. . .
··· ···
a0,m a1,m . . .
···
am,m . . .
0 is the cardinality of a countably in nite set, i.e.
correspondence with N.
5 Enumerations will start with 0 or 1, according to convenience.
4
··· ··· ···
a set whose elements can be put in a 1-1
for every element of a given set A. The diagonal function will be denoted by δ (x). Then, we have δ : A −→ A s.t. δ (a) ̸= a for every a ∈ A s.t. a is ai,i , because δ (a) = a + 1. The identity function, denoted by ι (x) and which is also obviously total, is the special case of schema (2) when x = x, i.e. f (0, x) = x. (Alternatively, we can see the identity function as the projection function Iin (x) = xi .) The relationship between these two functions is that, as given by δ (a) ̸= a, the diagonal function is
never the identity on A; hence, set A is incomputable, as there is no eective method to enumerate the rows of
A
.
De nition 4 is actually Church's Thesis; in this, eective calculability is associated with an algorithmic procedure, i.e.
a function
f is eectively calculable i there is an algorithm that
outputs a value given a certain input value. (Note that an algorithm has only a nite number of instructions that are applied in a nite number of steps.)
De nition 6. Let there be given a set A ⊆ N. A is computable if the characteristic function of x A is eectively calculable:
with respect to
( χA (x) =
if x ∈ A
1 0
otherwise
A is semi-computable if the semi-characteristic function of x with respect to A is eectively calculable:
( χA (x) =
if x ∈ A
1 ↑
otherwise
Thus, if A is computable, then there is an eective method that calculates whether x ∈ A or x ∈ A for all x ∈ N, A denotes the complement set of A. If there is an eective method to calculate x ∈ A, but no such method to calculate x ∈ / A, then A is said to be semi-computable.
Remark 7. As anticipated in the Introduction, I am henceforth writing computable (instead of recursive ) and semi-computable (instead of recursively enumerable ) for a set A whenever there is an eective methodi.e. an algorithmto calculate the (semi-)characteristic function for A. I leave the above terminology for functions unchanged, because no function is computable (i.e. eectively calculable) if it is not a primitive recursive function or a composition of primitive recursive functions.
De nition 8. A set A that satis es the condition [(x ∈ A) ∧ (φx = φy )] =⇒ (y ∈ A) for all x, y ∈ N and φ a p.r. (unary) function, is called an
index set.
Remark 9. The reader should keep in mind the case when φx = φf (x) , where f (x) = ι (x) is the A is an index set, then f (x) ∈ A.
identity function. Clearly, if x ∈ A and
?
Theorem 10. (Rice's theorem) The problem φx ∈ A is undecidable if A ̸= ∅ or A ̸= N. Intuitively put, Rice's theorem formulates the result that the only computable index sets are ∅ and N. These two index sets are said to be
φ and N contains all its indices. p.r. functions is
trivial, because ∅ contains no index of any p.r. function
The meaning of this result is that any non-trivial property of
undecidable, a term that will be properly de ned below; because the set of all p.r. 5
(unary) functions is semi-computable this means that every non-trivial property of semi-computable sets is undecidable. The following de nitions and results draw on Post (1944). Eective calculability and enumeration are tightly associated and indeed we have:
De nition 11. A set A ⊆ N is semi-computable if its members can be enumerated as A = {f (0) , f (1) , f (2) , ...} = Range (f ) = Ef = Ee or, equivalently,
A = {0, 1, 2, ...} = Dom (f ) = Wf = We where
f is recursive and e is the index for A.
Recall that semi-computable is taken here as a synonym for recursively enumerable when speaking of sets; this explains why computably enumerable, a term also often found in the literature, is a synonym for semi-computable. The fact that a set
A is semi-computable does not mean
that it is computable.
Example 12. Let us consider the set K = {e | e ∈ We }, known as Gödel's diagonal set, and called in Post (1944) the complete set, because every semi-computable set We is computable in K. K is semi-computable. In eect, K is the domain of the p.r. function ( ψ (x) =
if φx (x) ↓
x ↑
otherwise
x. But K is K had an eectively calculable characteristic function, then the following function
which is eectively calculable by applying an algorithmsay, a program Px to input incomputable. If
would be eectively calculable:
( f (x) = Then, f (x) ̸= φx for every
φx (x) + 1 0
if x ∈ K if x ∈ /K
.
x, which shows that f cannot be recursive. Indeed, let f (x) = φx (x); K is semi-computable
then, we have φx (x) = φx (x) + 1, and 0 = 1, which is impossible. Hence, but incomputable.
Besides by a diagonalization argument, as in Example 12, we can show that a semi-computable set fails to be computable by Post's Complementation Theorem.
Theorem 13. (Complementation Theorem) A semi-computable set A ⊆ N is computable i its complement A is also semi-computable Proof. (⇒) If χA (n) = 1, then put n in A. Otherwise, put n in A. Hence, both A and A are semi-computable.
(⇐) Let A, A be semi-computable sets s.t. A = {n1 , n2 , ...} and A = {m1 , m2 , ...}. Given some n ∈ N, generate successively n1 , m1 , n2 , m2 , ... comparing with n. Obviously, the end result of our generation and comparison must be that either n ∈ A or n ∈ A, so in a nite number of steps we shall nd the ni or the mi that is identical with n. This is thus an eective method to determine the membership of any n to either A or A. Hence, A is computable. 6
The concept of
generated set introduced in the ⇐-direction of Post's proof of Theorem 13 will
play an important role in this work.
We have the following important result (which here is a
Proposition, but is just part of the main text of Post's paper):
Proposition 14. Every generated set of positive integers is semi-computable. Proof. This can be restated in two statements, to wit, (a) every generated set is eectively calculable, and (b) every eectively calculable set of positive integers is semi-computable. With respect to (a), eectively calculable just means the same as eectively enumerable, i.e. all one need have is an eective process to enumerate elements into a set as belonging to it; any recursive function
k or ω
will be such a process. We have then the set {f (i)}i=0
f
, which is semi-computable by Def. 5, and
we are done with (b).
k or ω
With respect to the set A = {f (i)}i=0
Remark
.
of the proof above, we have the following remark:
k
k ω 15 The set {f (i)}i=0 , is nite, is computable. The set {f (i)}i=0 is computable i it admits of a recursive enumeration in order of magnitude, and non-computable otherwise. In other words, every nite set is computable, and an in nite semi-computable set is computable i it is the range of an increasing function
f.6 Importantly, this also tells us that semi-computable sets that
are incomputable are always in nite.
Theorem 16. Every in nite semi-computable set A contains an in nite computable subset A′ . Proof. Generate in order the elements of the recursive enumeration α = n1 , n2 , ... of an in nite set A and let m1 = n1 . As for m2 , let m2 = ni2 , i.e. the rst ni greater than n1 , and so on successively; because α is a recursive enumeration we are assured that for every ni there is an nj later in α s.t.
nj > ni . We thus generate the set A′ = {m1 , m2 , ...} without repetitions in order of magnitude. ′ Clearly, A is a subset of A that is in nite and computable.
Theorem 17. There is a semi-computable set A of positive integers that is incomputable. Proof. By Post's Complementation Theorem, A is not semi-computable. We show this by the diagonalization method. Let U = {Ai | i = 1, 2, ...; Ai is s.c.}. s.c. abbreviates semi-computable,
A is semi-computable by Proposition 14. More precisely, U is x thus is, or is not, in U according as it is, or is not, in the i -th set Ai . So, if x is not in U, then it must be in U ; but then it is not in the i -th semi-computable set in U, and U diers from each semi-computable Ai in the presence or be a set of generated elements; then,
the set of all the semi-computable sets. A positive integer
absence of at least one positive integer. Hence, U is not semi-computable. Now, make U = A, and QED.
Example 18. The set K = {x | x ∈ Wx } is semi-computable but incomputable. This was shown in Example 12 by an application of diagonalization (i.e.
by employing the diagonal function).
/ Wx } is not semi-computable. Assume otherwise that K is also This also means that K = {x | x ∈ semi-computable. Then, for some e ∈ N we must have We = K , thus giving
x ∈ We ⇔ x ∈ K ⇔ x ∈ /K⇔x∈ / Wx We get a contradiction when making x = e, so we conclude that K is not semi-computable.
6 Recall that a function f over N is increasing, or order-preserving, if f (x) < f (y) whenever x < y for x, y ∈ N.
7
Corollary 19. An incomputable set that is not semi-computable is essentially incomputable. Proof. (Informal) Example 18 above shows that the attempt to compute K leads to a contradiction. In eect, note the paradoxical character of K , kindred with Russell's paradox: As it is possible to
/ {n}}. Hence, K is essentially incomputable. have Wn = {n}, then we have K = {n | n ∈
2.1.2 2.1.2. In nite sets Above, a few references, explicit or implicit, were made with respect to in nite sets. In nity plays a central role in this work, namely in relation to the following result, which is directly connected with the proof of Corollary 19 immediately above:
Proposition 20. Every incomputable set is always in nite. For the present study, it su ces to grasp the concept of
natural order, i.e. the well-ordering of
the natural numbers, denoted by the symbol <. I assume that the reader is acquainted with the principle of induction. With this principle in hand, one way to de ne in nity mathematically is by the following statement that elaborates formally on the fact that
there exists an in nite set :7
In nity Axiom: There exists at least a set I s.t. (i) ∅ ∈ I , and (ii) if x ∈ I , then also {x} ∈ I . Formally:
∃I [∅ ∈ I ∧ ∀x (x ∈ I ⇒ (x ∪ {x}) ∈ I)]
De nition 21. Let I be a set. We say that I is an inductive set, and we write I˘, i I is a witness to the In nity Axiom, i.e.:
I˘
i
[∅ ∈ I ∧ ∀x (x ∈ I ⇒ (x ∪ {x}) ∈ I)]
We can then account constructively for the existence of the set N in the following way:
Proposition 22. There is a unique set I s.t. I ⊆ J for every inductive set J. Proof. (Sketch) Starting from (1) I˘ ∩ J˘ is an inductive set, and (2) for K̆ , we let n o D = J ∈ 2K̆ | J is J˘ and
n o I = x ∈ K̆ | ∀J ∈ D : x ∈ J
I is an inductive set, (b) for every J˘ we have I˘ ⊆ J˘, and (c) if I ′ is an inductive set and for every inductive set J we have I˘′ ⊆ J˘, then I˘′ = I˘. we show that (a)
More intuitively, if we let n = {0, 1, 2, ..., n − 1} in the sense that the set number
n, then
0 = ∅,
1 = {0} ,
2 = {0, 1} ,
This can be expressed in the intuitive principle that
3 = {0, 1, 2} ,
n represents the natural
...
each natural number n should have n elements.
Then, by applying induction we have
0 + 1 = ∅ ∪ {0} = 1, 7 This is one of the seven axioms of the axiomatization of set theory known as Zermelo-Fraenkel set theory with the Choice Axiom (ZFC for short). See Augusto (2020) for a brief discussion and references to the standard literature.
8
1 + 1 = {0} ∪ {1} = 2 2 + 1 = {0, 1} ∪ {2} = 3 . . .
n + 1 = n ∪ {n} for every n ∈ N, and N is the smallest inductive set in the sense that
N=
\
D=
\
I.
The formulation above of the In nity Axiom implies that N ⊆ I˘, and if additionally we know that
N ⊇ I˘, then we can formulate it as the induction property of N: ∃I [∅ ∈ I ∧ ∀n (n ∈ I ⇒ n + 1 ∈ I)] ⇒ N = I˘
Remark 23. It is now obvious that we can rephrase the In nity Axiom as: There exists a re exive set. In eect, if we consider x ∈ I˘ as a rst element, we have the set I˘ = {x, {x} , {x, {x}} , {x, {x} , {x, {x}}} , ...} where the notion of
ordering is evident: We have x < {x} < {x, {x}} < ...
s.t. {x} is the
successor of x, etc. Denoting this relationship by Succ (n) for n ∈ N, we have: Succ (n) = n + 1 = n ∪ {n}
Let us now start with the rst element ∅ ∈ I˘; then we have
N = {∅, {∅} , {∅, {∅}} , {∅, {∅} , {∅, {∅}}} , ...} By correlating every x ∈ I˘ with {x} ∈ I˘, we obtain a one-to-one mapping of I˘ onto a proper subset
I˘
of 2
− ∅.
There are three notations used to denote in nity, to wit, ω , ∞, and N. They are not equivalent in the present work, though. As mentioned above, we have typically
N = {0, 1, 2, 3, ...} = ω but we prefer to settle things so that N denotes the in nite set of natural numbers and
|N| = ∞ i.e. ∞ denotes the cardinality of N, also often denoted by ℵ0 , without regard to order.
9
Remark 24. But the two notations ω and ∞ may coincide in the notion of tending to in nity. Recall that an in nite sequence is de ned as
(an ) = {an | n ∈ ω} where an denotes the
n -th term of in nitely many terms belonging to ω = N or ω = Z+ . Let now
f (n) be the identity function ι (n), i.e. f (0) = 0, f (1) = 1, ...; then we have lim f (n) = ∞
n→∞ where n
→ ∞ and f (n) = ∞ just is the conventional notation of mathematical analysis, but
because n ∈ ω we may write instead f (n) = ω . In particular, if we consider n ∈ ω as a superscript
n times
s.t. the
n -th term coincides with the n -th potency in a sequence s.t. an = a...a , then we have for z}|{
an unbounded sequential function f (a
n
):
lim f (an ) = a∞ = aω
n→∞
Example 25. Let a = 011 and n ∈ Z+ s.t. an = (011)n . Then, a1 = 011, a2 = 011011, ..., n times
z}|{ a = 011 , and n
∞
n
lim (011) = (011)
n→∞ Note that (011)
ω
provides us with a means to
ω
= (011) .
represent nitely the in nite string 011011011...
corresponding to
011 011011 ... |{z} 1 | {z } 2 } | {z 3 | {z } . . .
a rather cumbersome representation. That is to say that we employ the notation ω to denote an in nite sequence
ordered by N (or any in nite subset of N); in eect, ω is the standard symbol 8
for the rst in nite ordinal.
Thus, I shall employ the notation ω also for in nite cardinality if an
in nite sequence is implied.
Remark 26. One way to explain intuitively the dierence between the two notations for in nity, ω and ∞, is as follows: Let there be given some in nite set A; if we look upon this set statically as a constructed set, then we write |A| = ∞, but if our view on it is dynamic, in the sense that we are interested in how it is constructed, i.e. how its elements get to belong to it one by one, or sequentially, then we write |A| = ω . An important aspect of this dynamic viewpoint on in nity is that at any one time of this construction we can stop and see the obtained objects (e.g., strings of
8 The natural numbers less than ω are also called nite ordinals, because a set A is said to be nite if there
A onto some n ∈ N. By starting with 0 = ∅, 1 = {0}, ..., and using the operation n + 1 = n ∪ {n} we reach the next ordinal after all the ordinal numbers, i.e. ω = {0, 1, 2, ...}. Thus, ω is the rst in nite ordinal. By applying now the operation ω + 1 = ω ∪ {ω} = {0, 1, 2, ..., ω}, we obtain the in nite sequence of ordinals ω + 1, ω + 2, ω + 3, ..., which in turn is followed by in nitely more in nite ordinals ω + ω, ω + ω + 1, ..., etc. is a one-to-one mapping of
10
symbols) as constituting a nite set. Take for example the number π = 3.14159...; we denote the in nite character of its decimal expansion by |π| = ∞, but we write |π|5 = ω to denote that there are in nitely many 5's in the decimal expansion of π , the rst 5 in the 4th decimal position, etc. We can thus call these two perspectives respectively
2.2
static in nity and dynamic in nity.
Productive Sets
Recall now from Rice's theorem (cf. Theorem 10) that the set of the natural numbers N, just like
∅, is a trivial index set. Above, N was approached dynamically, i.e. it was shown how each natural there is a recursive function succ : N −→ N s.t. succ (n) = n + 1 = m. It follows that N is eectively enumerable; in fact, N is computable, as for every n, m ∈ N s.t. succ (n) = m, m > n. In eect, let W0 = ∅, W1 = {0}, W2 = {0, 1}, ..., and apply the identity function to xi = f (i), which is obviously order-preserving, as f (i) < f (i + 1) for xi < xi+1 . We then have: W0 = ∅
number m ∈ N i m = n + 1 for n ∈ N, i.e.
W1 = (W0 ∪ {f (0)}) = (∅ ∪ {0}) = 1, and f (1) ∈ W1 W2 = (W1 ∪ {f (1)}) = (1 ∪ {1}) = 2, and f (2) ∈ W2 . . .
Wn = {0, 1, ..., n − 1} ∪ {f (n − 1)} = (n − 1 ∪ {n − 1}) = n, and f (n) ∈ Wn {z } | Wn−1
Wn+1 = {0, 1, ..., n − 1, n} ∪ {f (n)} = (n ∪ {n}) = n + 1, and f (n + 1) ∈ Wn+1 | {z } Wn
so that we have:
N=
ω [
Wn =
ω [
f (n)
n=0
n=0
What happens now if we construct a set, say A ⊆ N, that is obviously inductive but s.t. for every
xi ∈ A it is the case that f (i) ∈ / (Wi ⊆ A), i.e. there is a number xi in A not in Wi ⊆ A? We
then have f (i) ∈ (A − Wi ) and f (i) ̸= xj for j = 0, 1, ..., i − 1, and A ⊇ {x0 , x1 , ..., xi−1 , f (i)} is incomputable, though it is inductive; in particular,
A clearly has an in nite semi-computable
= {f (0) , ..., f (n) , ...}. Such a set A is said to be productive, and its relationship with Rice's theorem can be formulated as follows: If A ̸= ∅ or A ̸= N, then A is either productive or subset A
′
the complement of a productive set. This result is directly mirrored in complexity theory in the following way: The productive sets, as well as their (semi-computable) complements, constitute essentially undecidable problems.
In eect, productive sets are constructed in analogy with the
well-known diagonal method to prove the incomputability of the interval (0, 1] ∈ R; in other words, there is no eective method (e.g., a Turing machine) to enumerate the elements of a productive set. Hence, and paradigmatically, the complete theory of the natural numbers N is productive and the system of Peano arithmetic is creative.
9
9 These correspond to the sets
N = {ψe | ψ ∈ L (N) and ⟨N, +, ∗, 0, 1, ≤⟩ |= ψ}
11
De nition 27. A set A ⊆ N is called productive if there is a recursive function f (x) s.t. for any n ∈ N, Wn ⊆ A We say that f (x) is a
⇒
f (n) ∈ (A − Wn )
productive function for A and A is productive relative to f (x).
Remark 28. This de nition entails that we have [
|A| >1
Wn ⊆ A
n denotes greater than by (at least) one element, i.e. no semi-computable subset Wn of A A, or, equivalently, there is always one element n in A that does not belong to any of its subsets
where > is
1
Wn . Clearly, we have |A| = ω (cf. Remark 26). These results will be formally proven below.
De nition 29. A set B of positive integers whose complement B is a productive set is called co-productive. A productive function f (x) for B is a co-productive function for B. Example 30. The prototypical example of a productive set is K = {x | x ∈/ Wx }; thus K is a co-productive set with respect to K (cf. productive function for
Example 18).
The productive function for K (the co-
K ) is the identity function ι (x) = x. Examples of other productive sets,
where other is to be taken in the sense that K is the prototypical productive set, are:
10
Tot = {x | φx is total} = {x | Wx = ω} F in = {x | |Wx | < |ω|}
A we can eectively nd a natural number n that A but not in Wn . Such a number is called a witness (that A ̸= Wn , ∀n). Importantly, Remark
This example shows that for a productive set is in
26 also entails the following results:
Lemma 31. For g (x) a recursive function, there is a recursive function k (x) s.t. for every n ∈ N we have Wk(n) = Wn ∪ {g (n)}
and the set A s.t. g (x) ∈ A is productive relative to k (x). Proof. De ne
( φk(n) (y) =
1 ↑
if y ∈ Wn or y = g (n) otherwise
.
and
PA = {ψe | ψ ∈ L (N) and P A |= ψ} where L (N) is rst-order predicate language with identity,
PA
denotes the axiomatization of Peano arithmetic, and
e is the Gödel number of ψ. See Augusto (2020) for the symbol |=, which denotes logical consequence.
10 Prototypical, in turn, is taken in the sense of K ≤ A, where ≤ denotes (Turing-)reducibility. Note that K
K ) is an index set (cf. Def. 8). In eect, for two index sets A and B we have the result: If A is productive B is productive. The reader is referred to any of the cited texts on computability for elaborations on reducibility. Interestingly, in the case of the sets Tot and Fin, we have both K ≤ Tot and K ≤ Tot, and also (as well as
and A ≤ B , then
both K ≤ F in and K ≤ F in.
12
Then, we have
Wk(n) = Wn ∪ {y} . Let now y ∈ A; it is readily seen that
A is productive relative to k (n).
Theorem 32. If A ⊆ N is productive, then A has an in nite semi-computable subset. Proof. Let A be productive with productive function f (i), i ∈ N abbreviates the index ei , and let y0 = f (0). Because A is productive, we have y0 ∈ (A − (W0 = ∅)). Obtain now y1 = f (1) s.t. W1
z}|{ y1 ∈ A − W0 ∪ {y0 }, then an element y2 = f (2) s.t. y2 ∈ A − {y0 } ∪ {y1 }, etc. | {z } {z } | W1
W2
The set Wn+1 = {y0 , y1 , ..., yn } is a generated set, and hence it is semi-computable by Proposition
Wn z }| { n−1 14, but yn+1 ∈ A − {yi }i=0 ∪ {yn }, so yn+1 ̸= y0 , y1 , ..., yn for every natural number n ≥ 0. | {z }
Wn+1
Hence, the set {y0 , y1 , ...} ⊊ A is an in nite semi-computable set. The above results allow us to rede ne a productive set in the following way:
De nition 33. A set A ⊆ N is productive i there is a recursive function k (x) s.t. for all n ∈ N, ( Wn ⊆ A
⇒
Wk(n) ⊆ (A − Wn ) Wk(n) = |ω|
(1) (2)
.
Corollary 34. If A ⊆ N is productive, then A is not semi-computable. Proof. If A were semi-computable, there could be no positive integer yn+1in A not in the semi-
computable subset Wn+1 consequently
⊆ A.
But yn+1
∈ (A − Wn+1 ) where Wn+1 =
n−1
{yi }i=0 ∪ {yn } , and
A is not semi-computable. In eect, we would have it that there would be a natural
number n + 1 ∈ [(A − (Wn = A)) = ∅], an absurdity.
De nition 35. A set A ⊆ N is completely productive (c.p.) if there is a recursive function g (x) s.t. for every n ∈ N we have
g (n) ∈ A ⇔ g (n) ∈ / Wn or equivalently
g (n) ∈ [(A − Wn ) ∪ (Wn − A)] . The function g (x) is said to be a
c.p. function of A and A is said to be c.p. relative to g (x).
Example 36. K is c.p. with ι (x) as c.p. function. In eect, by the de nition of the set K, x ∈ Wx ⇒ x ∈ / K and x ∈ / Wx ⇒ x ∈ K .
Proposition 37. Every c.p. set A is productive. Proof. Wn ⊆ A implies that [(A − Wn ) ∪ (Wn − A)] = (A − Wn ). (It is not known whether there is a productive set that is not c.p.)
13
Remark 38. Obviously, [(A − Wn ) ∪ (Wn − A)] ̸= ∅, and so again we have A ̸= Wn , and n is a witness for the fact that A is c.p.
De nition 39. Let A ⊆ N be a productive set and Ψ an eective procedure to nd for every semi-computable subset Wn of A a witness to the fact that Wn ⊂ A. The set of all witnesses of A, called the productive center of A with respect to Ψ, is denoted by ΠΨ (A). Clearly, Dom (A) := {n | Wn ⊆ A}.
De nition 40. Let A ⊆ N be productive relative to f (x). Then, the set Π (A, f ) := f (Dom (A)) is called the productive center of A relative to f (x). The subset Π of A is called a productive center of A if Π = Π (A, f ) for some productive function f (x) of A. Proposition 41. If Π0 is a productive center of the productive set A, there is a productive center Π1 of A s.t. Π1 ⊆ Π0 and |Π0 − Π1 | = ω . Proof. Let f0 (x) be a productive function for A s.t. we have Π0 = Π (A, f0 ). Let now f1 (n) := f0 (k (n)) for k (n) a recursive function s.t. Wk(n) = Wn ∪ B , where B ⊆ Π0 . Let now Π1 = (A, f1 ). Then, it is easy to see that f1 (n) is a productive function of A and Π1 ⊆ Π0 . Hence, B ⊆ (Π0 − Π1 ) is an in nite semi-computable subset of A and |Π0 − Π1 | = ω . The following statements are left without proof. The objective is to give an idea of the
productivity of productive sets.11
in nite
Corollary 42. Every productive set A has a productive center Π1 s.t. |A − Π1 | = |ω|. Theorem 43. Every productive set has exactly countably many productive centers and exactly countably many productive functions. Theorem 44. Let A be productive relative to f (x) and let Π (A, f ) ⊆ B ⊆ A. Then, B is productive relative to f (x) and Π (B, f ) ⊆ Π (A, f ). Corollary 45. If A is productive relative to f (x), then Π (A, f ) is also productive relative to f (x). Corollary 46. Every productive set induces exactly k productive sets. 3
Productive Grammars and Essentially Undecidable Languages
3.1
Review of terminology and notation
In this Section, I recall the basic aspects of formal language theory that are relevant for the main subject of this paper. For convenience, I divide it into two smaller Sections, one recalling the core aspects of formal language theory and another reviewing Turing-decidability.
11 The proofs can be found in Dekker (1955).
14
3.1.1 3.1.1. Basics of formal language theory De nition 47. Let Σ = {a1 , a2 , ..., an } be a set of symbols (also: letters ) called an alphabet. If a1 precedes a2 , etc. up to an , a property denoted by a1 ≺ a2 ≺ ... ≺ an , then Σ is said to be in
lexicographic order. A word over the set Σ is a nite sequential factorization w = ai1 ai2 ...aik
i ∈ {1, 2, ..., n}, of symbols over Σ s.t. k ∈ N is the length of w, a property denoted by ℓ (w) = k . The intervals (ai1 , aik ], [ai1 , aik ), and (ai1 , aik ) of a word w are called subwords, respectively. 1. The substring w
′
= [ai1 , aik ) is called a (word) pre x.
2. The substring w
′
= (ai1 , aik ] is called a (word) su x.
3. The substring w
′
= (ai1 , aik ) is called a (word) in x.
Examples of alphabets in lexicographic order are the Roman alphabet {a, b, ..., z} or subsets thereof and the alphabet {0, 1}. From the above de nition, we have it that every pre x and every su x
proper su x, proper pre x, and a proper in x, respectively, as any word can be seen as a su x, a pre x, or
is an in x. By comparison to w = ai1 ai2 ...aik , the above subwords are said to be a a
an in x of itself. We denote an arbitrary (sub)word over an alphabet Σ by the nal letters of the Roman alphabet u, ..., z .
De nition 48. A word language L over Σ is a set of words w over Σ. Henceforth, I write only language(s), as I do not discuss any formal languages other than word languages.
De nition 49. A word w s.t. ℓ (w) = 0 is called the empty word, denoted by ϵ (or λ). Then, Σ∗ denotes the set of all words, including the empty word, over Σ. A language L over Σ just is a subset ∗
of Σ , i.e. language
L ⊆ Σ∗ (and any subset of Σ∗ , including ∅, is a language). More formally, we de ne a
L intensionally as:
This de nition gives us the
L = {w ∈ Σ∗ | w has property P }
complement of a language L as: L = {w ∈ Σ∗ | w hasn't property P }
+ + If a language L ̸= ∅ over Σ does not include the empty word, then we write Σ , i.e. Σ = S i , where i ∈ N denotes the length of the words that are elements (Σ∗ − {ϵ}). Note that Σ+ = i=1 ΣS i 0 ∗ i of Σ . As Σ = {ϵ}, we have Σ = i=0 Σ . Example 50. Consider the language L = ab, aab, aaab, ..., ai b, ... . This extensional de nition corresponds to the intensional de nition:
o n n+1 L = an b ∈ {a, b} |n ≥ 1 The complement of this language is constituted by words like
15
b, an , an bm for m > 1, etc.
Note in the above de nition that {a, b}
n+1
denotes that the words built over the alphabet {a, b}
+
are of length n + 1 for n ≥ 1; this is simply a speci cation of {a, b} . It should be obvious that if
Σ = ∅, then Σ∗ = Σ0 , but if Σ ̸= ∅, then Σ∗ is in nite, and because formal languages L over Σ just ∗ are subsets of Σ , they are in in nite number, too. However, a language L over an alphabet Σ can be nite or in nite.
Example 51. The languages L = ∅, L = {ϵ}, and L = {w ∈ Σ+ | w ∈ Hamlet} (where Hamlet denotes the set of all the words in Shakespeare's play identically entitled) are nite. The language of Example 50 above is in nite. A language can also be in nite if its words are in nite words. This requires a disambiguation of the expression in nite language.
De nition 52. Let (w||j )ω denote the in nite iteration Sωof the j -th letters of the nite word w + ω ω over an alphabet Σ . Then, w ∈ Σ , where Σ = i≥1 Σi , is called a periodic ω -word and Sω Lω = L ⊆ Σω = i=1 Li is a periodic ω -language. A periodic ω -word w s.t. w||j is a su x is called an ultimately periodic ω -word. Example 53. Given Σ = {a, b}, any word w ∈ {a, b}ω in which there are in nitely many iterations ∗ ω
ω
ω
b, baω , (ab) , abω a) is an in nite word over Σ and thus constitutes a language ω L . For instance, the language L = {w ∈ {a, b} | w = abω } is an ω -language, namely an ultimately periodic ω -language. In eect, we have: L = ab, abb, ..., abi , ... of w||j (e.g., a b , a
ω
I shall abbreviate (ultimately) periodic
ω -word and (ultimately) periodic ω -language as,
respectively, ω -word and ω -language. The disambiguation between an in nite language and an
∗ ω ω -language, respectively denoted by L and L , consists formally in the following result, which Sn<ω ∗ i requires the speci cation Σ = i≥0 Σ :
Proposition 54. For L∗ and Lω languages of nite and in nite words, respectively, we have L∗ ∩ Lω = ∅.
Proof. (Informal) For Σ = ∅, we have L∗ ⊆ Σ∗ = {ϵ}, but Lω ⊆ Σω = ∅. Clearly, {ϵ} ∩ ∅ = ∅. We now apply induction on n > 0: It is obvious that (n + 1 = m) ̸= (n + 1 = ω) whenever m < ω , and again we have Σ
+
∩ Σω = ∅.
Let us now restrict the discussion to the case when, for a word
w s.t. ℓ (w) = k where k ≥ j ,
we have
a1 a2 ...aj−1 aj | {z } w||j
aj+1 ...ak
j -th letters of a word w correspond to a (proper) pre x thereof. De nition 55. The pre x factorization of a word w ∈ Σ+ s.t. ℓ (w) = j consists of j pre xes w1 , w2 , ..., wj s.t. w1 = a1 , w2 = a1 a2 , etc., up to wj = a1 a2 ...aj . Then, the pre x closure of w is
i.e. when the
de ned as:
w b = wi ∈ Σ+ | i, j ∈ N and i ≤ j = {w1 , ..., wj−1 , wj } s.t.
{w1 } ⊂ {w1 , w2 } ⊂ ... ⊆ {w||j } . 16
∗
Note that w0 = ϵ, a fact to take into consideration for a language over Σ , as we then have
{w0 } ⊂ {w0 , w1 } ⊂ ... ⊆ {w||j } for j ≥ 0; then, w ∈ Σ
∗
is factorized into j + 1 pre xes and the closure of the word
w s.t. ℓ (w) = j
is given by w b = {w0 , w1 , ..., wj }.
De nition 56. A language L ⊆ Σk is said to be pre x-closed, denoted by Lb, if we have the (possibly in nite) union
b= L
[
w b
for every w ∈ L.
Remark 57. Clearly, the language L = {ϵ} is pre x-closed, as we have bϵ = {ϵ} = Lb, but L = ∅ is
b = ∅. not pre x-closed, as we have L
Example 58. For instance, for the language L = {aa, aba, abba} over {a, b}∗ the pre x closure of L is the set: b = {ϵ, a, aa, ab, aba, abb, abba} L In eect, we have for the word aa ∈ L,
ϵ aa |{z} w0
| {z } w1
| {z } w2
b. and w0 , w1 , w2 ∈ L The ω -languages can also be pre x-closed.
Below, in Remark 68, I account formally for this
anti-intuitive result.
ω = a, ab, ab2 , ..., abi , ..., abω . For the word d Example 59. The pre x-closure of the word abω is ab
ω a = a, ab, ab2 , ..., abω , abω a , i.e. ab ω ⊂ ab ω a. d [ [ abω a, we have the pre x-closure ab Languages are
generated by formal grammars, in the sense that upon the application of syntactic derived that belong to a speci c language Σ∗ or
rules on strings over a given alphabet Σ words are
Σω . I next provide the de nitions of these core terms.
De nition 60. A formal grammar is a 4-tuple G = (V, T, S, P ), where V = {A1 , ..., An } is a set of variable symbols and T = {a1 , ..., am } is a set of terminal symbols, with (V ∩ T ) = ∅, S ∈ V is the start symbol, and P = {r1 , ..., rk } is a set of rewriting rules of the form
α → β |{z} |{z} LHS
RHS
where LHS and RHS abbreviate left-hand side and right-hand side, respectively, denoting that string α ∈ (V ∪ T )
+
can be rewritten as string β ∈ (V ∪ T )
symbol.
17
∗
i α has at least one variable
Rewriting rules are also called production rules or productions; hence the
P. In order to dis-
tinguish clearly between variables and terminals uppercase and lowercase letters, respectively, are used. The rst production rule r1 is always S → β . The language
L generated by a formal grammar
is denoted by L (G).
De nition 61. A derivation of a word w ∈ L (G) from S ∈ VG is a nite sequence of steps each of k
which is the application of some production rule in {ri }i=1 ⊆ PG :
1
2
3
n
r1
ri
ri
ri
Dw = S =⇒ α1 =⇒ α2 =⇒ ...αn =⇒ w
leftmost (rightmost ), denoted by α =⇒l β (respectively α =⇒r β ), if at each step a production is applied to the leftmost (respectively rightmost) variable in α. A derivation α =⇒ β is said to be
G that generates leftmost (rightmost) derivations is called a left-derivation right-derivation ) grammar. De nition 62. The sequence of the k rules of a leftmost grammar applied in n steps in a derivation Dw is called a parse and is de ned as
Accordingly, a grammar (
Pw = r1,1 ri,2 ri,3 ...ri,n where ri,j , 1 ≤ i ≤ k , denotes that rule ri is the
j -th rule applied for 1 ≤ j ≤ n.
Every leftmost (rightmost) grammar can be converted into a rightmost (leftmost, respectively) grammar, but here I shall focus on leftmost grammars (henceforth just grammars). A parse Pw
N is the set of nodes, labeled by S ) or the interior nodes and by the terminals in w if they are leaves,
is typically constructed by means of a tree Tw = (N, E) where variables in the case of the root ( and
E is the set of edges joining two nodes. Clearly, every derivation Dw corresponds to a parse Pw ,
and reciprocally. The above de nition allows for the conception of an alphabet as Σ = (V ∪ T ), as we have for a given string α ∈
Σ∗ = (V ∪ T )
∗
, but we have w ∈ (T
∗
= ((Σ − V ) ∪ {ϵ})). That is
to say that no string is a word if it contains at least one variable; this, in turn, entails that no LHS
Chomsky grammar G M s.t. L (G) = L (M ) in the sense that L (G) is recognized by M, where by recognition it is understood that M can completely
of a production rule may consist entirely of terminal symbols. This de nes a if (i) Σ is nite and (ii) L (G) is associated with a machine model
process an input word one symbol at a time halting then in an accepting state. Table 1 provides all the information on Chomsky grammars required in this work. Note that this table schematizes more precisely the
extended Chomsky hierarchy, i.e. the hierarchy of the languages generated by
the four grammar types 0 through 3, known as Chomsky grammars, extended by the recursive 12
languages, for which no grammar is (yet) known (cf. Fig. 1; see Table 1 for the nomenclature). Note the following result about the Chomsky hierarchy:
Proposition 63. The Chomsky hierarchy is a proper inclusion hierarchy: RG L ⊂ C F L ⊂ C S L ⊂ RE L
Proof. Trivial. There are regular languages that are not context-free languages, there are contextfree languages that are not context-sensitive languages, and there are context-sensitive languages that are not recursively enumerable languages.
12 Recall that a recursively enumerable set is a semi-computable set and a recursive set is a computable set.
In
the (extended) Chomsky hierarchy, the recursion-based nomenclature has been kept for languages, despite a move to dierentiate the terminology of recursion theory and computability theory, as noted in the Introduction.
18
Grammar
α→β
Type 0
α ∈ (V ∪ T )+ , |V (α) | ≥ 1 β ∈ (V ∪ T )∗
Unrestricted
Language Class & Prototypical Language
Recognizers
Recursively enumerable (RE L )
Turing machines (TMs)
L = {(m, w) | m halts on w} Recursive (RL )
L=
Type 1 Context-
n
Total TMs (Deciders)
o n a2 | n ≥ 0
α, β ∈ (V ∪ T )+ , |β| ≥ |α| α = γAδ β = γXδ γ, δ ∈ (V ∪ T )∗ X ∈ (V ∪ T )+
Context-sensitive (C S L )
Linear-bounded
L = {an bn cn | n > 0}
automata
α ∈ V, |α| = 1 β ∈ (V ∪ T )∗
Context-free (C F L )
Pushdown automata
sensitive
Type 2
L = {an bn | n > 0}
Context-free
Type 3 Regular
α ∈ V, |α| = 1 β = Av or vA A ∈ V ∗, v ∈ T ∗
Regular (RG L )
Finite-state automata
L = {an | n > 0}
Table 1: The extended Chomsky hierarchy. (Adapted from Augusto, 2021.)
Remark 64. We also have
... ⊂ C S L ⊂ RL ⊂ RE L
if we consider the extended Chomsky hierarchy, which simply means what we call recursively enumerable languages are word sets whose complements are not recursively enumerable, i.e.
semi-
computable. I can now de ne a language more precisely as follows:
De nition 65. Let G be a formal grammar. The language L = L∗ generated by G is de ned as n o ∗ L (G) = w ∈ T ∗ | S =⇒ w G
n
n ∗ in G derivation steps, and * (Kleene star) denotes the re exive and transitive closure of the relation + =⇒ ⊆ (V ∪ T ) . G
where =⇒ denotes a derivation step s.t.
we have S
=⇒ α for the string α ∈ (V ∪ T )
This de nition applies directly to the Chomsky languages.
Example 66. Consider the formal grammar G = ({S, A, B} , {a, b} , S, P ) with
(r1 ) S → aA (r2 ) A → aAB | a P = . (r3 ) B → b | ϵ 19
This is a Type-1 Chomsky grammar. The language generated by this formal grammar is:
L (G) = {an bm | n ≥ 2, m ≥ 0} = = {aa, aaa, aaaa, ..., aab, aabb, aabbb, ..., aaab, ...} 13
3
The derivation of the word a b is:
S =⇒ aA =⇒ aaAB =⇒ aaaB =⇒ aaab r3
r2
r2
r1
The parse of this word is constructed by means of a tree as displayed in Figure 2. This language is pre x-closed: For example, for the word aaab we have the pre x closure:
[ = {a, aa, aaa, aaab} aaab \ Note that a ∈ / L (G), but it is a proper pre x of aaab ∈ L (G).
Figure 2: Parse tree Taaab .
ω
We can extend De nition 65 above to the ω -languages by specifying for L = L
n o ω L (G) = w ∈ T + | S =⇒ w G
where
G is an ω-grammar.
De nition 67. A formal grammar G = (V, T, S, P ) s.t. P contains at least one rule of the form α → βγδ where α ∈ (V
+
∪ T ∗ ), β, δ ∈ (V ∪ T ) , and γ ∈ V ω , is called an ω -grammar if V ω = (V + ) . ω
∗
13 Note that I abbreviated the rules by using |; in fact, there are ve rules in this grammar, but its simplicity allows for this abbreviation.
20
The notation (V
+ ω
)
denotes that one (at least) or more variables in
Let it be the case that the RHS of a rule is bA
ω
V is/are in nitely iterated.
c and we have A → a; then, we have the partial
derivation
i
ω
bAω c =⇒ baAω c =⇒ ba2 Aω c... =⇒ ba2+i Aω c... =⇒ baω c ω
where ba
c is an ω -word, but aω denotes an in nite sequence of a 's.14
Remark 68. The rule A → a is thus a continuous mapping fω : V ω −→ T ω that is in fact an
: V ∗ −→ T ∗ . In eect, consider that for win , ∞ ω denoting that a subword wi is iterated n times, we have wi = limn→∞ = wi . This allows for the pre x closure of an ω -language, inasmuch as we have for a given ω -word w , w b = w1 , ..., wi1 , wi2 , ..., wiω , ..., wj extension of an unbounded sequential function f∗
where 1 ≤ i ≤ j , and |w| b = ∞ but extensionally
nitely representable.
Example 69. Consider the ω-language L = {w ∈ {a, b}ω |w = abω }. The ω-grammar G = ({S, A, B}, {a, b} , S, P ) where (r1 ) S → AB ω (r2 ) A → a P = (r3 ) B → b generates this language. As seen above in Example 59, this ω -language is pre x-closed. A derivation
ω
of ab
is:
i
ω
r3
r3
S =⇒ AB ω =⇒ aB ω =⇒ abB ω =⇒ abi+1 B ω =⇒ abω r1
The parse tree
ω
r2
r3
Tabω is displayed in Figure 3, where the ellipsis denotes the in nite derivation
B =⇒ b.
Figure 3: Parse tree Tabω . The fact that, as pointed out above in Remark 68, the set w b for
w an ω-word is extensionally
nitely representable, allows for the recognition of ω -languages by nite automata.
The class of
14 Of course, an ω -word can coincide with an in nite sequence, say, aω or (ba)ω ; in other words, an in nite sequence of terminal letters is any of a pre x, a su x, or an in x. In the literature, ω -words are typically restricted to words of the form vz ∈ Lω where v ∈ T ∗ and z ∈ T ω . See, e.g., Staiger (1997) for a formal discussion of these ω -languages.
21
recognizers for the the
ω -languages is the so-called ω -automata, of which the Büchi automata are
prima inter pares. See Staiger (1997) for the case of the ultimately periodic ω-languages, and
Augusto (forthcoming) for the class of the ω -regular languages, a special subclass of these languages.
3.1.2 3.1.2. Turing-decidability for languages Recall from the remark on De nition 62 above that every word derivation Dw corresponds to a
word parse Pw , and reciprocally. However, it might not be easy to construct a parse tree for a given derivation. This is typically the case for the Type-0 Chomsky grammars.
Example 70. Consider the formal grammar G = ({S, A, B} , {a, b} , S, P ) with (r1 ) S → BA (r2 ) A → ϵ (r3 ) B → aBb P = . (r ) aBb → aa 4 (r5 ) bA → bbbA This is a Type-0 Chomsky grammar. The language generated by this grammar is:
L (G) = {an bm | n ≥ 2, m = n − 2 or m = n + 2k, k ≥ 0} 2 4
We can derive the word a b
∈ L (G) as follows:
S =⇒ BA =⇒ aBbA =⇒ aBbbbA =⇒ aBbbbbbA r1
r3
r5
r3
=⇒ aabbbbA =⇒ aabbbb r4
r2
The parse tree for this word is shown in Figure 4.
Figure 4: Parse tree Ta2 b4 .
22
De nition 71. Let L ⊆ Σ∗ be a language. The decision problem for L, denoted by DPL , consists ? in nding a Turing machine M capable of answering the question w ∈ L, known as the membership problem.15 Then, L is said to be Turing-decidable if there is a Turing machine M that computes ( DPL (w) =
Yes
if w ∈ L
No
if w ∈ /L
s.t. we have the sets
L = {w ∈ Σ∗ | M halts on input w in state qa } where qa denotes an accepting state, and
L = {w ∈ Σ∗ | M halts on input w in state qr } where qr denotes a rejecting state.
Remark 72. This is to say that a Turing machine M decides a language L i it halts on every input word w, whether in an accepting or a rejecting state. If M halts in an accepting state when w ∈ L for a given language L, but fails to halt in a rejecting state whenever w ∈ / L, then we say that L is a semi-decidable language. If M never halts on an input word w, then L s.t. w ∈ L is undecidable. Recall Remark 64 above. We have the following result:
Theorem 73. Every Chomsky grammar of Types 3 through 1 generates decidable languages. Proof. (Informal) In the extended Chomsky hierarchy, we have the strict inclusion relation: RG L ⊂ C F L ⊂ C S L ⊂ RL
De nition 74. Note that I am employing here a Turing machine as a 7-tuple M = (Q, Γ, #, Σ, q0 , H, δ) Q is a nite set of states, Γ is the tape alphabet, # ∈ Γ is the blank-cell symbol, Σ ⊆
where
(Γ⧹ {#}) is the input alphabet, q0 ∈ (Q − H) is the initial state, H = {qa , qr } for H ⊆ Q is the set of halting states, and δ : ((Q − H) × Γ) −→ (Q × Γ × {L, R}) is the transition function with L, R denoting left and right motion, respectively. A con guration for M is a pair Ci∈N = (q, uav) indicating that M is in state q ∈ Q (q0 ∈ Q for the initial con guration C0 ) with the current tape string uav and reading the symbol a. Con guration Ci yields con guration Ci+1 = (p, xby) in one step or move, written Ci ⊢M Ci+1 , i the transition δ (q, a) changes con guration Ci to con guration Ci+1 , i.e. i we have δ (q, a) = (p, b, ▽) where p ∈ Q, b ∈ Σ is the (new) symbol on the tape, and ▽ ∈ {L, R}. A computation for M is a nite sequence of con gurations C0 , C1 , ..., Cn n s.t. Conf (M, w) = {Ci }i=0 is the set of all the con gurations of M when computing a given input word
w.
For simplicity, unless otherwise stated a Turing machine M is deterministic, i.e. for every q
∈ Q and a ∈ Γ.
|δ (q, a)| = 1
Clearly, the Turing machine M in the de nition above eectively
calculates the characteristic function χL (w) (cf. Def. 6 above) if we make 1 stand for qa and 0 do so for qr . In other words, a language
L is Turing-decidable i the set L is Turing-computable,
15 The decision problem is also known in the literature as the Entscheidungsproblem, because of its rst formulation in German (for logical formulas) by the mathematician D. Hilbert. Cf. Hilbert & Ackermann (1928).
23
enumeration, which was already discussed above, but before I address that subject let us agreewith
a property denoted by L (M). An alternative formal way to formulate this is by the notion of
Post (1944)that recursive is the technical term corresponding to the more intuitive eectively
eective calculability as mechanical computability ; in fact, he showed that all computable numbers are eectively calculable by means of the Turing machine. This, now known as Turing's thesis, allows us to ex-
calculable when speaking of functions. Turing (1936) precisely de ned Church's
change the term recursive by the term Turing-computable in view of the short discussion in the Introduction, and because no function is computable if it is not computable by a Turing machine we shall henceforth satisfy ourselves with the abbreviation computable.
Lemma 75. No con guration Ci+1 ∈ Conf (M, w) of a Turing machine M is a proper pre x of a con guration Ci ∈ Conf (M, w). Proof. For every word w s.t. ℓ (wi+1 ) > ℓ (wi ), we have w1 , w2 , ..., wn |{z} |{z} |{z} C1
C2
Cn
where every Cj , 1 ≤ j ≤ n, is a unique con guration of M.
De nition 76. Let M be a Turing machine with n tapes, n ∈ Z+ , s.t. the content on tape i, i 1 < i ≤ n, is a word i w, denoting the word w on the i -th (We may consider that every w is tape. n a word that has been accepted by M so that L (M) = On every
i
w i=2 is the language recognized by M.)
i -th tape the content is i w = a1 a2 ...ak #..., k ≥ 1, with symbol a1 at the leftmost cell of
the tape and s.t.
ak is immediately followed by an in nite number of empty cells. Let tape 1 of
this Turing machine be a one-way write-only tape s.t. at the end of the computation the content of
i
i
i
i 's are dierent and il w denotes that i w is the l -th word enumerates L. M enumerates all the strings of L in canonical order if
tape 1 is 1 w#2 w#...#n−1 w#... where all on the sequence. This M
shorter strings precede longer strings and strings of the same length are alphabetically ordered. Clearly, a Turing machine enumerates a language L (M) in canonical order i it computes i i i k \ L (M), i.e. i (a) for every word w ∈ Σ it computes w1 , w2 , ...,i wk = ic w and (b) in such a i i i i i i i way that ℓ l+1 w ≥ ℓ l w and l a1 ⪯ l+1 a1 , ..., l ak ⪯ l+1 ak where l aj denotes the j -th letter of the
j -th pre x of the l -th word.
Theorem 77. For every language L ⊆ Σ∗ , L is semi-Turing-decidable i there is a Turing machine M that enumerates L, and L is Turing-decidable i there is a Turing machine M that enumerates the elements of L in canonical order. Proof. (Informal) If M simply enumerates L, then L is clearly a semi-computable set, but if M enumerates L in canonical order, then both L and L must be semi-computable by the Complementation Theorem (cf. Theorem 13).
Corollary 78. A language L is Turing-decidable i it is a pre x-closed language L\ (M). Proof. (Informal) By Lemma 75, every Turing machine can compute L\ (M) for a given language L (M). If a language L is not pre x-closed, its words cannot be enumerated by a Turing machine M in canonical order. In particular, for every word w ∈ L ⊆ Σk , there is a pre x wk s.t. M computes wk−1 , ℓ (wk−1 ) < ℓ (wk ), but M fails to compute wk s.t. ℓ (wk ) ≤ ℓ (w). 24
The Turing machine is a wholly abstract machine; in eect, it is equipped with one or more in nite tapes. In practice, we work with
parsers, also called syntax analyzers. An interesting aspect
of parsers is that they emulate the workings of a Turing machine almost to perfection: Given some grammar
G with alphabet Σ, there might be input words in Σ+ on which they do not stop. This
means that a parser is as good a Turing machine as we can get an implementation thereof. For this reason, I henceforth write simply decidable, instead of Turing-decidable with respect to a language L (G).
Example 79. Consider again the language L (G) generated by the grammar G of Example 70 above. The parser implemented by the software j ap accepts all words in L (G) but it does not halt on any word in {a, b}
+
that does not belong to this language; more precisely, this parser is unable
to construct the parse tree of any such word, entering into an in nite node generation. Hence, this Type-0 grammar generates a semi-decidable language.
3.2
Productive grammars and productive languages
As seen above, a set A ⊆ N may be only semi-computable or even computable, the latter case depending on whether both
A and its complement A are semi-computable sets. Languages are just L is called decidable if
sets of words; in the jargon of formal languages here adopted, a language
its is a computable set and semi-decidable if it is only semi-computable. set by employing Turing machines.
This terminology was
In Section 2.2 above, it was shown that productive sets are
incomputable. Then, if we construct languages that behave like productive sets, we have languages that are not only undecidable, but actually essentially undecidable languages; in this case, there is no Turing machine that can decide for each word w ∈ L, where
w is one of the words in L.
L is de ned intensionally, whether
De nition 80. Let G be a grammar. If G has at least one production rule on strings of n letters that mimics a productive function on n ∈ N, called a productive rule, then G is called a productive grammar. A language L = L (G), where G is a productive grammar, is called a productive language. Example 81. Consider the grammar G = ({S, A, B} , {a, b} , S, P ) with:
(r1 ) S → aA (r2 ) aA →l aaAB P = (r3 ) B → b
l
The subscript in rule r2 on → prescribes that this rule is compulsorily a leftmost-derivation
n
rule. We have L (G) = {a
\ b | n ≥ 1}, but it is evident that an b ∈ /L (G) for any n ∈ ω s.t. an is a
pre x. This is so because there is a single in nite derivation
ω
z }| { S |{z} =⇒ aA=⇒l aaAB =⇒l ...=⇒l aω aAB |{z} |{z} |{z} r1
s.t.
r2
r2
r2
r3 is never applied and there is no terminal word an b.
Clearly, no Turing machine M can
n
enumerate this language, let alone enumerate it in canonical order, as for every a
n
it is the case
\ that a b ∈ / L (G), but M halts neither in an accepting nor in a rejecting state. In eect, M has n n no means to determine, for any n ∈ ω , that a is a proper pre x of a b. Thus, L (G) is essentially undecidable.
25
Note with respect to this language that, were
G a Chomsky grammar (of Type 1 or 0), we would
have L (G) = ∅, because rule r2 hinders the derivation of any string w ∈ T
+
.
Theorem 82. Productive languages are outside the Chomsky hierarchy. Proof. (Informal) The set P in a Chomsky grammar G = (V, T, S, P ) is a set of production rules. Whenever there is a rule r ∈ P s.t. r prevents the rightmost or leftmost derivation of a word, then we have L (G) = ∅. If P ⊇ {r} in a grammar G = (V, T, S, P ) s.t. r is a productive rule, then L (G) ̸= ∅, and L (G) is a productive language. A similar theorem can be stated for the ω -languages and the proof is based on the fact that no productive language has a rule of type α → βγδ speci ed in De nition 67 above. The distinction between Chomsky or ω - languages and productive languages falls thus on the productive rules. I next analyze formally these rules.
De nition 83. Let wn be a pre x of a word w = wn+1 . Clearly, wn is a proper pre x of w, and w let us call it the terminal proper pre x of w. For every n, we de ne the function t : N −→ Σ+ s.t. t (n) = wn+1 , i.e. t (n) sends the terminal proper pre x of w to w itself. I shall call t the word terminating function. Clearly, t (n) is total and it is an increasing function. Hence, t is a recursive function even if because wn is only one letter away from
|Dom (t)| = ω . Then, the set L = {w | ∀n ∈ N, t (n) ↓ and t (n) = w} = = {t (0) , t (1) , t (2) , ...} = Range (t)
L is a language, i.e. a word set, we say L is decidable. n o Example 84. Consider the language L = an b ∈ {a, b}n+1 | n ≥ 1 . We have is computable even if its domain is in nite, and because that
t (1) = ab t (2) = aab . . .
t (n) = an b . . . It is easy to see that a Turing machine can enumerate the words of
L in canonical order. We thus
\ have L (M) and L is a decidable language. This language could be generated by a regular grammar, but because we are interested in Turing-decidability let us construct a Type-0 grammar for it. This can be the grammar G = ({S, A, B} , {a, b} , S, P ) with:
(r1 ) S → aAB (r2 ) aA → aaA P = (r3 ) AB → b It is also easy to see that L (G) is also semi-decidable, so the language generated by this grammar is actually decidable.
26
De nition 85. Let us now set Wn = {w ∈ Σn | t (n) = wn+1 }, Wn ⊆ L for a given language L. If we now make
( Wn ⊆ L ⇒
then t (n) is a productive function for
(1) (2)
t (n) t (n) ∈ (L − Wn )
L and L is a productive language.
L. This L is not a pre x-closed language, being thus an undecidable language. In the formalism of productive sets (cf. Section 2.2 above), we have the set Π (L, t), i.e. the productive center of L In eect, Wn is an in nite semi-computable set, but L ̸= Wn for any subset Wn of
means that
relative to the productive function t (n). Then we have
(1) Wn ⊆ L ⇒ (2) (3)
s (n) ↓ Ws(n) ⊆ (L − Wn ) Ws(n) = ω
for a recursive function s (n) s.t. Ws(n) = Wn ∪ {w} by de ning
( φs(n) (w) =
1 ↑
if w ∈ Wn or w = t (n) otherwise
.
We can then apply the results constituted by Proposition 41 through Corollary 46 to a productive language
L.
Consider again the language of Example 84, but now generated by the grammar
G of Example
81 above. It is easy to see that L (G) is undecidable, because w b ⊉ {w} for any word w ∈ L (G) we
\ have it that w ∈ / Wn . But L (G) contains an in nite semi-computable subset: \ L (G) ⊂ {a, aa, aaa, ..., aω } Additionally, L (G) is semi-computable. Thus, ductive language generated by
4
G.
G is a productive grammar and L (G) is the pro-
Conclusions
In the Introduction to this article, I justi ed the study of productive languages by the need to reduce our ignorance with respect to the in nitely large class of undecidable languages. There are in eect in nitely many undecidable languages, and uncountably in nitely many for that matter, a fact that nds its theoretical support in the following results in recursion or computability theory.
Lemma 86. There are exactly countably in nitely many p.r. functions and there are exactly countably in nitely many recursive functions. I now convert this result into the framework of Turing machines:
Theorem 87. Let M be the set of all Turing machines. Then, |M | = |ω|, i.e. there are countably in nitely many Turing machines. Proof. (Informal) There are as many Turing machines as (partial) recursive functions. 27
Let us now denote an uncountable in nity by 2
|ω|
|ω|
and remark that |ω| ≤ 2
ω
from Cantor's theorem, which equates with stating that the power set 2
, a result that follows
of ω is uncountable. Then,
it follows that there are languages that are not Turing-recognizablea result that I have proven above constructively via the productive languages. Formally, we have:
Corollary 88. There are uncountably in nitely many languages that are undecidable. Proof. Let PL denote the class of all productive languages. I have shown above constructively that, alone for PL , we have already |PL | ≥ |ω|.
References
Augusto, L. M. (2020). Logical consequences. Theory and applications: An introduction. 2nd ed. London: College Publications.
Augusto, L. M. (2021). Languages, machines, and classical computation. 3rd ed. London: College Publications.
Augusto, L. M. (forthcoming). Regular languages and their automata. Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics, 58 (2), 345-363. Cooper, S. B. (2004). Computability theory. Boca Raton, etc.: Chapman & Hall/CRC. Cutland, N. J. (1980). Computability. An introduction to recursive function theory. Cambridge, etc.: Cambridge University Press.
Dekker, J. C. E. (1955). Productive sets. Transactions of the American Mathematical Society, 78, 129-149. Hilbert, D. & Ackermann, W. (1928). Grundzüge der theoretischen Logik. Berlin: Springer. Post, E. L. (1944). Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, 50, 284-316. Rogers, H. (1967). Theory of recursive functions and eective computability. New York, etc.: McGraw Hill.
Smullyan, R. M. (1993). Recursion theory for metamathematics. New York & Oxford: Oxford University Press.
Soare, R. I. (1996). Computability and recursion. Bulletin of Symbolic Logic, 2, 284-321. Soare, R. I. (1999). The history and concept of computability. In E. R. Grior (ed.), Handbook of computability theory (pp. 3-36). Amsterdam: North-Holland. Soare, R. I. (2016). Turing computability. Theory and applications. Berlin & Heidelberg: Springer. Staiger, L. (1997). ω-languages. In G. Rozenberg & A. Salomaa (eds.), Handbook of formal languages. Vol. 3: Beyond words (pp. 339-387). Berlin & Heidelberg: Springer. 28
Turing, A. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, 42 (1), 230-265.
29