According to our site's definition of a programming language a language needs to be capable of addition of natural numbers and primality testing of natural numbers. Of the elementary cellular automata, some are periodic and others are chaotic. Rule 110, which is in some sense near the border between periodic and chaotic, is known to be Turing complete. Rule 54 is rumoured to be Turing complete but not yet known to be.

I suspect that rule 126 is not Turing complete. I also suspect that it is not capable of addition or primality testing. However, I do not have a proof either way.

How should such a rule be treated? Should a language be assumed valid until it can be proved that it does not meet our requirements? Or should it be assumed invalid until it can be proved that it does meet our requirements?

This question was prompted by an old answer on a recently active challenge. The answer has since been deleted.

  • 2
    \$\begingroup\$ It's not directly an answer to the question, but a related question: where's the interpreter or compiler? That's also a practical requirement for considering something to be a programming language. \$\endgroup\$ – Peter Taylor Oct 11 '16 at 10:45
  • \$\begingroup\$ Yes, how would answers in any Wolfram rule be scored (or written, for that matter)? \$\endgroup\$ – ETHproductions Oct 11 '16 at 20:43
  • \$\begingroup\$ That's a good point. For those rules which do meet our requirements (for example, the Turing complete ones) I guess the language would be "Implementation X of rule 110". Maybe an implementation from PPCG... \$\endgroup\$ – trichoplax Oct 11 '16 at 21:13
  • \$\begingroup\$ I guess the score for golf would be either the number of digits in the binary input, or the number of bytes required to describe that binary number (depending on what the interpreter takes as input). If there's dispute on how a particular interpreter should be scored that would need a separate meta question. \$\endgroup\$ – trichoplax Oct 11 '16 at 21:16

It's invalid until proven valid

If you cannot prove that a language can do addition and primality testing, it's not a programming language by our definition.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .