In Fewest (distinct) characters for Turing Completeness, the goal is to find the minimum number of characters which make a language Turing Complete...in other words, allow it to do any computation possible with any other language. In this challenge, we'll be doing somewhat of the opposite, and finding the minimum number of characters, without which Turing Completeness is impossible.
+!() are all that's needed to write any JS program. We could try using just one of these characters,
+, as a solution. However, I can get around this with something like:
eval("1\x2b2"). So, I might add
\ to the list. This would keep going until I find a small list of characters with which it is difficult or impossible to write any program with.
- You must be able to write a valid program without using any characters in your chosen set. It doesn't need to do anything useful, it just can't error (this is to prevent a character set which includes a single character needed in any valid program)
- Actual "Turing Completeness" isn't necessarily required, since languages like C impose things like maximum sizes for pointers which would rule out many languages. I won't set any specific requirements for "how" Turing Complete the threshold is, but be reasonable, and answers which use a clearly Turing Incomplete language or similar tricks should be downvoted
- Like code-golf, competition is purely within a language, not between different ones
How this post works:
This is a sort-of-CnR. Since determining whether a subset of characters is required for TC-ness or not is itself a fun challenge, Robbers will have the task of trying to "crack" submissions by finding a way to achieve TC-ness without the chosen subset of characters (or proving such a task is impossible). Thus, Cops can fall into two categories:
- Cop-cops: Submissions which are specifically designed to have a trick that still allows TC-ness, as a challenge to Robbers
- Sort-of-cops: Submissions which do not have an intended crack, where the possible-TC-ness is either unknown or can be proven (it's recommended to say how certain you are that it's not crackable, to prevent Robbers from wasting their time on a likely impossible sort-of-cop)
Here is an example of each:
This is a known-crackable cop. The solution isn't super hard to find, but I hope you have fun with it!
And a non-cop-cop:
I'm 99% certain this is valid.
And a proven-non-cop-cop:
[all of unicode]
Proof: Kinda obvious
The winner of the cops' challenge, per language, is the smallest subset of characters required for Turing Completeness, which is not cracked within two weeks (at which point it becomes "safe").