Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

A (one dimensional) cellular automaton is a function1 F : Σ → Σ with the property that there is a K > 0 such that F (x)i depends only on the 2K + 1 coordinates xi−K , xi−K+1, . . . , xi−1, xi, xi+1, . . . , xi+K . A periodic point of σ is any x such that σ^p (x) = x for some p ∈ N, and a periodic point of F is any x such that F^q (x) = x for some q ∈ N. Given a cellular automaton F, a point x ∈ Σ is jointly periodic if there are p, q ∈ N such that σ^p (x) = F^q (x) = x, that is, it is a periodic point under both functions.

This project aims to explore the nature of one-dimensional Cellular Automata, in the hope of finding the structure of cellular automata through its periodic points.

2034 views
License: MIT
ubuntu2004
Tweet
Share
Share
1
import random

2


3
def process_line(line, window_dict):

4
    new_line = []

5
    for i in range(0, len(line) - 2):

6
        window = tuple(line[i:i+3])

7
        #print(window, window_dict[window])

8
        new_line.append(window_dict[window])

9
    return new_line

10


11
def get_random_seq(n):

12
    seq = []

13
    for _ in range(n):

14
        seq.append(random.randint(0,1))

15
    return seq

16


17
class Tree:

18
    def __init__(self, root):

19
        self.root = root

20
        

21
    

22
class Node:

23
    # Initializes a Node object

24
    def __init__(self, value: int, left, center, right):

25
        self.value = value

26
        self.left = left

27
        self.center = center

28
        self.right = right

29


30
    def __str__(self):

31
        if self is None:

32
            return "*"

33
        

34
        return str(self.value)

35


36
    # Returns a tuple of the node's children

37
    # Order is (left, center, right)

38
    def get_children(self):

39
        return tuple(self.left, self.center, self.right)

40
    

41
    # Returns the value of the node

42
    def get_value(self):

43
        return self.value

44
    

45
    def get_left_child(self):

46
        return self.left

47
    

48
    def get_center_child(self):

49
        return self.center

50
    

51
    def get_right_child(self):

52
        return self.right

53
    

54
def main():

55
    #line = [0,1,1,0,1,0,1]

56
    line = get_random_seq(25)

57
    window_dict = {(0,0,0): 0, (0,0,1): 1, (0,1,0): 1, (0,1,1): 1, (1,0,0):1, (1,0,1): 0, (1,1,0): 0, (1,1,1):0}

58
    

59
    list_of_lines = []

60
    list_of_lines.append(line)

61


62
    count = 0

63
    while len(line) >= 3:

64
        offset = ""

65
        for i in range(0, count):

66
            offset = offset + "   "

67
        out = offset + str(line)

68
        print(out)

69
        line = process_line(line, window_dict)

70
        list_of_lines.append(line)

71
        count = count + 1

72


73


74
    offset = ""

75
    for i in range(0, count):

76
        offset = offset + "   "

77
    out = offset + str(line)

78
    print(out)

79
    

80
    rev_lines = list_of_lines[::-1]

81
#     for i in rev_lines:

82
#         print(i)

83
        

84
    #tree = create_node(list_of_lines[::-1], 0, 0)

85
    #print_tree(tree)

86


87
# Recursively creates the tree structure from base to top

88
# for easier analysis

89
def create_node(lines, level, idx):

90
    if (level == len(lines) - 1):

91
        return Node(lines[level][idx], None, None, None)

92
    return Node(lines[level][idx], create_node(lines, level + 1, idx), create_node(lines, level + 1, idx + 1), create_node(lines, level + 1, idx + 2))

93


94


95


96
        

97
# Prints the tree structure

98
def print_tree(root):

99
    lists = []

100
    lists.append([])

101
    lists[0].append(root.value)

102
    lists.append([])

103
    lists[1].append(str(root.left))

104
    lists[1].append(str(root.center))

105
    lists[1].append(str(root.right))

106
    

107
    #print(root.value)

108
    lists = print_left(root.left, 2, lists)

109
    lists = print_right(root.right, 2, lists)

110
    

111
    for i in lists:

112
        print(i)

113


114
def print_left(node, level, lists):

115
    if node is None:

116
        return lists

117
    

118
    if level >= len(lists):

119
        lists.append([])

120
    lists[level].append(str(node.left))

121
    lists[level].append(str(node.center))

122
    lists[level].append(str(node.right))

123
    

124
    lists = print_left(node.left, level+1, lists)

125
    return print_right(node.right, level+1, lists)

126
    

127
def print_right(node, level, lists):

128
    if node is None:

129
        return lists

130
    

131
    if level >= len(lists):

132
        lists.append([])

133
    

134
    lists[level].append(str(node.center))

135
    lists[level].append(str(node.right))

136
    

137
    return print_right(node.right, level+1, lists)

138


139


140


141


142
if __name__ == "__main__":

143
    main()

144
    

145