4
$\begingroup$

I was reading about sierpenski's triangle and i found that it is similar to pascal's Triangle, which can show coefficients in binomial expansion, also rule 90 from ECA.

If Sierpenski's triangle can show coefficients in binomial expansion, and was simulated by other two systems {Pascal's Triangle} and {Rule 90} does that means it is a computationa model ?

What about rule 110, which is proved to be universal, is it a computational model also?

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Could you clarify whether you're asking about what Wikipedia calls a "computational model" (as linked in the question) or about what Wikipedia calls a "model of computation"? These are two very different things. $\endgroup$
    – David Richerby
    Oct 1, 2015 at 12:23
  • 2
    $\begingroup$ Yes david, i am asking about the computational model. $\endgroup$
    – abc
    Oct 1, 2015 at 15:27
  • 2
    $\begingroup$ generally the only effective way to measure this is Turing completeness $\endgroup$
    – vzn
    Oct 1, 2015 at 18:32
  • 1
    $\begingroup$ @vzn In the sense intended by the question, "computational model" refers to a computational simulation of a physical system (e.g., computational fluid dynamics), not to "models of computation" such as Turing machines. I agree that, for "models of computation", Turing completeness is the right concept but it doesn't seem to have anything to do with the unrelated concept of "computational models". $\endgroup$
    – David Richerby
    Oct 2, 2015 at 8:26
  • 1
    $\begingroup$ ok. was thrown off by your own comment. the "model of computation" wikipedia page says nothing about "computational simulation of a physical system"; it mentions TM complete models and weaker models such as DFAs under "abstract machines". actually have an idea for an answer after reviewing all this. $\endgroup$
    – vzn
    Oct 2, 2015 at 15:00

2 Answers 2

Reset to default
5
$\begingroup$

I would not call Sierpenski's triangle a computational model. A computational model should be a system that has a way to compute something. This means there needs to be a way to supply an input, and a way that the system does something with that input to compute something. Sierpenski's triangle is a single thing (a single set), and it is fixed -- there is no way to supply different inputs and get a different output.

For similar reasons, I would not call Pascal's triangle a computational model.

However, I would call rule 90 a computational model. There are standard ways of providing an input and computing stuff (e.g., the input bitstring is interpreted as a row, and then successive rows are derived using the cellular automaton rules, which is interpreted as a computation). Similarly, I would call rule 110 a computational model. Or, more generally, I might call cellular automata a computational model, and rule 90 and rule 110 as two instances of cellular automata.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ So, if i said i was able to simulate rule 90 and rule 110 by a specific cellular automaton model and that model can compute the input, i can say that it is a computational model? $\endgroup$
    – abc
    Oct 1, 2015 at 10:20
  • 2
    $\begingroup$ It's unclear exactly what the question is asking about. Your answer addresses whether Sierpinski's triangle is what Wikipedia would call "a model of computation": a thing such as a Turing machine. The question, though, links to the Wikipedia page "Computational model", which talks about something completely different. In that sense, e.g., a "computational model" is a computer simulation of a real-world system, which one might use to investigate that system (e.g., crowd dynamics) $\endgroup$
    – David Richerby
    Oct 1, 2015 at 12:27
  • 1
    $\begingroup$ @DavidRicherby No, i just mentioned the computational model , model of computation is surely a different thing. Thanks for the note $\endgroup$
    – abc
    Oct 1, 2015 at 15:30
1
$\begingroup$

DW's answer does not point this out specifically (maybe hes aware of this) but to expand on it somewhat, CA rule 90 can produce a Sierpinski triangle with a simple single black dot input. see here. the same rule 90 leads to other complex patterns.

so reviewing the wikipedia definition of computational model (not to be confused with models of computation!):

A computational model is a mathematical model in computational science that requires extensive computational resources to study the behavior of a complex system by computer simulation.[citation needed] The system under study is often a complex nonlinear system for which simple, intuitive analytical solutions are not readily available. Rather than deriving a mathematical analytical solution to the problem, experimentation with the model is done by adjusting the parameters of the system in the computer, and studying the differences in the outcome of the experiments. Operation theories of the model can be derived/deduced from these computational experiments.

cellular automata clearly classically fit these criteria although they are not mentioned specifically on the wikipedia page. and the Sierpinski triangle may be created from some of the simple CA rules and inputs. the Sierpinski triangle is an example of emergent behavior of a computational model where that particular output is one "outcome of experiments of experimentation with the model by adjusting parameters of the system". note as a somewhat related angle that Sierpinski triangles have been found naturally in seashells and other basic processes eg:

so in short a Sierpinski triangle may be one of the basic signs of the presence of some kind of "computational model".

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ it seems clear now thanks man. very soon, i will publish a research about ECA and other structures with chaotic behavior, how to build these structures from just a signle input ... i am sure you will be interested in it, so keep an eye on the chat. $\endgroup$
    – abc
    Oct 3, 2015 at 19:03

Your Answer

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

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