1 of 77

6 tiles

April 6th 2022 at Turku University, Finland��Tristan Stérin��Hamilton Institute & Computer Science Department

Maynooth University, Ireland

1

ERC No 772766, SFI 18/ERCS/5746

2 of 77

Personal background

Final year PhD student supervised by Damien Woods
Studying:�

Molecular computing
“Simple” computing systems
Tile assembly
Small Turing machines and busy beaver

2

D. Woods, D. Doty et al., Diverse and robust molecular algorithms using reprogrammable DNA self-assembly, Nature, 2019.

3 of 77

Personal background

Final year PhD student supervised by Damien Woods
Studying:�

Molecular computing
“Simple” computing systems
Tile assembly
Small Turing machines and busy beaver

3

D. Woods, D. Doty et al., Diverse and robust molecular algorithms using reprogrammable DNA self-assembly, Nature, 2019.

4 of 77

Personal background

Final year PhD student supervised by Damien Woods
Studying:�

Molecular computing
“Simple” computing systems
Tile assembly
Small Turing machines and busy beaver

4

D. Woods, D. Doty et al., Diverse and robust molecular algorithms using reprogrammable DNA self-assembly, Nature, 2019.

5 of 77

Personal background

Final year PhD student supervised by Damien Woods
Studying:�

Molecular computing
“Simple” computing systems
Tile assembly
Small Turing machines and busy beaver

5

← help prove that BB(5) = 47,176,870

https://bbchallenge.org

6 of 77

The Collatz process

6

Let’s iterate: 34, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1, 2, 1, 2, 1, ...

7 of 77

The Collatz process

7

Collatz conjecture: All strictly positive integers reach 1 under the action of the Collatz process.

^ Open since at least the 60’

8 of 77

The Collatz process

8

Collatz conjecture: All strictly positive integers reach 1 under the action of the Collatz process.

Two seemingly independent components:

Cyclic Collatz conjecture: the only strictly positive cycle is 2,1,2,1,...
Non-divergence conjecture: No Collatz trajectory on the strictly positive integers diverges.

As of 2020, computer tested up to 2^67

D. Barina. The Journal of Supercomputing, 2020.

9 of 77

The Collatz process

9

Theorem (Conway 1972). Generalised Collatz Maps are Turing-complete.

J.H Conway. Number Theory Conference, 1972.

P. Koiran and C. Moore. TCS, 1999.

One catch: exponential slowdown.

10 of 77

The Collatz process

10

What is the computational power of the Collatz process?

Motivating question:

11 of 77

The Collatz process

11

Some minimalistic computing systems can simulate Turing machines efficiently: rule 110.

M. Cook. Complex Systems, 2004

T. Neary and D. Woods. ICALP, 2006.

What is the computational power of the Collatz process?

Motivating question:

12 of 77

The Collatz process

12

What is the computational power of the Collatz process?

Motivating question:

Let’s study the Collatz process symbolically, for instance in binary.

Approach:

13 of 77

The Collatz process

13

111010

14 of 77

The Collatz process

14

111010

How to perform 3x+1 in base 2?

15 of 77

The Collatz process

15

How to perform 3x+1 in base 2?

16 of 77

The Collatz process

16

How to perform 3x in base 2?

3x = 2x + x

⇔

Adding x to its left shift

⇔

Adding each bit of x to its right neighbour

17 of 77

The Collatz process

17

How to perform 3x in base 2?

3x = 2x + x

⇔

Adding x to its left shift

⇔

Adding each bit of x to its right neighbour

18 of 77

The Collatz process

18

How to perform 3x in base 2?

111010

19 of 77

The Collatz process

19

How to perform 3x in base 2?

111010

1

20 of 77

The Collatz process

20

How to perform 3x in base 2?

111010

1

21 of 77

The Collatz process

21

How to perform 3x in base 2?

111010

11

22 of 77

The Collatz process

22

How to perform 3x in base 2?

111010

11

23 of 77

The Collatz process

23

How to perform 3x in base 2?

111010

111

24 of 77

The Collatz process

24

How to perform 3x in base 2?

111010

111

25 of 77

The Collatz process

25

How to perform 3x in base 2?

111010

0111

26 of 77

The Collatz process

26

How to perform 3x in base 2?

111010

10111

27 of 77

The Collatz process

27

How to perform 3x in base 2?

0111010

10111

28 of 77

The Collatz process

28

How to perform 3x in base 2?

0111010

010111

29 of 77

The Collatz process

29

How to perform 3x in base 2?

00111010

010111

30 of 77

The Collatz process

30

How to perform 3x in base 2?

00111010

1010111

31 of 77

The Collatz process

31

How to perform 3x in base 2?

00111010

1010111

29

87 = 3*29

32 of 77

The Collatz process

32

How to perform 3x in base 2? Run this machine:

00111010

1010111

3x binary

Finite State Transducer

Caption

read : write

3x

29

87

33 of 77

The Collatz process

33

How to perform 3x in base 2? Run this machine:

00111010

1011000

3x+1 binary

Finite State Transducer

Caption

read : write

29

3x + 1

88

34 of 77

The Collatz process

34

How to perform 3x in base 2? Run this machine:

00111011

1011001

3x+2 binary

Finite State Transducer

Caption

read : write

29

89

3x + 2

35 of 77

Small digression on multiplication

35

How to perform C*x in base 2?

Immediate if C = 2^k�

36 of 77

Small digression on multiplication

36

How to perform C*x in base 2?

Immediate if C = 2^k�
If C is not 2^k, the binary representation of C gives you a “convolution filter” to apply to your input while propagating carries

37 of 77

Small digression on multiplication

37

How to perform C*x in base 2?

Immediate if C = 2^k�
If C is not 2^k, the binary representation of C gives you a “convolution filter” to apply to your input while propagating carries.�

For instance 5x = [1,0,1]·[4,2,1] x = 4x + x

⇔

Add each bit of x to 0*first neighbour and 1*second neighbour

⇔

Convolute x with the filter 101 while propagating carries

38 of 77

Small digression on multiplication

38

How to perform C*x in base 2?

Immediate if C = 2^k�
If C is not 2^k, the binary representation of C gives you a “convolution filter” to apply to your input while propagating carries.�
Carries are bounded by: �
Hence state space is finite and there is a FST to compute C*x in base 2 with states

39 of 77

Small digression on multiplication

39

5x minimal binary FST

You can construct and minify these “arithmetic FSTs”�
Swapping read:write to write:read

preserves determinism and gives you division by C�

Similar construction in any base

40 of 77

Back to the Collatz process

40

1010000010

001111000100

001011010100

1000100000

321

241

181

17

-

Each row gives an odd iterate of

-

41 of 77

Small digression on , the 2-adic integers

41

...0000000000000000111010

...000000000000001011000

29

3x + 1

88

The machine can process left-infinite binary words

These are called 2-adic integers,

42 of 77

Small digression on , the 2-adic integers

42

...1010101010101010101010

...000000000000000000000

-1/3

3x + 1

0

The machine can process left-infinite binary words

These are called 2-adic integers,

43 of 77

Small digression on , the 2-adic integers

43

(+,x) is a non countable ring�
Not a field because you can’t represent ½

Can be completed into field of 2-adic numbers which allows for finite number of decimals. E.g: ½ becomes .1�
as for instance �
Since x/2 and 3x+1 are defined in the same way, the Collatz process is naturally defined on

44 of 77

Small digression on , the 2-adic integers

44

Since mod 2, x/2 and 3x+1 are well defined in the 2-adic integers (and are pretty much the same as in N), you can naturally run the Colltaz process on any 2-adic integer.

This includes:�

Any rational with odd denominator, e.g. -178/57
Non-real irrational numbers such as \sqrt(-7)

45 of 77

Small digression on , the 2-adic integers

45

The Collatz conjecture generalises to:

Lagarias’ Periodicity Conjecture: � Every odd-denominator rational reaches a cycle.

J. C. Lagarias. The American Mathematical Monthly, 1985.

For instance, three known strictly negative cycles:

-1, -1, ...

-5, -7, -10, -5, …

-17, -25, -37, -55, -82, -41, -61, -91, -136, -68, -34, -17, ...

�

Hence, the symbolic, base-2 approach to Collatz is fruitful.

46 of 77

Small digression on , the 2-adic integers

46

The Collatz conjecture generalises to:

Lagarias’ Periodicity Conjecture: � Every odd-denominator rational reaches a cycle.

J. C. Lagarias. The American Mathematical Monthly, 1985.

For instance, three known strictly negative cycles:

-1, -1, ...

-5, -7, -10, -5, …

-17, -25, -37, -55, -82, -41, -61, -91, -136, -68, -34, -17, ...

�

Hence, the symbolic, base-2 approach to Collatz is fruitful.

47 of 77

Back to the Collatz process

47

1010000010

001111000100

001011010100

1000100000

321

241

181

17

-

Each row gives an odd iterate of

-

48 of 77

Back to the Collatz process

48

000001010000010

00001111000100

001011010100

1000100000

321

241

181

17

-

49 of 77

Back to the Collatz process

49

000001010000010

00001111000100

001011010100

1000100000

321

241

181

17

-

3x+1 binary

Finite State Transducer

50 of 77

Back to the Collatz process

50

000001010000010

00001111000100

001011010100

1000100000

321

241

181

17

-

3x+1 binary

Finite State Transducer

y = 3x + 1

51 of 77

Back to the Collatz process

51

000001010000010

00001111000100

001011010100

1000100000

321

241

181

17

-

3x+2 binary

Finite State Transducer

y’ = 3(3x + 1) + 2

52 of 77

Back to the Collatz process

52

000001010000010

00001111000100

001011010100

1000100000

321

241

181

17

-

3x+2 binary

Finite State Transducer

y’’ = 3(3(3x + 1) + 2) + 2

53 of 77

Back to the Collatz process

53

000001010000010

00001111000100

001011010100

1000100000

321

241

181

17

-

3x+2 binary

Finite State Transducer

y’’ = 3(3(3x + 1) + 2) + 2

x = 0

54 of 77

Back to the Collatz process

54

000001010000010

00001111000100

001011010100

1000100000

321

241

181

17

-

y’’ = 3(3(3x + 1) + 2) + 2 = 1*3^2 + 2*3 + 2

122 in base 3 is 17

1001 in base 2 is 17

The Collatz process embeds a base 3 -> 2 algorithm (not in AC0)!

Columns simulate the Collatz process simultaneously than rows but in base 3.

T. Stérin and D. Woods. Reachability Problems, 2020.

55 of 77

Back to the Collatz process

55

1010000010

111000100

1010100

00000

321 (base 2)

17�base 3

-

The 9 first Collatz steps of 321

are completely encoded in this triangle.

T^9(321) = 17

56 of 77

Back to the Collatz process

56

000001010000010

00001111000100

001011010100

1000100000

321

241

181

17

-

y’’ = 3(3(3x + 1) + 2) + 2 = 1*3^2 + 2*3 + 2

57 of 77

Back to the Collatz process

57

3x+{0,1,2} in binary and x-{0,1}/2 in ternary are dual

58 of 77

Base 6

58

59 of 77

Base 6

59

0

1

2

3

4

5

5145_6 =

1120102_3 =

10001111001_2 =

1145_10

60 of 77

6 tiles

60

Brought to our attention by Matthew Cook, also studied by other authors.

Base 3

Base 2

61 of 77

6 tiles

61

Brought to our attention by Matthew Cook, also studied by other authors.

Deterministic:

x = 2*west+south

x

62 of 77

6 tiles

62

Brought to our attention by Matthew Cook, also studied by other authors.

Deterministic:

x = 3*north+east

x

63 of 77

6 tiles

63

Brought to our attention by Matthew Cook, also studied by other authors.

Deterministic:

Chinese Remainder Theorem

X is unique solution < 6 of:

X = south % 2

X = east % 3

x

64 of 77

6 tiles

64

Brought to our attention by Matthew Cook, also studied by other authors.

Non det:

West 0, North 0 is ambiguous
West 2, North 1 is ambiguous
West 0, North 1 non feasible
West 2, North 0 non feasible

x

65 of 77

6 tiles

65

66 of 77

6 tiles

66

X = 1502_6 = 398

= 3^4 * north_2 + east_3

= 2^4 * west_3 + south_2

= 3^4 * 4 + 74 = 398

= 2^4 * 24 + 14 = 398

Diag_6 = 3^k * north_2 + east_3 (Euclidean div by 3^k)

= 2^k * west_3 + south_2 (Euclidean div by 2^k)

(east,south) are solving CRT in Z/3^k x Z/2^k → Z/6^k

k = 4 is the size

of the square.

67 of 77

6 tiles

67

Brought to our attention by Matthew Cook, also studied by other authors.

All tiles commute:

Z’ is unique no matter the path used.

z

2z + n

3z + w

3p + e

p

2q + s

q

z’

6z + x

68 of 77

6 tiles

68

000001010000010

00001111000100

001011010100

1000100000

321

241

181

17

-

69 of 77

6 tiles

69

321

17

70 of 77

6 tiles

70

321

17

71 of 77

6 tiles

71

321

17

Magenta encodes 241 = 1_3 1110001_2, the next odd Collatz iterate of 321

72 of 77

Cyclic Collatz conjecture

72

321

17

321 != 17

73 of 77

Cyclic Collatz conjecture

73

321

17

For all non trivial borders, north_2 != west_3

74 of 77

75 of 77

76 of 77

These 6 tiles are Turing complete in a relaxed model

76

T. Stérin, M. Cook, D. Woods, DNA, 2021.

77 of 77

77

Acknowledgement

Damien Woods, Maynooth University, Ireland
Matthew Cook, ETH, Zurich
Jarkko Kari, UTU, Finland
Johan Kopra, UTU, Finland

Our institutions: Maynooth University, the Hamilton Institute & Dpt of Computer Science
Funding agencies: European Research Council, Science Foundation Ireland

ERC No 772766, SFI 18/ERCS/5746