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.
License: MIT
ubuntu2004
/*
* Copyright (C) 2004 Bryant Lee
*
* This file is part of FPeriod.
*
* FPeriod is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* FPeriod is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with FPeriod; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
/* String Ops
* Some operations that can be performed on strings
*
* Written by: Bryant Lee
* Date: 10/29/04
*/
#include "StringOps.h"
#include <string>
#include <vector>
extern int UINTSIZE;
/* split
* Split the string on c
*/
void split(const string &str, char c, vector<string> &output) {
int i = 0, last = -1, strlength = str.length();
//Assume output is already empty
for(i = 0; i < strlength; i++) {
if(str[i] == c) {
if(last != -1) {
output.push_back(str.substr(last, i - last));
}
last = -1;
}
else if(last == -1) {
last = i;
}
}
if(last != -1) {
output.push_back(str.substr(last, strlength - last));
}
}
/* trim
* Remove leading and trailing whitespace
*/
void trim(string &str) {
unsigned int i = 0;
while(i < str.length() && str[i] == ' ') {
i++;
}
str.erase(0,i);
i = str.length() - 1;
while(i >= 0 && str[i] == ' ') {
i--;
}
str.erase(i + 1, str.length() - i + 1);
}
/* alphachar
* returns true if c is an upper or lower case letter
*/
bool alphachar(char c) {
return (c >= 65 && c <= 90) || (c >= 97 && c <= 122);
}
/*
* Copy the contents of b into a
*/
void copyWord(byte *a, byte *b, unsigned int length) {
unsigned int i = 0;
for(i = 0; i < length; i++) {
a[i] = b[i];
}
}
/*
* Copy the contents of b into a
*/
void copyUIntArray(unsigned int *a, unsigned int *b, unsigned int length) {
unsigned int i = 0;
for(i = 0; i < length; i++) {
a[i] = b[i];
}
}
/* printArray
* Print an array to screen
*/
void printArray(byte *arr, unsigned int length) {
unsigned int i = 0;
for(i = 0; i < length; i++) {
cout << (int) arr[i];
if(i != length - 1)
cout << ",";
}
cout << "\n";
}
/*
* printUInt
* Print the word
*/
void printUInt(unsigned int word, unsigned int length) {
unsigned int i = 0;
for(i = 0; i < length; i++) {
if(word & (1 << i))
cout << "1";
else
cout << "0";
}
cout << "\n";
}
/*
* printUIntArray
* Print array of Uints
*/
void printUIntArray(unsigned int word[], unsigned int length) {
unsigned int i = 0;
int j;
while(length > 0) {
for(j = 0; j < (UINTSIZE < (int)length ? UINTSIZE : (int)length); j++) {
if(word[i] & (1 << j))
cout << "1";
else
cout << "0";
}
cout << " ";
length -= UINTSIZE;
i++;
}
}
/*
* (used in main.cpp and func.cpp)
* Return true when we iterate past end. Return false otherwise.
*/
bool iterateWord(byte* arr, unsigned int length, unsigned int shiftSize) {
unsigned int i = 0;
bool ret = false;
while(i < length) {
arr[i]++;
if(arr[i] >= shiftSize) {
arr[i] = 0;
i++;
}
else
break;
}
if(i == length)
ret = true;
return ret;
}