CoCalc -- MATH498E Source Code FDENSE.txt

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.

Shared Project -- M498ES23-Cellular-Automata

LEMMA Research Project / MATH498E Source Code FDENSE.txt

²⁰³³ views
License: MIT
ubuntu2004

1
import java.time.Duration;
2
import java.time.Instant;
3
import java.util.*;
4
import java.util.function.Function;
5

6
public class FDense {
7
    private static int N = 2; // Size of the alphabet
8
    private static HashMap<Integer, Integer> Rule= new HashMap<Integer, Integer>();
9

10
   private static HashMap<Integer, Integer> createHashMap(char[] rule, int k) {
11
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
12
        int n = (int) Math.pow(2, k); // Total number of input patterns
13
        
14
        // Iterate over all input patterns and store the output in the HashMap
15
        for (int i = 0; i < n; i++) {
16
        	hashMap.put(i, Integer.parseInt(String.valueOf(rule[i]).trim()));
17
        }
18
        
19
        return hashMap;
20
    }
21
    
22
    private static List<String> generateWords(int length) {
23
        List<String> words = new ArrayList<>();
24
        generateWordsHelper("", length, words);
25
        return words;
26
    }
27

28
    private static void generateWordsHelper(String prefix, int length, List<String> words) {
29
        if (prefix.length() == length) {
30
            words.add(prefix);
31
        } else {
32
            for (int i = 0; i < N; i++) {
33
                generateWordsHelper(prefix + i, length, words);
34
            }
35
        }
36
    }
37
    
38
    public static List<String> applyRule(List<String> words, int span) {
39
        List<String> newWords = new ArrayList<>();
40
        int  key;
41
        for (String word : words) {
42
            StringBuilder newWord = new StringBuilder();
43
            for (int i = 0; i < word.length(); i++) {
44
                String pattern = "";
45
                if(i == word.length() - span + 1) {
46
                	pattern += word.charAt(i);
47
                	pattern += word.charAt(i+1); 
48
                	pattern += word.charAt(i+2);
49
                	pattern += word.charAt(0);
50
                } else if (i == word.length() - span + 2) {
51
                	pattern += word.charAt(i);
52
                	pattern += word.charAt(i+1); 
53
                	pattern += word.charAt(0);
54
                	pattern += word.charAt(1);
55
                } else if (i == word.length() - span + 3) {
56
                	pattern += word.charAt(i);
57
                	pattern += word.charAt(0); 
58
                	pattern += word.charAt(1);
59
                	pattern += word.charAt(2);
60
                } else {
61
                	pattern += word.charAt(i);
62
                	pattern += word.charAt(i+1);
63
                	pattern += word.charAt(i+2);
64
                	pattern += word.charAt(i+3);
65
                }
66
                
67
                // apply the rule to the input pattern and append the result to the new word
68
                key = Integer.parseInt(pattern, 2);
69
                int output = Rule.get(key);
70
                newWord.append(output);
71
            }
72
            newWords.add(newWord.toString());
73
        }
74
        return newWords;
75
    }
76

77
    
78
	public static String applyRule(String word, int span) {
79
		int key;
80
		String newWord = "";
81
		for (int i = 0; i < word.length(); i++) {
82
			String pattern = "";
83
			if (i == word.length() - span + 1) {
84
				pattern += word.charAt(i);
85
				pattern += word.charAt(i + 1);
86
				pattern += word.charAt(i + 2);
87
				pattern += word.charAt(0);
88
			} else if (i == word.length() - span + 2) {
89
				pattern += word.charAt(i);
90
				pattern += word.charAt(i + 1);
91
				pattern += word.charAt(0);
92
				pattern += word.charAt(1);
93
			} else if (i == word.length() - span + 3) {
94
				pattern += word.charAt(i);
95
				pattern += word.charAt(0);
96
				pattern += word.charAt(1);
97
				pattern += word.charAt(2);
98
			} else {
99
				pattern += word.charAt(i);
100
				pattern += word.charAt(i + 1);
101
				pattern += word.charAt(i + 2);
102
				pattern += word.charAt(i + 3);
103
			}
104

105
			// apply the rule to the input pattern and append the result to the new word
106
			key = Integer.parseInt(pattern, 2);
107
			newWord += Rule.get(key);
108
		}
109

110
		return newWord;
111
	}
112
    
113
    public static void main(String[] args) {
114
		int k = 12;
115
		int m = 10;
116
		int span = 4;
117
		
118
		List<String> originalWords = new ArrayList<>();
119
		List<String> wordsWithKperiod = new ArrayList<>();
120
		List<String> allWords = new ArrayList<>();
121
		
122
		originalWords = generateWords(m);
123
		
124
		//System.out.println(originalWords);
125
		
126
		wordsWithKperiod = generateWords(k-m);
127
		
128
		for (int i = 0; i < originalWords.size(); i++) {
129
			for (int j = 0; j < wordsWithKperiod.size(); j++) {
130
				allWords.add(originalWords.get(i) + wordsWithKperiod.get(j));
131
			}
132
		}
133
		
134

135
		/*
136
		for (int i = 0; i < originalWords.size(); i++) {
137
			for (int j = 0; j < wordsWithKperiod.size(); j++) {
138
				String newWord = originalWords.get(i) + wordsWithKperiod.get(j);
139
				newWord += newWord.substring(0, span); // add first k characters to end of string
140
				allWords.add(newWord);
141
			}
142
		}
143
		*/
144
		
145
		//testing
146
		System.out.println(allWords);
147
		
148
		String tabularRule = "0000111101001011";
149
		Rule = createHashMap(tabularRule.toCharArray(), span);
150
		System.out.println(Rule);
151
		
152
		System.out.println(applyRule(allWords, span));
153
		
154
		
155
		for(int z = 0; z < allWords.size(); z++) {
156
			String newWord = applyRule(allWords.get(z), span);
157
			while(!newWord.equals(allWords.get(z))) {
158
				newWord = applyRule(newWord, span);
159
			}
160
			System.out.print("true ");
161
		}
162
		
163
		
164
	}
165
}
166

Product

Resources

Company