6
$\begingroup$

I'm working on my graduation project for CS, which is about cellular automata. Recently, i was able to build a system where the input is transferred to multiple different structures at once. The input consists of numbers, a sequence of numbers ranges from (-infnite to infinite), like ('5','65443'or'9921075').

From the sequence of numbers {input}, i can see each number's behavior and how it interacts with other numbers by analysing the different structures it outputs, it is like a Cellular Automaton structure simulates another Cellular Automaton structure.

How can i relate these properties to universality, What should i look for or analyze in these structures to show universality?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ determining arbitrary universality is very, very hard and nearly as hard as the halting problem... try dropping by Computer Science Chat for more discussion $\endgroup$
    – vzn
    Commented Sep 28, 2015 at 15:36
  • 2
    $\begingroup$ The buzzword is simulation. $\endgroup$
    – Raphael
    Commented Sep 28, 2015 at 16:58

2 Answers 2

Reset to default
6
$\begingroup$

In order to show that your computation model is universal, you have to show that you can implement every computable function in your model. You do this by picking some other computation model $M$ and showing how to simulate $M$ in your model. For somewhat more formal definitions, see this answer.

As stated, this sounds difficult, and the first step is to look at various proofs of universality to get some ideas of what is involved. Some examples are listed in the Wikipedia article. It's possible that your model can easily simulate one of the simpler computation models such as counter machines, and this is perhaps the first thing to check.

It is also possible that your model is not Turing-complete but is still quite strong, say PSPACE-complete or EXPTIME-complete.

Improve this answer
$\endgroup$
2
$\begingroup$

Proving arbitrary CAs are universal in some sense is one of the hardest problems in CS/mathematics, and is probably about as hard as the Busy Beaver problem or nearly equivalent to the halting problem. Depending on scope this may be outside the range of an undergraduate research project.

Some sense of this can be understood by looking at Mathew Cooks very ingenious 40 page proof of the universality of rule 110. The rule was conjectured to be universal for many years before the proof was discovered. The proof uses tag systems which are used in other CA-TM equivalence constructions.

Eric Weisstein has a basic survey/collection of references on this Mathworld. Note, that study of this problem goes back decades, eg to Von Neumann. Another famous proof is with the Game of Life by Conway.

Another case study is the Wolfram $25K prize for 2,3 machine universality.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.