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
import sys

3
import itertools

4


5
def get_rule_dict(n: int, width: int):

6
    # Get the list representing the rule num

7
    # Converts n to binary string of length 2^3 and then pulls it back into

8
    # int list

9
    vals = [int(x) for x in '{0:0{k}b}'.format(n, k=2**width)]

10
    

11
    # Create a dictionary mapping the possible length width binary sequences

12
    # to the rule and returns it

13
    return dict((zip(itertools.product([1,0], repeat=width), vals)))

14


15


16
def apply_mapping(line, rules, width):

17
    new_line = []

18
    for i in range(0, len(line) - (width - 1)):

19
        window = tuple(line[i:i+width])

20
        new_line.append(rules[window])

21
    #print(line, new_line)

22
    return tuple(new_line)

23


24
def permuteUnique(nums):

25
        per = permutations(nums)

26
        l = []

27
        for i in per:

28
            if i not in l:

29
                l.append(i)

30
        return l

31


32
# Returns list of binary permutations of length n

33
def get_permutations(n):

34
    p = []

35
    perms = []

36
    for i in range(n):

37
        p.append(0)

38
    perms.append(p)

39
    for i in range(len(p)):

40
        p[i] = 1

41
        ps = permuteUnique(p)

42
        perms = perms + ps

43
    return perms

44


45
    

46
# def main():

47
#     #TODO: add support for getting rule as int from args

48
#     #rule 90

49
#     #rules = {(1, 1, 1): 0, (1, 1, 0): 1, (1, 0, 1): 0, (1, 0, 0): 1, (0, 1, 1):1, (0, 1, 0): 0, (0, 0, 1): 1, (0, 0, 0): 0}

50
#     #rule 110

51
#     rules = {(1, 1, 1): 0, (1, 1, 0): 1, (1, 0, 1): 1, (1, 0, 0): 0, (0, 1, 1):1, (0, 1, 0): 1, (0, 0, 1): 1, (0, 0, 0): 0}

52
    

53
#     d = {}

54
#     freq = {}

55
#     perms = get_permutations(10)

56
#     for i in perms:

57
#         x = apply_mapping(i, rules)

58
#         if x in d:

59
#             d[x] = d[x] + 1

60
#         else:

61
#             d[x] = 1

62
    

63
#     isSurjective = True

64
#     for key,val in d.items():

65
#         if val == 0:

66
#             isSurjective = False

67
#         print(key, val)

68
        

69
#     if isSurjective:

70
#         print("SURJECTIVE")

71
#     else:

72
#         print("NOT SURJECTIVE")

73
def get_random_seq(n):

74
    seq = []

75
    for _ in range(n):

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

77
    return seq

78


79
def main():

80
    seq = get_random_seq(25)

81
    rule_dict = get_rule_dict(30,3)

82
    print("Initial Sequence: {}".format(seq))

83
    for i in range(10):

84
        seq = apply_mapping(seq, rule_dict, 3)

85
        print("Evolution {}: {}".format(i+1, seq))

86


87
if __name__ == "__main__":

88
    main()

89
    

90
    

91
    

92