Reversible AND universal elementary cellular automata

[Giulio Prisco]

TL;DR Summary

Has any of the reversible extensions of the elementary one-dimensional cellular automata described by Wolfram in NKS (e.g. Rule 37R) been shown to be computationally universal (like Rule 110)? If so, please give me links. Otherwise, could this be the case? Or is there a proof that no nR can be universal?

Has any of the reversible extensions of the elementary one-dimensional cellular automata described by Wolfram in NKS (e.g. Rule 37R) been shown to be computationally universal (like Rule 110)? If so, please give me links. Otherwise, could this be the case? Or is there a proof that no nR can be universal?

 

[pbuk]

Interesting question, answers don't seem easy to find. Given that we can easily construct e.g. a NOR gate with a second order (reversible) cellular automaton I would have thought we should be able to construct a UTM. This paywalled paper could be useful: https://link.springer.com/referenceworkentry/10.1007/978-3-540-92910-9_7

 

[Giulio Prisco]

Interesting question, answers don't seem easy to find. Given that we can easily construct e.g. a NOR gate with a second order (reversible) cellular automaton I would have thought we should be able to construct a UTM. This paywalled paper could be useful: https://link.springer.com/referenceworkentry/10.1007/978-3-540-92910-9_7

Thanks, I have that paper.

Wolfram mentions Rule 37R as an example of “cellular automata with class 4 overall behavior” (NKS, Chapter 11). “I strongly suspect that all class 4 rules, like rule 110, will turn out to be universal,” he says.

 

[Giulio Prisco]

The NOR gate is universal, so I would think that if a second-order reversible 1D cellular automata supports NOR gates that can be arbitrarily combined, then it is universal. Or not?

 

[Pythagorean]

The NOR gate is universal, so I would think that if a second-order reversible 1D cellular automata supports NOR gates that can be arbitrarily combined, then it is universal. Or not?

NOR gates are only universal when we fix the topology of the inputs and outputs in particular ways. So what do you mean by arbitrarily combined?

 

[Jarvis323]

Nor gates are logically complete or logically universal, but it's not the same as universal computation (Turing complete). For universal computation you need unbounded memory and a way to traverse/access it in a coherent way.

 

[pbuk]

The NOR gate is universal, so I would think that if a second-order reversible 1D cellular automata supports NOR gates that can be arbitrarily combined, then it is universal.

As I indicated in #2 that is my instinct too (and more valuably it also seems to be Stephen Wolfram's), but instinct is not enough as @Jarvis323 points out.

Just in case anyone is thinking that we could do some impossible things with a reversible computing machine (like "unmultiply" a number to find its factors in polynomial time), note that (i) we can't (which hints at some of the characteristics of a reversible computer) and (ii) reversible computing is widely studied and has origins at least as far back as Charles Bennett's definitive paper Logical Reversibility of Computation from 1973.