2
$\begingroup$

I'm working on a research about Elementary Cellular Automata (ECA), and i found a method to build a system that can solve mathematical equations by using a specific cellular automaton structure.

The system is about encoding the equation into numbers and by applying some rules, these numbers are transferred to a Cellular Automaton structure.

For example => x^3-81=0 , after encoding it to numbers, it showed a structure contains 3 triangle, which is the answer of the equation encoded ===> (x^3-81=0) ==> (x^3=81) => (x=3).


So, i have read the article about turing-complete:

a system of data-manipulation rules (such as a cellular automaton) is said to be Turing complete or computationally universal


What i want to say is, the equation was transferred to numbers {data-manipulation rules} and it computed the input (the equation), then showed the answer (output).

Does that makes the system a turing complete ?

I have also tested other equations:

  1. x^2-25=0
  2. x^3-27=0
  3. x^4-16=0

And the system always shows the right answer as triangles.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Hello! At the very least, you need to give a precise definition of what equations you can solve. A single example isn't nearly enough. $\endgroup$
    – David Richerby
    Commented Sep 21, 2015 at 10:21
  • 5
    $\begingroup$ You need to give a precise definition of what equations you can solve. Three examples isn't nearly enough. However, your examples suggest that it can only solve equations of the form $x^a=b$ for constants $a$ and $b$. I don't see any reason why being able to calculate the $a$th root of $b$ would indicate Turing completeness. $\endgroup$
    – David Richerby
    Commented Sep 21, 2015 at 13:48

1 Answer 1

Reset to default
4
$\begingroup$

If you can solve arbitrary equations involving an arbitrary number of unknowns, then you have shown universality, as explained below. So there is a sense in which your broad question "solving mathematical equations means universality" is actually true -- but we have to precisely define what "mathematical equations" mean here. From your actual examples it seems you are not at the final goal of showing universality: it is not sufficient to solve ploynomial equations in a single variable.

If the equations you can solve are so-called Diophantine equations, then your system is universal. That is, polynomials with multiple variables and integer coefficients, and solved with solutions in the natural numbers. According to the solution of Hilbert's tenth problem such equations encode recursively enumerable sets (of natural numbers). The question whether the polynomial can have value $0$ with fixed `input' value of the first variable codes membership of that value in the set we compute. Or as wikipedia states: "Every recursively enumerable set is Diophantine". This seems universal to me.

To see how complicated these polynomials can be, have a look at this Formula based on a system of Diophantine equations for the prime numbers. (This example generates prime numbers, so is slightly different, but can be tweaked.)

The right definition of universality is not always clear. We must encode input and output in a way suitable to the machine at hand (here the cellular automaton) without giving away parts of the solution. I remember some controversy concerning this.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ I would caution that the examples in the question don't suggest that the CA can solve arbitrary Diophantine equations. $\endgroup$
    – David Richerby
    Commented Sep 21, 2015 at 14:50
  • 1
    $\begingroup$ I edited the answer to include David Richerby's caveat. I hope that was OK. One thing: I am having a hard time parsing/understanding the sentence "The question whether..." -- can you rephrase? $\endgroup$
    – D.W. ♦
    Commented Sep 21, 2015 at 15:30
  • $\begingroup$ Thanks for your suggestions. I hope my statements are more understandable now. $\endgroup$
    – Hendrik Jan
    Commented Sep 21, 2015 at 21:11
  • $\begingroup$ I am very curious about this universality concept, could you please provide some reference? I would appreciate some more formal definition. $\endgroup$
    – Marek
    Commented Jul 12, 2016 at 13:31
  • $\begingroup$ universality = Turing completeness, the property of a computational device to perform all computable functions, as defined by the Turing machine or equivalent notions. $\endgroup$
    – Hendrik Jan
    Commented Jul 13, 2016 at 14:11

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.