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

/* FuncNode
 * Node used to represent a single piece of a function (term, operator,
 * or constant)
 *
 * Written by: Bryant Lee
 * Date: 10/29/04
 */

#include "FuncNode.h"

#include <iostream>
#include <fstream> //for printing

extern int UINTSIZE;

//No argument constructor
FuncNode::FuncNode() {
  type = 0;
  val = 0;
}

//primary constructor
FuncNode::FuncNode(int iType, int iVal) {
  type = iType;
  val = iVal;
}

//copy constructor
FuncNode::FuncNode(const FuncNode &m) {
  type = m.type;
  val = m.val;
}

//copy assignment
const FuncNode& FuncNode::operator=(const FuncNode &right) {
  type = right.type;
  val = right.val;

  return *this;
}

//deepCopy
FuncNode* FuncNode::deepCopy() {
  return new FuncNode(*this);
}

//If holding a constant, returns the constant
//If holding a term, returns the term value based on
// the array x
int FuncNode::termValue(byte *x, int wLength, int i) {
  int ret = -1, index = 0;

  if(type == 1) { //term
    index = (i + val) % wLength;

    if(index < 0) {
      index += wLength; //adjust for c's negative residuals
    }

    ret = x[index];
  } else if(type == 3) { //constant
    ret = val;
  }

  return ret;
}

//If holding a constant, returns the constant
//If holding a term, returns the term value based on
// the array x
int FuncNode::termValue(unsigned int *x, int wLength, int i) {
  int ret = -1, index = 0;

  if(type == 1) { //term
    index = (i + val) % wLength;

    if(index < 0) {
      index += wLength; //adjust for c's negative residuals
    }

    if(index < UINTSIZE) { //if index < UINTSIZE, avoid divide ops
      ret = (x[0] & (1 << index)) >> index;
    }
    else {
      ret = (x[index/UINTSIZE] & (1 << (index % UINTSIZE)))
	     >> (index % UINTSIZE);
    }
  } else if(type == 3) { //constant
    ret = val;
  }

  return ret;
}

//like above except used by inputs, rather than by actual word
int FuncNode::termValue_by_inputs(byte *itTerms, int numTerms,
				  const map<int,int> &optFindTerm) {
  int ret = -1;

  if(type == 1) { //term
    ret = itTerms[optFindTerm.find(val)->second];
  } else if(type == 3) { //constant
    ret = val;
  }

  return ret;
}


//print
void FuncNode::print(ofstream & fout) {
  if(type == 1) {
    fout << "x[" << val << "]";
  }else if (type == 2){
    if(val == 1) {
      fout << "+";
    } else if(val == 2) {
      fout << "-";
    } else if(val == 3) {
      fout << "*";
    } else if(val == 4) {
      fout << "^";
    }
  } else if(type == 3) {
    fout << val;
  }
}

//relational ops
bool FuncNode::operator==(const FuncNode &right) const{
  return (this == &right);
}

bool FuncNode::operator!=(const FuncNode &right) const{
  return !(operator==(right));
}

bool FuncNode::operator<(const FuncNode &right) const{
  return (this < &right);
}

bool FuncNode::operator>(const FuncNode &right) const{
  return (this > &right);
}

bool FuncNode::operator<=(const FuncNode &right) const{
  return (operator<(right) || operator==(right));
}

bool FuncNode::operator>=(const FuncNode &right) const{
  return (operator>(right) || operator==(right));
}