Dave Computes Slow-To-Terminate Programs

Exponential Time

I'm interested in simple rewrite rules that terminate after a large number of steps. For example:

..., 0 --> ...
..., x --> ..., x - 1, x - 1

Read as: If a sequence of nonnegative integers ends in 0, then remove the 0. Otherwise, remove the last integer x and append x - 1 twice.

Starting from 3, we get:

3
2, 2
2, 1, 1
2, 1, 0, 0
2, 1, 0
2, 1
2, 0, 0
2, 0
2
1, 1
1, 0, 0
1, 0
1
0, 0
0

Starting from n, these rewrite rules will terminate in 2ⁿ - 1 steps, so they require exponential time. But exponential time is just the tip of the iceberg.


Ackermann's Function

Here's a more interesting set of rewrite rules.

..., 0, x --> ..., x + 1
..., x, 0 --> ..., x + 1
..., x, y --> ..., x - 1, x, y - 1

Starting from [2, 2], we get:

2, 2
1, 2, 1
1, 1, 2, 0
1, 1, 3
1, 0, 1, 2
1, 0, 0, 1, 1
1, 0, 0, 0, 1, 0
1, 0, 0, 0, 2
1, 0, 0, 3
1, 0, 4
1, 5
0, 1, 4
0, 0, 1, 3
0, 0, 0, 1, 2
0, 0, 0, 0, 1, 1
0, 0, 0, 0, 0, 1, 0
0, 0, 0, 0, 0, 2
0, 0, 0, 0, 3
0, 0, 0, 4
0, 0, 5
0, 6
7

Starting from [0, 0] requires 2 steps (and results in a value of 1).
Starting from [1, 1] requires 4 steps (and results in a value of 3).
Starting from [2, 2] requires 22 steps (and results in a value of 7).
Starting from [3, 3] requires 1,772 steps (and results in a value of 53).
Starting from [4, 4] does not finish in a reasonable amount of time.

These rules are my version of Ackermann's Function, which is traditionally defined recursively. Altering the base case rules can give us resulting values that are simpler to understand, but they don't substantially change the extraordinary running times.

..., 1, 0 --> ..., 2
..., 2, 0 --> ..., 0
..., x, 0 --> ..., 1

Now, we can summarize the values resulting from each operation as:

0, x = x + 1
1, x = x + 2
2, x = 2x3, x = 2^x4, x = 2^^x5, x = 2^^^x

Thus, 2^^4 = 2^2^2^2 = 2^16.


My Rewrite Rules for Sequences

I started to wondered if other rewriting rules for sequences led to such interesting behavior. I wrote a program to generate and test rewrite rules. Here's what I found.

..., 0, x --> ..., 0
..., x, y --> ..., y, x - 1, y + 1

Here's a sample run of these rules.

2, 2
2, 1, 3
2, 3, 0, 4
2, 3, 0
2, 0, 2, 1
2, 0, 1, 1, 2
2, 0, 1, 2, 0, 3
2, 0, 1, 2, 0
2, 0, 1, 0, 1, 1
2, 0, 1, 0, 1, 0, 2
2, 0, 1, 0, 1, 0
2, 0, 1, 0, 0, 0, 1
2, 0, 1, 0, 0, 0
2, 0, 1, 0, 0
2, 0, 1, 0
2, 0, 0, 0, 1
2, 0, 0, 0
2, 0, 0
2, 0
0, 1, 1
0, 1, 0, 2
0, 1, 0
0, 0, 0, 1
0, 0, 0
0, 0
0

It is fairly easy to show these rules always terminate with a value of 0. Here are the running times for this rule.

[0, 0] terminates in 1 step
[1, 1] terminates in 5 steps
[2, 2] terminates in 25 steps
[3, 3] terminates in 113 steps
[4, 4] terminates in 481 steps
[5, 5] terminates in 1,985 steps
[10, 10] terminates in 2,095,105 steps


If we allow our rules to append on either end of the sequence, we get even more complex behavior. Here's one that behaves more chaotically.

x, y, ... --> x, ...  (if x = 0 or y = 0)
x, y, ... --> ..., y + 1, x - 1, x + 1  (otherwise)

[1, 1] terminates in 307 steps.
[3, 3] terminates in 4,479 steps.
[10, 10] terminates in 189,295 steps.

When run, it appears to be blowing up. But once a 0 gets into the first position, it quickly swallows up the remainder of the sequence.

Starting from [0, 0], the following simple rules take 25 steps to terminate (but isn't particularly interesting for other starting values).

x, 0, ... --> x + 1, ..., x, 0
x, y, ... --> ..., y - 1

Starting from [0, 0], the following more complex rules take a remarkable 7,129 steps to terminate.

0, 0, ... --> 1, ..., 0
0, y, ... --> ..., y
x, 0, ... --> x + 1, ..., 0, x
x, y, ... --> x - 1, y - 1, ...

Busy Beavers

A Busy Beaver program is the program of a given length that terminates after the greatest number of steps. We know that there is no algorithm for generating busy beaver programs (because otherwise it could be used to solve the halting problem).

Nonetheless, I set out to find candidate busy beaver programs--or, at least, short programs that take a long time to terminate. Here are some of my favorites.


Brainf**k

For this esoteric programming language, I assumed that programs begin at the leftmost of an infinite array of cells initialized to zero, that cell values cannot be negative, and that programs crash (instead of ignoring or terminating) upon encountering any error condition. Here's a sample run:

+[->+<]  0, 0

+[->+<]  1, 0

+[->+<]  0, 0

+[->+<]  0, 0

+[->+<]  0, 1

+[->+<]  0, 1

+[->+<]  0, 1

+[->+<]  0, 1

+[->+<]  0, 1

And here are some of my favorite slow-to-terminate programs:

+ (1 steps)
++ (2 steps)
+[-] (5 steps)
++[-] (9 steps)
+++[-] (13 steps)
++++[-] (17 steps)

+++++[-] (21 steps)

++++++[-] (25 steps)

+++++[+--] (31 steps)

++++++[+--] (37 steps)

+++++[[->]<] (46 steps)

>++++[-[>]+<] (66 steps)

>+[>+++[-<]>>] (134 steps)
>+[>++++[-<]>>] (185 steps)
+[->++++++[-<]>] (630 steps)


Fractran

A Fractran program repeatedly multiplies the current value by the first fraction in the program that gives an integer result, until no such multiplication is possible. I assumed that all programs start in the simplest nontrivial state:  2. Thus, the program [1/36, 3/2, 4/3] produces the states:

2 (times 3/2)
3 (times 4/3)
4 (times 3/2)
6 (times 3/2)
9 (times 4/3)
12 (times 3/2)
18 (times 3/2)
27 (times 4/3)
36 (times 1/36)
1

Here are some of my favorite slow-to-terminate Fractran programs:

[1/3, 9/2] (3 steps)
[1/36, 3/2, 4/3] (9 steps)
[1/75, 45/2, 50/3] (12 steps)
[1/216, 4/3, 27/2] (20 steps)
[25/8 , 4/15, 135/2] (23 steps)
[1/42, 21/5, 35/2, 30/7, 14/3] (26 steps)
[154/15, 11/42, 77/2, 3/77, 70/3] (48 steps)
[125/148176, 648/2401, 8/1125, 972405/2] (670 steps)


Lambda Calculus

I'll use Scheme syntax for my Lambda Calculus programs. Here's a sample run:

((lambda (x0) (x0 (x0 x0))) (lambda (x0) x0))
((lambda (x0) x0) ((lambda (x0) x0) (lambda (x0) x0)))
((lambda (x0) x0) (lambda (x0) x0))

(lambda (x0) x0)

And here are some slow-to-terminate programs:

(lambda (x0) x0) [0 steps]
((lambda (x0) x0) (lambda (x0) x0)) [1 step]
((lambda (x0) (x0 x0)) (lambda (x0) x0)) [2 steps]
((lambda (x0) (x0 (x0 x0))) (lambda (x0) x0)) [3 steps]
((lambda (x0) ((x0 (x0 x0)) x0)) (lambda (x0) x0)) [4 steps]
((lambda (x0) (x0 x0)) (lambda (x0) (x0 (x0 (lambda (x1) x1))))) [8 steps]
((lambda (x0) (x0 x0)) (lambda (x0) (x0 (x0 (x0 (lambda (x1) x1)))))) [14 steps]
((lambda (x0) (x0 x0)) (lambda (x0) (x0 (x0 (lambda (x1) (lambda (x2) (x0 x1))))))) [26 steps]
((lambda (x0) (x0 x0)) (lambda (x0) (x0 (lambda (x1) (x1 (x0 (x0 (lambda (x2) x2)))))))) [58 steps]
((lambda (x0) ((x0 x0) x0)) (lambda (x0) (((x0 (lambda (x1) x0)) (lambda (x1) x0)) (lambda (x1) x0)))) [99 steps]

Tag Systems

These 2-tag systems begin in the start state 10. At each step, the matching rule removes the first 2 symbols and appends the given symbols to the end. Here is a sample run of the 2-tag system 0x -> 0, 1x -> 1000. (The matching symbols are underlined, and the appended symbols are shown in boldface.)

10
1000
001000
10000
0001000
010000
00000
0000
000
00
0

Here are some slow-to-terminate 2-tag systems using 2 symbols.

0x -> 0, 1x -> 100 (5 steps)
0x -> 0, 1x -> 1000 (10 steps)
0x -> 0, 1x -> 00100 (13 steps)
0x -> 0, 1x -> 100000 (21 steps)
0x -> 0, 1x -> 0010000 (25 steps)
0x -> 0, 1x -> 00001010 (50 steps)
0x -> 0, 1x -> 0000101010 (118 steps)
0x -> 0, 1x -> 000010101010 (232 steps)

And ones with a halting symbol:

0x -> 100, 1x -> 020 (21 steps)
0x -> 01121, 1x -> 11011 (70 steps)

And some with 3 rules:

0x -> 0, 1x -> 221, 2x -> 001 (779 steps)
0x -> 220, 1x -> 1, 2x -> 110 (779 steps)
0x -> 12, 1x -> 1, 2x -> 01210 (915 steps)
0x -> 0, 1x -> 02, 2x -> 10201 (915 steps)

And these favorite 3-tag systems, which start on the string 100:

0xx -> 0, 1xx -> 11001 (587 steps)
0xx -> 00, 1xx -> 0101100 (1,766 steps)

Thue

These Thue programs start from a single 0, find the first matching rule, and replace the left side of the rule with the right. Here is a sample run of the program 10->, 1->00, 0->111. (The matching symbols are underlined, and the appended symbols are shown in boldface.)

0
111
0011
00001
000000
11100000
110000
1000
00
1110
11
001
0000
111000
1100
10

And here are some slow-to-terminate Thue programs:

[0->, 0->] 1 step

[0->1, 1->] 2 steps

[0->11, 1->] 3 steps

[0->111, 1->] 4 steps

[0->1111, 1->] 5 steps

[0->11111, 1->] 6 steps

[0->1, 111->, 1->00] 8 steps

[10->, 1->00, 0->111] 16 steps

[100->, 1->00, 0->111] 28 steps

[100->, 1->00, 0->1111] 45 steps

[100->, 1->00, 0->11111] 66 steps

[100->, 1->00, 0->111111] 91 steps