26
\$\begingroup\$

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 , 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

\$\endgroup\$
1
  • \$\begingroup\$ Sort-of-cop: HQ9+, 0 bytes \$\endgroup\$
    – Ohentis
    May 19 at 18:28

28 Answers 28

7
\$\begingroup\$

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. (=<

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Does this address it? codegolf.stackexchange.com/a/247593/98085 \$\endgroup\$
    – Cong Chen
    May 20 at 13:27
  • 1
    \$\begingroup\$ I feel like the emoticon this makes is less of a grumpy face, and more of either a mischievous scheming face (with the ( as the mouth), or a very mopey sad face (with the < as the mouth) \$\endgroup\$
    – des54321
    May 24 at 18:02
6
\$\begingroup\$

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.

\$\endgroup\$
3
6
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$
    – Steffan
    May 22 at 22:16
4
\$\begingroup\$

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

\$\endgroup\$
1
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
1
3
\$\begingroup\$

Almost certainly not a cop - Vyxal, 15 bytes

{(ƛ⁽‡≬λ@∆Ė†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.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
1
3
\$\begingroup\$

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

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Four registers and some way to loop might be enough to achieve Turing Completeness, but I'm sure not going go try :p \$\endgroup\$ May 22 at 18:43
  • \$\begingroup\$ @RadvylfPrograms Wait, I think I've got something. Going to test my idea rigorously (read: a lot) and might turn one into a cop-cop. \$\endgroup\$ May 24 at 13:33
  • 2
    \$\begingroup\$ Your E one's been cracked, I guess they didn't bother commenting \$\endgroup\$ May 24 at 13:34
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Aand I can't do lambda calculus because lexical scoping :| \$\endgroup\$
    – emanresu A
    May 20 at 7:43
  • \$\begingroup\$ Cracked by ais523 \$\endgroup\$
    – emanresu A
    May 24 at 9:40
3
\$\begingroup\$

Cop-cop: Applesoft BASIC, 1 byte

=

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

\$\endgroup\$
2
  • \$\begingroup\$ Could you link to a speciifcation and/or implementation that supports your intended crack? The only emulator I could find seems to restrict memory addresses and values to 16 bits, so although storage is possible with POKE/PEEK, it isn't unbounded--and I have no idea if that's a quirk of the environment trying to stay faithful to the Apple 2 or a limit of the "ideal" language itself! \$\endgroup\$ May 26 at 7:19
  • 1
    \$\begingroup\$ I believe that peek/poke works just like the C machine code injection here works. \$\endgroup\$
    – Ohentis
    May 27 at 4:45
3
\$\begingroup\$

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.

\$\endgroup\$
13
  • 2
    \$\begingroup\$ You can use the ??= trigraph for #, although without define you might be able to just do away with it completely. \$\endgroup\$ May 19 at 20:29
  • 2
    \$\begingroup\$ Another trigraph-- ??< for {. There's also a digraph (<%) for {. \$\endgroup\$ May 19 at 23:35
  • 1
    \$\begingroup\$ char x; isn't a program. It is a valid translation unit, but without a main function, it cannot be built or executed. (And to be language-lawyery, C17 5.1.2.2.1: "It [the main function] shall be defined with a return type of int and with no parameters [...] or with two parameters [...]". So I really don't think you can avoid having { and ( or their trigraph equivalents. \$\endgroup\$ May 20 at 5:13
  • 1
    \$\begingroup\$ tcc accepts int main; as an program (builds it and everything). I should have specified that it only works for a specific implementation (as languages are defined by implementation on PPCG.) Fixed now. Sorry for the trouble! \$\endgroup\$ May 20 at 6:10
  • 1
    \$\begingroup\$ @Pyautogui: Your TIO link builds, but not "and everything" - it then crashes when you try to run it, on a non-executable .bss section, or on the 00 00 bytes decoding as add [rax], al. The question says "It doesn't need to do anything useful, it just can't error - The way I read that, that includes running, not just compiling. The only way to even have a runnable program is probably something like the crack used, __attribute__((section(".text"))) const char main[] = "0xc3"; (To get the main label attached to the machine code for an x86 ret instruction) \$\endgroup\$ May 23 at 2:51
2
\$\begingroup\$

Sort-of-cop: Brainflak, 1 byte

{

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

\$\endgroup\$
2
\$\begingroup\$

Sort-of-cop: Charcoal, 3 characters

FUW

and prevent indefinite loops while prevents access to Python.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Cracked \$\endgroup\$
    – pxeger
    May 20 at 11:12
2
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ cracked \$\endgroup\$
    – des54321
    May 20 at 21:16
  • \$\begingroup\$ another non-cop answer might be iI:, as you need : to make a goto label, and being able to goto arbitrary labels isn't useful if you cant make labels \$\endgroup\$
    – des54321
    May 20 at 23:17
  • \$\begingroup\$ @des54321 Even without labels I think you could still be TC through clever use of for to execute a statement conditionally and call %0 to recursively invoke the entire script. \$\endgroup\$
    – Neil
    May 21 at 7:03
  • \$\begingroup\$ youre right @Neil, I was thinking something similar, that variables let you still get control flow from calling other scripts \$\endgroup\$
    – des54321
    May 21 at 19:37
2
\$\begingroup\$

Sort-of-cop: Python, 2 bytes

(

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

\$\endgroup\$
1
  • 5
    \$\begingroup\$ Cracked \$\endgroup\$
    – benrg
    May 21 at 18:38
2
\$\begingroup\$

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.

\$\endgroup\$
1
1
\$\begingroup\$

Sort-of-cop: Brainfuck, 1 byte

[

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can you write a valid program with this? \$\endgroup\$
    – emanresu A
    May 19 at 21:53
  • \$\begingroup\$ Sure. As I understand it, 1 is a valid Racket program. It returns 1. It need not do anything, according to the challenge rules, IIRC. I might be wrong. If so, I am happy to delete this answer. \$\endgroup\$ May 19 at 22:44
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ I'm pretty you dont actually need the dupneg in there, because without being able to tell the difference between a 1 and a 0 with either + or =, you cant make any kind of conditional. There might even be a case that could be made for taking out +, as I dont think theres any way to emulate that behavior with `+/` \$\endgroup\$
    – des54321
    May 20 at 4:27
  • \$\begingroup\$ @des54321 So you saying that I can take out ~ and + and leave it as =? \$\endgroup\$
    – Aiden Chow
    May 20 at 7:27
  • \$\begingroup\$ I'm not 100% sure about +, but I am pretty sure that ~ doesnt allow you to do much in the way of conditionals. It might be possible to make something really janky with + that lets you simulate the behavior of = though \$\endgroup\$
    – des54321
    May 20 at 17:07
  • \$\begingroup\$ My guess is that there might be a way to be Turing-complete without + and =, but ~ is crucial since it's the only way to add bits to the playfield. IIRC, infinite growth of data is a necessary condition for Turing-completeness. \$\endgroup\$
    – DLosc
    May 24 at 17:18
1
\$\begingroup\$

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

S

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

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Am I missing something, but isn't variable declaration I HAS A <name> ITZ <something>? \$\endgroup\$
    – emanresu A
    May 21 at 10:16
  • \$\begingroup\$ Oh, yes. I have hardly used LOLCODE and misread the docs. Quite foolish of me, I apologize. \$\endgroup\$ May 21 at 17:01
  • 1
    \$\begingroup\$ Cracked by ais523 \$\endgroup\$
    – emanresu A
    May 24 at 19:37
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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#.

\$\endgroup\$
2
1
\$\begingroup\$

Cop-cop: Elixir, 2 characters

d-

Without these characters you cannot create any function… maybe.

\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! Is it possible to write any valid program in C# without using (? (the challenge requires that it is possible to write something valid without using the subset you specify) \$\endgroup\$
    – pxeger
    Jun 2 at 8:55
  • \$\begingroup\$ Thank you! Well, I might have misunderstood the meaning of "valid program". Does it have to run? I just created som library code, which compiles and could be used by other running code. \$\endgroup\$
    – AndersJH
    Jun 3 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.