Smallest subset of characters required for Turing Completeness

Question

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.

Example:

In JavaScript, it is well known that the characters +!()[] 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 ", ', and \ 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.

Rules:

• 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:

1. Cop-cops: Submissions which are specifically designed to have a trick that still allows TC-ness, as a challenge to Robbers
2. 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:

Cop-cop: JavaScript, 4 characters

+"'\

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:

Sort-of-cop: JavaScript, 6 characters

+S("'\

I'm 99% certain this is valid.

And a proven-non-cop-cop:

Sort-of-cop: JavaScript, 1114112 characters

[all of unicode]

Proof: Kinda obvious

Scoring:

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").

Robbers post: Robbers: Smallest subset of characters required for Turing Completeness

Chat room: https://chat.stackexchange.com/rooms/136437/smallest-subset-of-characters-required-for-turing-completeness

Answer 1

Cop-cop: R, 3 bytes, cracked by Cong Chen

(=<

Try it online!

I imagine this won't take long for one of the R afficionados to crack...
But, as a bonus, it looks like a grumpy face. (=<

Answer 2

Sort-of cop, Common Lisp, one character

(

I am almost certain that no Turing Complete CL program can be written without an open paren: the language can easily be extended/modified such that, in the extended language, one can, but I don't think you can bootstrap such an extension without (.

Programs can still be written, such as 1 or nil.

This is characters, not octets in a file.

Answer 3

Sort-of-cop: Desmos, 1 character

=

Took out variable/function declaration, which is essential in doing anything useful in Desmos. Would love to be proved wrong though. I have a more restrictive version if this happens to be cracked.

Answer 4

Round 2!

Actual Cop: Python, 4 characters, cracked

:[ef

CPython 3.10.2 on Linux. This blocks all control flow and obvious workarounds.

No file encoding workarounds, please. (If you want, I can invent a language called Pythom which doesn't have the encoding syntax feature. Hopefully, though, this is a clear enough rule.)

Answer 5

Sort-of-cop: Ada, 5 bytes

:wWlL

Ada is case insensitive, so letters count twice. : prevents defining constants, variables or arguments to functions, wW prevents "with"ing any packages that might have variables, and lL prevents any sort of loop variables. (There's still a goto statement, but without variables it's not enough.)

Answer 6

Cop-cop, Haskell, 22 characters, cracked by ais523

({$                 　`

Although this is more restrictive than my original maybe-cop, forbidding block comments and all non-line-break Unicode whitespace (that hyphen-looking one is U+1680 OGHAM SPACE MARK), I have worked through the possible crack I initially foresaw.

ais's crack is a bit simpler than what I initially had in mind, but it works on the same principle of using lists for everything, and I realized something like it would work just about the moment I finished writing this possibly faulty Bitwise Cyclic Tag interpreter:

[]#_=[]
dataString#program|[[head]<*>[program]]==["0"],[programTail]<-[tail]<*>[program],[dataTail]<-[tail]<*>[dataString]=dataTail:dataTail#programTail
dataString#program|[[head]<*>[dataString]]==["1"],[programTail]<-[tail]<*>[program],programNext<-[head]<*>[programTail],newData<-dataString++programNext=newData:newData#programTail
dataString#program|[programTail]<-[tail]<*>[program]=dataString#programTail
main=do[input]<-sequence[getLine];[[[dataString,program]]]<-pure[[read]<*>[input]];[[cycledProgram]]<-pure[[cycle]<*>[program]];print[dataString#cycledProgram]

Try it online!

Answer 7

Actual Cop: Python, 3 characters, cracked

:ef

CPython 3.10.2 on Linux. This blocks all control flow and obvious workarounds.

No file encoding workarounds, please. (If you want, I can invent a language called Pythom which doesn't have the encoding syntax feature. Hopefully, though, this is a clear enough rule.)

Answer 8

Maybe-cop, Haskell, 4 characters, cracked by pxeger

($ `

Defining functions is possible, but writing a program is challenging. Nevertheless, this doesn't feel airtight, as only the most straightforward infix opportunities are closed off.

Answer 9

Sort-of-cop: Headass, 1 byte; cracked by m90

E

E allows you to access stored variables other than the four main registers, access other code blocks, and also halt the program on a dime by trying to reach out of bounds with it (though you can still halt without it)

I'm not sure whether it is TC without it, because you can still loop / enter and exit loops with {}:;), but I feel like the lang may be too constrained to allow you to do enough. Just a gut feeling not sure.

Sort-of-cop: Headass, 1 byte

}

On the opposite side of the coin, without matching loop brackets, there's no looping within each code block. This means you aren't able to loop through input or all of your stored variables, which makes me 90% sure that it isn't TC, since you can't store arbitrarily many variables. Looping is still possible with E, but the main registers are cleared. Additionally, variables have no upper limit, but encoding/decoding data would be hard probably.

Not a cop: Headass, 2 bytes

E}

If all else fails, remove all loops :)

Answer 10

almost-certainly-not-cop, tinylisp, 1 character, cracked by ais523

i

Without i in tinylisp, you cannot perform if statements, load the library, or construct a string from codepoints (which would give you access to i through evaling code), which prevents any control flow from being possible.

Answer 11

Cop-cop: Applesoft BASIC, 1 byte

=

Prevents variable assignment, should be pretty easy to figure out.

Answer 12

Sort-of-cop: C (tcc), 6, 5 4 bytes (cracked by ais523)

{(?%

-1 byte thanks to @RadvylfPrograms

-2 byte thanks to @EngineerGaming

To the best of my knowledge, C is not Turing complete with these restrictions. No control flow, as if, while, for, switch, function calls, etc. are ruled out by this subset. I am merely somewhat sure of this answer. There is probably a crack; I just do not know it. The { character is in this subset as there are hacky machine-code tricks that can be used to create a function definition without using (, but there are none that I know of that are do not use { or (.

The ? and % are to prevent (tri|di)graph tricks.

Answer 13

Almost certainly not a cop - Vyxal, 15 bytes, cracked by me

{(ƛ⁽‡≬λ@∆Ė†E'µøÞ

This was a pain.

†E provide access to python. 'ƛµ allow iterating over infinite lists. {( are loops. @⁽‡≬λ stop the definition of functions. ∆ deals with a certain ACE vulnerability that hasn't been patched yet. ø deals with øV which is replace until no change. And of course Ė (eval as vyxal) is necessary so there are no workarounds.

Just to be on the safe side, I'm banning Þ, the delimiter for list digraphs which can be infinite.

I'm pretty sure this blocks all infinite loops.

Answer 14

Sort-of-cop: Brainfuck, 1 byte

[

Well, brainfuck needs this character to loop. This answer is quite boring.

Answer 15

Sort-of-cop: Brainflak, 1 byte

{

In effect, a translation of my Brainfuck answer. Without it, there is no looping.

Answer 16

Sort-of-cop: Charcoal, 3 characters

ＦＵＷ

Ｆ and Ｗ prevent indefinite loops while Ｕ prevents access to Python.

Answer 17

Sort-of-cop: Retina 0.8.2, 1 character

`

Without this character you can't configure a stage, which means you can't add an indefinite loop.

Answer 18

Sort-of-cop: PARI/GP, 1 character

(

You can't call a function without (, which includes control flow functions like if, while, for. The only remaining control flow is list comprehension, but it can only loop over a list, whose size is known and finite. So every program terminates.

Answer 19

Cop-cop: Batch, 2 characters, cracked

iI

Without these to form if (case-insensitive), you can't use conditional looping.

This was originally a sort-of-cop but ended up becoming a cop-cop. For a sort-of-cop, %! should work to prevent accessing variables.

Answer 20

Sort-of-cop: Python, 2 bytes

(

Probably impossible, no spaces and parentheses completely breaks Python, not even allowing imports.

Answer 21

Sort-of-cop: Nim, 1 byte (cracked by the default)

:

Nim needs : to do to any control flow. Thus, as best I can tell, this is a valid if uninteresting answer to this question. I would love to be proven wrong.

Answer 22

Sort-of-cop: Racket, 2 bytes

([

To the best of my knowledge, this prevents Racket from being Turing complete by preventing the creation of any control flow, any function declaration, any arithmetic, etc. I might be wrong, as I am quite inexperienced with Racket.

Answer 23

Sort-of-cop: BitCycle, 3 characters

~+=

I just took out all ways (I think) to do infinite looping and conditionals. Might be proved wrong by someone more experienced in BitCycle than me.

Answer 24

Sort-of-cop: LOLCODE, 1 byte (cracked by ais523)

S

This prevents variable declaration, i.e. "I HAS VAR".

Answer 25

Sort-of-cop: Headass, 4 bytes

^+-]

Posting this even though it's longer because it uses a different approach; Now you only have access to values 1 and 0 :P (and input i guess but that doesnt count)

I think this is possible but I can't confirm it

For fun, while I'm here,

Sort-of-cop: Headass, 10 bytes

DR^+-[]<>(

I have no idea if this is possible. It'd be a computational model I am unfamiliar with. My main idea is something to do with using how many values are on the array somehow. You can technically still use value 0 but it might be tricky, since the only char that explicitly gives 0 here is ), which is used for control flow/conditionals, so that might get messy.

Answer 26

Sort-of-cop: C#, 3 characters

.=;

No .Equals() for you!

Answers cracked by the default:

Sort-of-cop, 1 byte

;

Sort-of-cop

=

No variables and no conditionals.

There are a lot of these in C#.

Answer 27

Cop-cop: Elixir, 2 characters

d-

Without these characters you cannot create any function… maybe.

Answer 28

Sort-of-cop: C#, 1 byte

(

No calling main or other methods, functions, if or loops. Maybe this doesn't count, but you can still write library code.

using System;

namespace Code;

public class A {
    
    public string Greeting { get; set; } = "Hello ";
    
    public Func<string,string> GreetPerson =>  name => Test + name;
    
    public Func<int,int> Square => a => a*a;
}

Answer 29

Sort-of-cop: Knight, 3 characters

E=`

Takes out EVAL, variable assignment, and ` (run shell command). Taking out variables should prevent Knight from being Turing complete. E is there to prevent the EVAL and ASCII strategy for running any Knight code (which would allow variable assignment), and ` is there to prevent running Shell, which is Turing complete.

Answer 30

Probably-a-Cop: Go, 1 byte

(

Functions can be anonymous in Go, but they must use a pair of parens to declare and call them. This prevents declaring main() as an entry point into a full program, as well as declaring/calling any new functions since Go doesn't have special lambda syntax.