Generation and analysis of lamplighter programs
Carlos Martin

arXiv:1707.02652v1 [cs.DM] 9 Jul 2017

Abstract
We consider a programming language based on the lamplighter group that uses only composition and iteration as control structures. We derive generating functions and counting formulas
for this language with the goal of avoiding repetition of equivalent programs.

1

Introduction

The structured program theorem states that every computable function can be implemented in a
programming language that uses only composition and iteration as control structures [1][2]. In this
paper, we consider a programming language that manipulates an infinite sequence of bits with the
following instructions:
t
r
l
[E]

toggle current bit
move right
move left
repeat E while current bit is 1

We can combine these primitive instructions to create more complex ones. For example, [t] sets
the current bit to 0, [t]t sets it to 1, and []t[] loops forever. t[tEt]t repeats E while the current bit is
0, inverting the loop condition. The state of the current bit is preserved because either t preceding
a check for the loop condition is immediately cancelled by a subsequent t.
We can swap two bits without additional memory using the xor swap algorithm:
[rn tln ]
| {z }

xn := xn ⊕ x0

rn [ln trn ]ln
| {z }

x0 := x0 ⊕ xn

[rn tln ]
| {z }

xn := xn ⊕ x0

A more complex instruction is [tr[r]r[r]trt[l]l[l]r], which doubles a string of 1s using two buffers
as described below. The loop stops when the left buffer has been exhausted.
t
r[r]r[r]
trt
[l]l[l]r

remove 1 tally mark from left buffer
move to right buffer
add 2 tally marks to right buffer
move to left buffer

The programming language is generated by the grammar
E = (t + r + l + [E])∗

1

Therefore, its generating function is the solution to
E(z) = (z + z + z + z 2 E(z))∗
1
=
1 − (3z + z 2 E(z))
which is
E(z) =

1 − 3z +

2
p
(1 − z)(1 − 5z)

= 1 + 3z + 10z 2 + 36z 3 + 137z 4 + 543z 5 + . . .
where the nth coefficient, denoted by [z n ]E(z), is the number of expressions of length n. Since
E(z) has branch points at z = 1 and z = 51 , its radius of convergence is 15 . Therefore [4]
lim ([z n ]E(z))1/n = 5

n→∞

Suppose
−β
A(z) + B(z) 1 − zr
f (z) =
zα
where r is the radius of convergence of f , the radius of convergence of A and B is greater than
r, and B(r) 6= 0. Then an asymptotic expression for [z n ]f (z) is given by [4]
[z n ]f (z) ∼

B(r)
rα Γ(β)

nβ−1 r−n

For E(z) we have r = 15 , α = 2, β = − 21 , and
1 − 3z
2
(1 − z)1/2
B(z) = −
2
A(z) =

Thus an asymptotic expression for [z n ]E(z) is [6]
5n+3/2
[z n ]E(z) ∼ √
2 πn3
Notice that the instructions t, r, and l generate a group under composition. This group is called
the lamplighter group, and is described in the next section.

2

The lamplighter group

The lamplighter group is the restricted wreath product
L = (Z/2Z) o Z = (Z/2Z)⊕Z o Z

2

with presentation
ht, r | tn , [t, rk tr−k ] for k ≥ 1i
where r−1 = l. The group can be viewed as the action of a lamplighter on an infinite sequence
of lamps. t toggles the lamp above the lamplighter, r moves the lamplighter right, and l moves the
lamplighter left. Each group element is an ordered pair (a, b) where a ∈ (Z/2Z)⊕Z ∼
= Pfinite (Z) and
b ∈ Z. The group operation is
(a1 , b1 )(a2 , b2 ) = (a1 + σ b1 a2 , b1 + b2 )
and the group inverse is
(a, b)−1 = (−σ −b a, −b)
where σ is the shift operator, defined by (σa)(i) = a(i + 1). For example,
↓

. . .  . . .
represents the element (δ−2 + δ1 , 3). The arrow points to the origin, the black squares indicate
toggled lamps, and the underscore indicates the final position of the lamplighter. The group identity
is (0, 0) and the group generators are
t = (δ0 , 0)
r = (0, 1)
l = (0, −1)

2.1

Word norm

A word is a representation of a group element as a product of group generators. The word norm of
a group element is the length of the shortest word that represents it. For instance, the norm of the
group identity is zero, since it can be expressed as the empty product. The norm of a lamplighter
group element (a, b) under the generating set {t, r, l} is [3]
(
|a↓ | + |a↑ − b| b ≥ 0
|(a, b)| = kak1 + a↑ − a↓ +
|a↑ | + |a↓ − b| otherwise
where k·k1 is the 1-norm and
(

0
a=0
(min ◦ supp)(a) otherwise

(

0
a=0
(max ◦ supp)(a) otherwise

a↓ =
a↑ =

This can be seen by dividing the movement of the lamplighter into three stages, as shown in the
following diagram:

3

a↓

0

a↑

b

The shortest word for a lamplighter group element is a solution to the traveling salesman problem
in one dimension, where the vertices are the locations of the toggled lamps. If b ≥ 0, the lamplighter
visits the leftmost toggled lamp, the rightmost toggled lamp, and b in that order. Similarly, if b < 0,
the lamplighter visits the rightmost toggled lamp, the leftmost toggled lamp, and b in that order.
The set of all lamplighter group elements with b ≥ 0 is given by
(li (g − 1)r(gr)i−1 )[i>0]
|
{z
}
stage 1

g(rg)j
| {z }

(rk (g − 1)l(gl)k−1 )[k>0]
|
{z
}

stage 2

stage 3

for all i, j, k ∈ N, where g = ε + t and [·] is the Iverson bracket (in this context). Similarly, the
set of all elements with b < 0 is given by the expression above with l and r switching places. Notice
that this representation of each lamplighter group element is of minimal length.
The word distance between two group elements is the smallest number of generators needed to
change one into the other. For a symmetric generating set, it can be expressed as
d(g, h) = |g −1 h|
Notice we also have the inequality
|ab| ≤ |a| + |b|

2.2

Growth function

The growth function G(z) of a group G is a formal power series whose nth coefficient is the number
of group elements with a norm of n. For example,
(Z/nZ)(z) =

X

zk =

k∈[0,n)

1 − zn
1−z

with respect to the singleton generating set, and
Z(z) =

X

z |k| =

k∈Z

4

1+z
1−z

with respect to the standard generators {1, −1}. The growth function of G o Z can be expressed
in terms of the growth function of G as follows [5]:
(G o Z)(z) = (1 + z 2 (G(z) − 1)(z 2 G(z))∗ )2 G(z)Z(zG(z))
2

1 + zG(z)
1 − z2
G(z)
=
2
1 − z G(z)
1 − zG(z)

Letting G = Z/2Z yields

L(z) =

1 − z2
1 − z2 − z3

2
(1 + z)

1 + z + z2
1 − z − z2

which has a radius of convergence of ϕ−1 , where ϕ is the golden ratio:
√
1+ 5
ϕ=
= 1.6180 . . .
2
Hence
lim ([z n ]L(z))1/n = ϕ

n→∞

Since
A(z) + B(z) 1 −
L(z) =
zα
−1
where r = ϕ , α = 0, β = 1, and


z −β
r

A(z) = 0
B(z) =

ϕ(1 − z)2 (1 + z)3 (1 + z + z 2 )
(ϕ + z)(1 − z 2 − z 3 )2

The lamplighter group grows asymptotically as
√
15 + 7 5 n
[z ]L(z) ∼
ϕ
5
n

2.3

Lamplighter programs

Recall the grammar that generates our programming language:
E = (G + [E])∗
where G = t + r + l are our generators. Since (a + b)∗ = a∗ (ba∗ )∗ , we have
E = (G + [E])∗
= G ∗ ([E]G ∗ )∗
To avoid counting equivalent generator sequences, we would like to represent each lamplighter
group element with its shortest word. Hence we replace G ∗ with L:
E = L([E]L)∗
5

Thus the new generating function is given by
E(z) = L(z)(zE(z)zL(z))∗
=

L(z)
1−

z 2 E(z)L(z)

1+

p

Solving for E(z) yields
E(z) =

2L(z)
1 − 4z 2 L(z)2

Its radius of convergence is the smallest root of the polynomial
−1 + 3z + 7z 2 − 11z 4 − 9z 5 + 2z 6 + 7z 7 + 3z 8
which is approximately 0.2256. Hence
lim ([z n ]E(z))1/n ≈ 4.432

n→∞

which is smaller than the exponential growth rate of 5 we had previously. Note that [z n ]E(z) ≥
[z ]L(z), since there must be at least one program for every lamplighter group element. Therefore,
the exponential growth rate of E will always be bounded below by ϕ ≈ 1.618.
n

2.4

k-shift subsets

Consider the subset of G o Z containing all elements with a shift of k:
(G o Z)k = G⊕Z × {k}
The growth function of this subset is

(G o Z)k (z) =

1 − z2
1 − z 2 G(z)

2

G(z)(zG(z))|k|

Notice that (G o Z)0 ∼
= G⊕Z is a normal subgroup of G o Z:
(a1 , b1 )(a2 , 0)(a1 , b1 )−1 = (a1 + σ b1 a2 , b1 )(a1 , b1 )−1
= (a1 + σ b1 a2 , b1 )(−σ −b1 a1 , −b1 )
= (a1 + σ b1 a2 − σ b1 σ −b1 a1 , b1 − b1 )
= (a1 + σ b1 a2 − a1 , 0)
= (σ b1 a2 , 0)
In the lamplighter group, we have

Lk (z) =

1 − z2
1 − z2 − z3

2

(1 + z)(z + z 2 )|k|

The radius of convergence of this function is ρ−1 , where ρ is the plastic number:
p
p
√
√
3
3
108 + 12 69 + 108 − 12 69
ρ=
= 1.3247 . . .
6
6

Thus ρ is the exponential growth rate of Lk . Finally, let Lk,1 and Lk,0 denote the set of k-shift
elements which do and do not, respectively, toggle the final bit:

Lk,0 (z) =

1 − z2
1 − z2 − z3

2

(z + z 2 )|k|

Lk,1 (z) = Lk,0 (z)z

3

Dead loops

3.1

After a loop

In this section, we show that certain loops are never entered and can be eliminated from a program
without changing its behavior. For example, the current bit is always 0 immediately after any loop.
Hence we can eliminate the second of two consecutive loops:
[a][b] = [a]
More generally, let b ∈ L0,0 be a 0-shift element that does not toggle the central bit. Then
b ∈ L0,0 =⇒ [a]b[c] = [a]b
Since [a]b[c] is equivalent to a shorter program (which will be generated earlier in the generation
process), we can exclude it. Hence, we exclude all expressions of the form [E]L0,0 [E] by taking
E = L([E]L)∗
= L(ε + ([E]L)∗ [E]L)
= L + L([E]L)∗ [E]L
and remove all Ls between loops that are in L0,0 :
E = L + L([E](L − L0,0 ))∗ [E]L
Therefore
E(z) = L(z) + L(z)(z 2 E(z)(L(z) − L0,0 (z)))∗ z 2 E(z)L(z)
= L(z) +

z 2 E(z)L(z)2
1 − z 2 E(z)(L(z) − L0,0 (z))

which yields
E(z) =

1 − z 2 L(z)L0,0 (z) +

2L(z)
p
(1 − 2xL(z) + z 2 L(z)L0,0 (z))(1 + 2xL(z) + z 2 L(z)L0,0 (z))

The radius of convergence of this function is approximately 0.2409. Hence
lim ([z n ]E(z))1/n ≈ 4.150

n→∞

7

3.2

Inside a loop

Let a ∈ L0,1 be a 0-shift lamplighter group element that toggles the central bit. Then
a ∈ L0,1 =⇒ [a[b]c] = [ac]
since the current bit is always 1 at the beginning of a loop body. Thus we exclude all expressions
of the form [L0,1 [E]E] by creating a new nonterminal symbol Y for loops:
E = L + L(Y (L − L0,0 ))∗ Y L
Y = [E]
Expanding the expression inside the loop:
E = L + L(Y (L − L0,0 ))∗ Y L
Y = [L + L(Y (L − L0,0 ))∗ Y L]
and replacing the inner L with L − L0,1 :
E = L + L(Y (L − L0,0 ))∗ Y L
Y = [L + (L − L0,1 )(Y (L − L0,0 ))∗ Y L]
Hence
L(z)2 Y (z)
E(z) = L(z) +
1 − Y (z)(L(z) − L0,0 (z))


L(z)Y (z)(L(z) − L0,1 (z))
2
Y (z) = z L(z) +
1 − Y (z)(L(z) − L0,0 (z))
The radius of convergence of E(z) when solved is approximately 0.244303. Hence
lim ([z n ]E(z))1/n ≈ 4.093

n→∞

The following graph illustrates the growth sequences we have derived so far:

8

4

Loop unrolling

We can turn a doubly-nested loop into a singly-nested loop:
[[a]] = [a]
This is because the inner loop is entered whenever the outer loop is entered, and the outer loop
ends whenever the inner loop ends. Thus we exclude expressions of the form [[E]] = [Y ]:
E = L + L(Y (L − L0,0 ))∗ Y L
Y = [L + (L − L0,1 )(Y (L − L0,0 ))∗ Y L − Y ]
In general, we can unroll the first iteration of a loop when we know that the loop will be executed
at least once. By inverting the loop elimination conditions from the previous section, we obtain the
following loop unrolling conditions:
b ∈ L0,1 =⇒ [a]b[c] = [a]bc[c]
a ∈ L0,0 =⇒ [a[b]c] = [ab[b]c]
This might seem to only make programs longer. However, if we know that the loop can only be
executed at most once, we can eliminate the rest of the loop and thus inline the loop body:
[a]b[c] = [a]bc[c] = [a]bc
[a[b]c] = [ab[b]c] = [abc]

9

A loop that is executed at most once is called a transient loop. This occurs when the current
bit is always 0 at the end of the loop body, preventing another iteration. For example,
a ∈ L0,1 =⇒ [a] is transient
c ∈ L0,0 =⇒ [a[b]c] is transient
Hence we have the following reductions:
b ∈ L0,1 , c ∈ L0,1 =⇒ [a]b[c] = [a]bc[c] = [a]bc
b ∈ L0,1 , e ∈ L0,0 =⇒ [a]b[c[d]e] = [a]bc[d]e[c[d]e] = [a]bc[d]e
a ∈ L0,0 , b ∈ L0,1 =⇒ [a[b]c] = [ab[b]c] = [abc]
a ∈ L0,0 , d ∈ L0,0 =⇒ [a[b[c]d]e] = [ab[c]d[b[c]d]e] = [ab[c]de]
noting that L0,a L0,b = L0,a+b mod 2 . Since they are provably equivalent to smaller expressions,
we can exclude expressions of the following forms from the generation process:
Transient type 1
Transient type 2

5

After a loop
[E]L0,1 [L0,1 ]
[E]L0,1 [E[E]L0,0 ]

Inside a loop
[L0,0 [L0,1 ]E]
[L0,0 [E[E]L0,0 ]E]

Infinite loops

Because the halting problem is undecidable, no algorithm can determine whether a program terminates, for all possible programs. Nonetheless, we can prove that certain programs will (or will not)
terminate. This is the goal of termination analysis.
For example, if a loop body consists of a 0-shift lamplighter group element that does not toggle
the central bit, the loop will never terminate if entered. This is because the current bit, which is 1
at the beginning of the body, will remain 1 at the end of it. Since the loop condition is always true
at the end of the loop body, the loop cannot be escaped.
a ∈ L0,0 =⇒ [a] is an infinite loop
Similarly, suppose there is a 0-shift toggling element that follows an inner loop at the end of a
loop body. Either the inner loop does not terminate, which a fortiori results in an infinite loop, or
it terminates when the current bit becomes 0. The current bit is toggled from 0 to 1 as the end of
the loop is reached, resulting in an infinite loop:
c ∈ L0,1 =⇒ [a[b]c] is an infinite loop
Since they are extensionally equivalent, we can exclude all expressions of the previous two forms
from the generation process except for the smallest infinite loop, namely the empty loop [].
Suppose we use ⊥ denote a point in a program which, if reached, guarantees non-termination.
Any instructions before ⊥ are absorbed by it since either they do not terminate, which results in
⊥, or they do terminate, allowing ⊥ to be reached. Similarly, any instructions after ⊥ do not affect
the non-termination outcome, and are also absorbed by it:
a⊥b = ⊥
10

From the previous examples of infinite loops, we have
a ∈ L0,0 =⇒[a] = [⊥]
c ∈ L0,1 =⇒[a[b]c] = [⊥]
Finally, from the loop unrolling conditions of the previous section we have
a ∈ L0,0 =⇒[a[⊥]b] = [⊥]
b ∈ L0,1 =⇒[a]b[⊥] = ⊥
These rules allow us to propagate the detection of non-termination through a program.

6

Fixed-shift programs

Let Ei be defined as follows:
Ei = Li +

X

Lj [E0 ]Ei−j

j∈Z

Ei is a set of programs which always shift by i bits. Each element of Ei is equivalent to a partial
function (Z/2Z)B → (Z/2Z)B
⊥ where B ∈ Pfinite (Z) is the finite set of bits that are read or toggled,
which can be determined statically.
A machine configuration consists of its current memory, given by the infinite bit sequence, and a
program counter indicating which instruction is being executed. The set of configurations assumed
by a machine executing an expression in Ei is finite, since B is finite. Therefore, it is easy to detect
non-termination by detecting whether the machine configuration repeats.
For any set of bits B and any partial function over those bits (Z/2Z)B → (Z/2Z)B
⊥ , we can find
the shortest representative program and exclude all longer, equivalent programs.
(k)
(k)
Let Li be the subset of Li that does not toggle bit k. Then we can define Ei as a subset of
Ei that never toggles bit k:
X (k) (k−j) (k−j)
(k)
(k)
Ei = Li +
Lj [E0
]Ei−j
j∈Z

This allows us to extend some of our previous results. For example, we have
(0)

b ∈ E0
(0)

since E0

=⇒ [a]b[c] = [a]b

returns to the same bit without ever toggling it. Thus, for example,
n 6= 0 =⇒ [a]rn [t]ln [b] = [a]rn [t]ln
(0)

In general, we can replace the role of L0,0 with E0 .

7

Conclusion

We have constructed a programming language based on P00 that manipulates an infinite sequence of
bits using function composition and iteration. We derived combinatorial formulas for this language
11

and for subsets of it that collapse certain classes of equivalent programs. Our analysis of equivalent
programs included dead loops, nested loops, loop unrolling, and infinite loops.
This analysis can be applied to program search. The goal of program search is to search efficiently
through the space of possible programs and find one which satisfies a desired specification or inputoutput behavior. This can be used for automatic program synthesis.
We hope that this combinatorial analysis will be extended to more complex classes of equivalent
programs, yielding further reductions in the search space. In particular, we would like to find tighter
upper and lower bounds on limn→∞ ([z n ]E(z))1/n for the set E of non-equivalent programs.

References
[1] Corrado Böhm. On a family of Turing machines and the related programming language. International Computation Centre Bulletin, 3:185–194, July 1964.
[2] Corrado Böhm and Giuseppe Jacopini. Flow diagrams, Turing machines and languages with
only two formation rules. Communications of the ACM, 9(5):366–371, 1966.
[3] Sean Cleary and Jennifer Taback. Dead end words in lamplighter groups and other wreath
products. The Quarterly Journal of Mathematics, 56(2):165–178, 2005.
[4] Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press,
Princeton NJ, 2009. Chapter 4.
[5] Walter Parry. Growth series of some wreath products. Transactions of the American Mathematical Society, 331(2):751–759, 1992.
[6] Neil Sloane. The encyclopedia of integer sequences. Sequence A002212.

12

