Of course "functional complete" is not a sufficient condition for being Turing complete (because a Turing machine is not reduced to its arithmetic-logic unit, which must be functionally complete, but it is a complete automaton with memories).
However, "functional complete" is a necessary condition for being Turing complete.
Most proofs of Turing completeness do not go as low as the Boolean functions, but they suppose the availability of higher level functions that ensure the functional completeness, i.e. incrementing, decrementing and testing if a value is zero (which in real hardware must be implemented by using Boolean functions).
My comment was based on the line that I have quoted from the parent article, which was one of its first lines.
Moreover, a Turing machine with infinite memory has a fundamental difference only in theory, i.e. in the set of problems that can be solved with it, in comparison with a machine having an identical structure, but finite memory.
For practical purposes, the difference between a machine that is identical with a Turing machine, except by having a finite memory, and other simpler machines, like an automaton with one stack or a finite-state automaton, is much more fundamental.
Because an infinite memory is irrealizable, all the proofs that some real system is "Turing complete" are proofs that the system is equivalent with a Turing machine whose infinite memory is replaced by a finite memory, which is actually the only kind of computing machine that can be made.
So in such a context, any discussion about the infinite memory of a Turing machine is pointless.
>There is absolutely no advantage in showing that some system can compute "Rule 110". It is simpler and clearer to show that it can compute AND and XOR, or AND and NOT.
Which is explicitly wrong. You need extra stuff (roughly) equivalent to looping as well as the ability to interact with an unbounded inputs (110 does this by emulating a tag system). Fixed-width boolean circuits implement AND and XOR, but they are not Turing complete.
Showing a system can implement rule 110 is a lot stronger than showing it can implement AND and XOR or AND and NOT. You can even have a system with a single unbounded stack and access to those functions and it still won't be able to implement rule 110 (it will be a pushdown automaton).
That sentence did not contain any reference to Turing machines.
"Rule 110" by itself is just a Boolean function, which, as I have mentioned is completely equivalent with the pair AND + XOR.
By using a suitably initialized memory and an automaton that besides other features that are needed to address the memory (a.k.a. "move the tape", when the memory is modeled as a tape or shift register) is able to compute "Rule 110", it is possible to build the equivalent of a Turing machine.
My point is that using "Rule 110" does not bring any simplification or any other advantage instead of just using the pair AND + XOR. The machine using "Rule 110" and which is equivalent with a Turing machine is completely equivalent with an otherwise identical machine, except that the "Rule 110" function is replaced by the AND + XOR pair. The only effect of "Rule 110" is to make the description of the machine more complicated and more obscure and if that machine were implemented in real hardware or software it would be more inefficient, due to redundant gates or computations.
Even using the equivalent machine with AND + XOR does not bring any advantage instead of the traditional definition of a Turing machine, which uses higher-level functions, whose implementation details are not relevant for proving Turing completeness.
Rule 110 is not a simple boolean function. It's a cellular automata. The boolean function is part of its description but not the whole thing.
For example if you take the standard rule 110, but run it with a different background pattern (for example the one where every cell is by default in state 0) it isn't Turing complete any more.
I suggest you take a look at the proof that 110 is Turing complete (pdf here http://www.complex-systems.com/pdf/15-1-1.pdf). It doesn't just follow from elementary properties of the boolean gates AND and XOR.
To be fair, it's pretty nasty that the Rules are named ambiguously, where a critical part of the "Rule+" of interest is something (the background pattern) in the CA system but outside the Rule system. It's fixable, but still gross, and plays into Wolfram's style of making things seem more profound by hiding the ball.
Of course "functional complete" is not a sufficient condition for being Turing complete (because a Turing machine is not reduced to its arithmetic-logic unit, which must be functionally complete, but it is a complete automaton with memories).
However, "functional complete" is a necessary condition for being Turing complete.
Most proofs of Turing completeness do not go as low as the Boolean functions, but they suppose the availability of higher level functions that ensure the functional completeness, i.e. incrementing, decrementing and testing if a value is zero (which in real hardware must be implemented by using Boolean functions).
My comment was based on the line that I have quoted from the parent article, which was one of its first lines.
Moreover, a Turing machine with infinite memory has a fundamental difference only in theory, i.e. in the set of problems that can be solved with it, in comparison with a machine having an identical structure, but finite memory.
For practical purposes, the difference between a machine that is identical with a Turing machine, except by having a finite memory, and other simpler machines, like an automaton with one stack or a finite-state automaton, is much more fundamental.
Because an infinite memory is irrealizable, all the proofs that some real system is "Turing complete" are proofs that the system is equivalent with a Turing machine whose infinite memory is replaced by a finite memory, which is actually the only kind of computing machine that can be made.
So in such a context, any discussion about the infinite memory of a Turing machine is pointless.