4 ms·

As far as I can tell from your comment you have the terms "functional complete" and "Turing complete" confused. These are emphatically not the same thing. A ci

As far as I can tell from your comment you have the terms "functional complete" and "Turing complete" confused. These are emphatically not the same thing. A circuit of (e.g.) NAND gates defines a mathematical function over a fixed, finite number of variables (the number of input wires to your circuit) and with a fixed number of outputs (likewise the output wires). A Turing complete computer accepts inputs which are unbounded in length, I.e. it accepts an input of at least length n for any natural number n. It can also output unbounded strings. These two are fundamentally completely different. Functional completeness for a set of gates doesn't tell you much about Turing completeness. For all of the interesting stuff to do with Turing machines you need this unbounded input size so you can do things like consider descriptions of other Turing machines as inputs to your Turing machine. Essentially what you need is something equivalent to looping or recursion. Note that the Halting problem is completely trivial for NAND circuits, exactly because there is no looping.

adrian_b 2y ago
Perhaps you have not read TFA. 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.
- eigenket 2y ago
  Specifically I was responding to this >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).
  - adrian_b 2y ago
    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.
    - eigenket 2y ago
      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 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.

adrian_b 2y ago

Perhaps you have not read TFA. 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.

eigenket 2y ago
Specifically I was responding to this >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).
- adrian_b 2y ago
  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.
  - eigenket 2y ago
    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 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.