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
/*
 * 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;
}