HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to prove universality in complex systems?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
systemsproveuniversalityhowcomplex

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#47650, answer score: 6

Revisions (0)

No revisions yet.