7
\$\begingroup\$

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.

\$\endgroup\$
6
  • 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, 2016 at 10:45
  • \$\begingroup\$ Yes, how would answers in any Wolfram rule be scored (or written, for that matter)? \$\endgroup\$
    – ETHproductions
    Oct 11, 2016 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 is on Codidact now
    Oct 11, 2016 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 is on Codidact now
    Oct 11, 2016 at 21:16
  • 2
    \$\begingroup\$ Possible duplicate of Do submissions have to be answered with a programming language? \$\endgroup\$
    – The Fifth Marshal
    Feb 27, 2021 at 21:21
  • \$\begingroup\$ I disagree that the two are "duplicates" per se, but since the answers to the question linked by @pppery make this entire question null and void, I've cast to VTC \$\endgroup\$
    – caird coinheringaahin g Mod
    Feb 27, 2021 at 23:31

1 Answer 1

Reset to default
16
\$\begingroup\$

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.

\$\endgroup\$

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