Fewest (distinct) characters for Turing Completeness

Question

Summary:

For any given language, what is the smallest amount of unique characters for your language to be Turing-Complete?

Challenge:

For any language of your choice, find the smallest subset of characters that allows your language to be Turing-Complete. You may reuse your set of characters as many times as you want.

---

Examples:

• JavaScript: +!()[] (http://www.jsfuck.com)

• Brainfuck: +<>[] (assumes a wrapping cell size)

• Python 2: ()+1cehrx (made from scripts like exec(chr(1+1+1)+chr(1)))

Scoring:

This challenge is scored in characters, not bytes. For example, The scores for the examples are 6, 5, and 9.

---

Notes:

• This challenge differentiates from others in the sense that you only your language to be Turing-Complete (not necessarily being able to use every feature of the language.)

• Although you can, please do not post answers without reducing the characters used. Example: Brainfuck with 8 characters (since every other character is a comment by default.)

• You MUST provide at least a brief explanation as to why your subset is Turing-Complete.

Answer 1

Skull, 9 characters

[]{}|:NUM

So Skull is an interesting language. You need NUM to set number mode. This adds to the amount of characters you need as you have to use one at the beginning of your programs. Also I mean that is the entire language except for 3 other characters.

{ x [ y ] } Increment or decrement the specified cell (x) by the specified number (y)
{ x { While the specified cell (x) is not 0...
} } End while
| x | Print out the specified cell (x) to the screen

This is a simple program doing addition (4+2)

:NUM:       // set mode to NUM
{0[+4]}      // set cell 0 to 4
{1[+2]}      // set cell 1 to 2
{0{         // while cell 0 is not 0
  {0[-1]}   // subtract cell 0 by 1
  {1[+1]}   // add 1 to cell 1
}}          // end while
|1|         // print cell 1 (6)

Answer 2

Actually, 4 chars

'u+≡

We construct strings with 'u+, and then we use ≡ to eval them. The Actually ≡ command uses python eval, which was already proven turing complete in the Whispers v1 answer.

If you have a length 1 string and you increment it with u, you get the next char in the Actually codepage. We can make length 1 strings with '. The problem is, we can't create a space. We only have increment. However, at the very end of the actually codepage is a non-breaking space. And Python is fine with the non-breaking space.

Here's the I combinator:

''uu'+uuuuuuuuuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuu+'≡uuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+''u+

Try it online!

Answer 3

Java 5-6, 15 characters

023456789\bdefu

Java 5 and 6 offer the unique possibility to run applications directly within the static initializer block. No static, no main.

class c{static{System.out.println("Hello, World!");}}

The code above will print Hello, World! when called. Ok, after there will be an exception, but we don't care about it. Also, this works in any version from Java 1.0 to 1.6 (= Java 6).

But if we optimize, there are still too many characters.

Java 5 introduced enums. And this helps dramatically reduce the number of different characters because we can get rid of the static keyword.

A simple code like this works in Java 5 and 6:

enum e{e;{System.out.println("Hello, World!");}}

But this challenge requires that Turing complete capabilities are shown. So that code doesn't really do that. The following does:

enum e{e;{int i=0;i++;int t=i;t--;if(t == 0){i--;}for(;;){t++;i++;}}}

This code contains 19 different characters ( ()+-0;=efimnortu{}, space included), but if we escape it as unicode values as Java allows with \uXXXX, such as below

\u0065\u006e\u0075\u006d\u0020\u0065\u007b\u0065\u003b\u007b\u0069\u006e\u0074\u0020\u0069\u003d\u0030\u003b\u0069\u002b\u002b\u003b\u0069\u006e\u0074\u0020\u0074\u003d\u0069\u003b\u0074\u002d\u002d\u003b\u0069\u0066\u0028\u0074\u0020\u003d\u003d\u0020\u0030\u0029\u007b\u0069\u002d\u002d\u003b\u007d\u0066\u006f\u0072\u0028\u003b\u003b\u0029\u007b\u0074\u002b\u002b\u003b\u0069\u002b\u002b\u003b\u007d\u007d\u007d

Then the complete list of source code contains exclusively 15 characters: 023456789\bdefu.

Answer 4

Batch, 25 characters

 !%-/1:=abcdefgilnopstxy

^{(Includes newline and space.)}

With these characters, you can translate brainf*ck (without , and .), which is Turing-complete:

brainf*ck Command | Limited Batch Equivalent
------------------|--------------------------------
initialization    | setlocal enabledelayedexpansion
                  | set/at=1-1
                  | set/al=111--111--11--11--11
                  | set/an=1--1--1
                  | set/an=%n%%t%%t%%t%%t%
------------------|--------------------------------
+                 | if !c%t%!==%l% set/ac%t%=-1
                  | set/ac%t%-=-1
------------------|--------------------------------
-                 | set/ac%t%-=1
                  | if !c%t%!==-1 set/ac%t%=%l%
------------------|--------------------------------
<                 | set/at-=1
                  | if %t%==-1 set/at=%n%
------------------|--------------------------------
>                 | if %t%==%n% set/at=-1
                  | set/at-=-1
------------------|--------------------------------
[                 | :l
                  | if !c%t%! lss 1 goto:e
------------------|--------------------------------
]                 | goto:l
                  | :e

t stores the pointer position, and c_ stores the value of the cell at index _. Labels :l and :e will need to be renamed accordingly for nested brackets.

Answer 5

APL (Dyalog Unicode), 12 characters

{}()1:⋄⊃↓∇⍵,

This answer specifically avoids using ⍎ (execute).

With these characters, it's possible to simulate Bitwise Cyclic Tag:

{1⊃⊃{1⊃⊃1↓⍵:⍵⋄⍵}⍵:∇((1↓1↓⊃⍵),(⊃⊃⍵),⊃1↓(⊃⍵),↓1↓1)({⊃⊃1↓⍵:(⊃1↓⍵),⊃1↓(⊃⍵),↓1↓1⋄⊃1↓⍵}⍵)⋄∇((1↓⊃⍵),⊃⊃⍵)(1↓⊃1↓⍵)}

This function takes one parameter on the right which is a list of length two containing a list representation of the program string and the data string. It halts by throwing an error.

Example with program string of 1 1 0 1 0 0 and data string of 1 0:

{1⊃⊃{1⊃⊃1↓⍵:⍵⋄⍵}⍵:∇((1↓1↓⊃⍵),(⊃⊃⍵),⊃1↓(⊃⍵),↓1↓1)({⊃⊃1↓⍵:(⊃1↓⍵),⊃1↓(⊃⍵),↓1↓1⋄⊃1↓⍵}⍵)⋄∇((1↓⊃⍵),⊃⊃⍵)(1↓⊃1↓⍵)}{(((1)1⍵1⍵(⍵))(1⍵))}(⊃1↓1)

⍬ can be represented with 1↓1 and 0 can be represented with ⊃1↓1.

Answer 6

Ada (GNAT), 29 28 27 distinct characters

It is possible to construct any computer program in GNAT with the following set of characters...

with syem.acn_od;prubg("+1)

...by placing the machine code of the program in an array and representing it as 1+11+111.... This employs a similar technique as this answer.

As an example, the following is a "Hello, World!" program that compiles and runs on AMD64 Linux.

with system.machine_code;procedure main is begin system.machine_code.asm(".byte 111+111+1+1+1+1+1+1+1+1+1+1;.byte 11+1+1;.byte 111+111+11+11+11+1;.byte 111+111+11+11+11+1;.byte 111+111+11+11+11+1;.byte 11+11+11+11+11+11+1+1+1+1+1+1;.byte 11+11+11+11+11+11+11+11+11+1+1;.byte 11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1;.byte 11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1;.byte 111;.byte 11+11+11+11;.byte 11+11+1+1+1+1+1+1+1+1+1+1;.byte 11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1;.byte 111;.byte 111+1+1+1;.byte 11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1;.byte 11+11+11+11+11+11+11+11+11+1;.byte 11+11+11;.byte 11+11+11+11+11+11+11+11+1+1+1+1+1+1;.byte 11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1;.byte 1;.byte 11+11+11+11+11+11+11+11;.byte 11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1;.byte 1;.byte 11+11+11+11+11+11+11+11+1+1+1+1+1+1+1;.byte 11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1;.byte 11+1+1;.byte 11+11+11+11+11+11+11+11+1+1;.byte 11+1+1+1+1;.byte 1+1+1+1+1");end;

Try it online!

C++ (gcc), 16 distinct characters

Any computer program in C++ may be represented with the following distinct characters.

main(){s".t 1+;}

The following is a "Hello, World!" program that compiles and runs on AMD64 Linux.

main(){asm(".int 1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+11+11+11+11;.int 11+1+1;.int 1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1;.int 11+1+1;.int 1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+1+1+1+1;.int 1111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1;.int 1111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+1+1+1+1+1+1+1+1+1;.int 11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1");}

Try it online!

Crystal, 14 distinct characters

Any computer program in Crystal may be represented with the following distinct characters.

asm(".int 1+,)

The following is a "Hello, World!" program that compiles and runs on AMD64 Linux.

asm(".int 1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+11+11+11+11,11+1+1,1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1,11+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+1+1+1+1,1111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1,1111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+1+1+1+1+1+1+1+1+1,11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1")

Try it online!

D, 24 19 18 distinct characters

Any computer program in Dlang can be constructed with the following characters:

const ia=1+;m(){d}

The following is a "Hello, World!" program that compiles and runs on AMD64 Linux.

const a=1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+11+11+11+11;const aa=11+1+1;const aaa=1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1;const aaaa=11+1+1;const aaaaa=1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+1+1+1+1;const aaaaaa=1111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1;const aaaaaaa=1111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+1+1+1+1+1+1+1+1+1;const aaaaaaaa=11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1;int main(){asm{di a;di aa;di aaa;di aaaa;di aaaaa;di aaaaaa;di aaaaaaa;di aaaaaaaa;}}

Try it online!

FreeBASIC, 14 distinct characters

Any computer program in FreeBASIC may be represented with the following distinct characters.

asm
.int 1+;ed

The following is a "Hello, World!" program that runs on AMD64 Linux.

asm
.int 1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+11+11+11+11;.int 11+1+1;.int 1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1;.int 11+1+1;.int 1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+1+1+1+1;.int 1111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1;.int 1111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+1+1+1+1+1+1+1+1+1;.int 11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1;end asm

Try it online!

Nim, 23 21 19 18 distinct characters

Any computer program in Nim may be represented with the following distinct characters.

func ()=
asm".it1+

The following is a "Hello, World!" program that compiles and runs on AMD64 Linux.

func f()=
 asm ".int 1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+11+11+11+11"
 asm ".int 11+1+1"
 asm ".int 1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1"
 asm ".int 11+1+1"
 asm ".int 1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+1+1+1+1"
 asm ".int 1111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1"
 asm ".int 1111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+1+1+1+1+1+1+1+1+1"
 asm ".int 11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1"
f()

Try it online!

Pascal (FPC), 29 28 distinct characters

Any computer program in Free Pascal can be constructed with the following characters:

procedu asmbl;.i"\01234567ng

The following is a "Hello, World!" program that compiles and runs on AMD64 Linux.

procedure a assembler;asm.ascii"\152\001\130\152\015\132\211\307\350\015\000\000\000\110\145\154\154\157\054\040\127\157\162\154\144\041\136\017\005"end;begin a end.

Try it online!

Rust, 26 25 distinct characters

Any computer program in Rust can be constructed with the following characters:

fn mai(){usetd:rch!".1+;}

The following is a "Hello, World!" program that compiles and runs on AMD64 Linux.

fn main(){unsafe{std::arch::asm!(".int 1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+11+11+11+11;.int 11+1+1;.int 1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1;.int 11+1+1;.int 1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+1+1+1+1;.int 1111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1;.int 1111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+1+1+1+1+1+1+1+1+1;.int 11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1")}}

Try it online!

V, 25 22 21 distinct characters

Any computer program in V may be represented with the following distinct characters.

{asm i386.nt0124579,}

The following is a "Hello, World!" program that compiles and runs on AMD64 Linux.

{asm i386{.int 3126329706,13,3898540394,13,1819043144,1461726319,1684828783,84893217}}

Try it online!

Zig, 25 distinct characters

Any computer program in Zig can be constructed with the following characters:

pub fnmai()vod{slte".1+;}

The following is a "Hello, World!" program that compiles and runs on AMD64 Linux.

pub fn main()void{asm volatile(".int 1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+11+11+11+11;.int 11+1+1;.int 1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1;.int 11+1+1;.int 1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+1+1+1+1;.int 1111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1;.int 1111111111+111111111+111111111+111111111+111111111+111111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+1+1+1+1+1+1+1+1+1;.int 11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+111+111+111+111+11+11+11+11+11+11+11+11+11+1+1+1+1+1+1+1+1+1+1");}

Try it online!

Answer 7

SmileBASIC, 9 charcaters

(space)$+=@GOT[]

$ - required for string variables
+ - for concatenating strings
= - assignment
@ - labels and label string literals (@ABC = "@ABC", when used in an expression)
GOT - used for GOTO, variable names, and label names
[] - accessing characters in strings
space - separator

Here is a Bitwise Cyclic Tag interpreter (some spaces replaced with line breaks for readability)

Program is encoded as G=0, O=10, T=11, and the data string uses T and O as 1 and 0.

G$=@<program here>
G$[O]=O$
T$=@<initial data here>
T$[O]=O$

GOTO @G
@TO @OO
G$=G$+G$[O]
G$[O]=O$
@G
GOTO O$+@G[O]+G$[O]+T$[O]
@GO @GT
T$[O]=O$
GOTO @OO
@TT @OT
T$=T$+G$[O]
GOTO @OO

Answer 8

Turing Machine But Way Worse - 4 characters

0 1\n (The \n should be replaced with an actual newline)

States can be represented in binary and everything else uses a 0 or 1.

Spaces separate different parts of a command and newlines separate commands.

Answer 9

Perl 6, 9 characters

~^<>.EVAL

The goal here is to EVALuate arbitrary strings. To do this, we can use the ~^ to bitwise xor strings into other strings, as long as we have enough characters, as well as the <<>> to delimit the actual strings themselves. There's some fiddling in avoiding syntax errors when using <>, but we can generally use the characters .EVAL~^ to produce more characters.

For example, if you wanted to create the string 4*9, you could do:

<<...>>~^<<VEV>>~^<<LAA>>

And to evaluate that, you wrap it in more <<>>s and EVAL it a few times:

say <<<<...>>~^<<VEV>>~^<<LAA>>>>.EVAL.EVAL

Try it online!

Unfortunately, we can't get the full range of ASCII with just xors, so we can use ~& inside the evaluated strings, in the form 'string'~&'string'. This gets us a Turing complete subset of ASCII, but not all of it, so for convenience we can xor it once more to get a full subset.

For reference, a full program will go through 5 EVAL stages before executing:

<<<<........EE............................>>~^<<.E.....EVVE.....E.....................>>~^<<.V.....VLLVEEE..V....E.....E..EEEE..E.>>~^<<EL.....L~~LLVV.ELE.VEL.....L..LLLL.ELE>>~^<<L^.....^^^^~~L.V^L~^L~EE..E~~^~~~~^^~L>>>>
(<< ........EE............................ >>~^<< .E.....EVVE.....E..................... >>~^<< .V.....VLLVEEE..V....E.....E..EEEE..E. >>~^<< EL.....L~~LLVV.ELE.VEL.....L..LLLL.ELE >>~^<< L^.....^^^^~~L.V^L~^L~EE..E~~^~~~~^^~L >>)
'/.....//wm_.=/'~&'wEE..Ew~^wwww^5w'
'..'~^'weW5'
say 1

Here is a full program generator that can handle ASCII characters, and an example Hello World! program.

Answer 10

Keg, 9 characters

~+-*/:{|}

This subset of Keg was shown to compile to Volatile, which was in turn compiled to the Minsky Machine by TuxCrafting. The lack of output commands does not matter because Turing-completeness does not require output capabilities.

Answer 11

APL (Dyalog Unicode), 8 characters

016 ⎕DR⍎

The "create an arbitrary source code and eval it" approach.

While a typical APL source code contains lots of Unicode symbols, all of them have codepoints that fit into two bytes. That means any reasonable APL source code as a string will have data representation 160. Such a string can be generated by applying reinterpret data representation of an array on any type of array, including a Boolean array.

For example, the following code runs the shortest infinite loop ~⍣≡0:

⍎160⎕DR 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0

Try it online!

Having access to all APL features, this character set is definitely Turing-complete.

---

I considered emulating a Minsky machine or other minimalistic Turing-complete languages using tradfns/dfns, but I can't find anything that works within 7 distinct characters.

Answer 12

Pyth, 5 characters

 1Cv+

1C+ can construct any string, and v evaluates a string as Python 3 expression.

A Hello World program in this format can be written as follows:

v+++++++++++++++++++++C+111 1C+++111 1 1 1C++++++++++++++11 11 11 11 11 11 11 11 11 1 1 1 1 1 1C+++++++++11 11 11 11 11 11 11 11 11 11C+++++111 1 1 1 1 1C+++++++++11 11 11 1 1 1 1 1 1 1C+++11 11 11 1C+++++++++++11 11 11 11 11 11 1 1 1 1 1 1C++++++++++11 11 11 11 11 11 11 11 11 1 1C+++++++++++++++++11 11 11 11 11 11 11 11 11 1 1 1 1 1 1 1 1 1C+++++++++++++++++11 11 11 11 11 11 11 11 11 1 1 1 1 1 1 1 1 1C111C+++11 11 11 11C+++++++++++11 11 1 1 1 1 1 1 1 1 1 1C++++++++111 1 1 1 1 1 1 1 1C111C+++111 1 1 1C+++++++++++++++++11 11 11 11 11 11 11 11 11 1 1 1 1 1 1 1 1 1C+++++++++11 11 11 11 11 11 11 11 11 1C++11 11 11C+++11 11 11 1C++++++++++11 11 11 1 1 1 1 1 1 1 1

as seen here.

Answer 13

Lenguage, 1 character

<insert any character here>

Lenguage programs only depend of the length of the program. The length of the program is taken and converted to brainf*** using a formula described here. Since brainf*** is Turing-complete, and all brainf*** programs can be converted to Lenguage, Lenguage is Turing-complete as well. You can choose any one character you like and repeat it the right amount of times to get any brainf*** program possible.

Answer 14

RETURN, 2 characters

()

From esolangs.org:

RETURN is an esoteric programming language made by Ben Russell (the third one by this author so far), which incorporates a new theory, in which all commands are blank functions, that call other blank functions, and the commands are called by the number of functions passed through a function. It is called RETURN because commands are executed depending on the return codes, effectively.

Try it online!

Here are the commands

(numbers means how many function arguments are needed)

1. Add 1
3. Subtract 1
5. Move pointer right
7. Move pointer left
9. Put character (optional)
11. Put number
13. Get character (optional)
15. Get number
17. While nonzero repeat what's in the next group of brackets
19. If nonzero skip next group of brackets
21. While zero repeat what's in the next group of brackets
23. If zero skip next group of brackets
25. Exit with return code 0
27. Exit with return code defined at pointer

Answer 15

Pxem, 5 characters (assumes arbitrary length of filename and arbitrary size of stack are available).

.acvz

How it works

According to this archive of blog, this is how to emulate a CTS:

3.2.2.1. Syntax in EBNF

    Filename = init, main [, omitable ];
    init = dummy, data-string;
    dummy = '01';
    data-string = { data-bit }, end-of-string;
    data-bit = '0', actual-bit;
    actual-bit = '0' | '1';
    end-of-string = '1';
    main = '.z', { command, } exiter, '.a';
    command = empty-checker, actual-command;
    empty-checker = 'c0.z1.z.a.v1.v.c0.z0000.a'; If empty, data string is updated with a '0' string.
    actual-command = '00.a1.z.a0.zv', pushing-data-string-reversed, '.v00.a';
    pushing-data-string-reversed = { actual-bit, '0' };
    exiter = '.c0.z1.z.a.v1.v00.a.c1';
    omitable = '.d.pxe';

But these modification would make it still Turing-complete:

• Omit omitable
• Replace 0 and 1 with a and z respectively

This is thus the code to emulate the program (011, 10, 101) with input "1":

azazz.z.ca.zz.z.a.vz.v.ca.zaaaa.aaa.az.z.aa.zvzazaaa.vaa.a.ca.zz.z.a.vz.v.ca.zaaaa.aaa.az.z.aa.z.vaaza.vaa.a.ca.zz.z.a.vz.v.ca.zaaaa.aaa.az.z.aa.z.vzaaaza.vaa.a.ca.zz.z.a.vz.vaa.a.cz.a

Answer 16

Ada, 32 characters

_()+,.01:;=abcdeghiklmnoprstuvw\n

The minimum base I can find is 26 characters:

procedure p is
g : natural;
begin
while (g = 0) loop
g := g + 1;
end loop;
end;

But that leaves us without unlimited storage. Loading the vector library costs us six more:

with ada.containers.vectors;

procedure c is
package vnat is new ada.containers.vectors (natural, natural);
use vnat;
t : vnat.vector;
v : natural;
begin
set_length (t, 100);
t := update_element(t, 0);
v := element (t, 0);
while (not (v = 10)) loop
v := v + 1;
end loop;
end c;

The standard only demands compilers support 200 character lines, so a newline is required.

Answer 17

Batch, 13, setcal:%/~= and newline

call:INIT%NEGONE%
::inc1
call set/aHERE=~ARR%%%POS%%%%NEGONE%
set/aARR%POS%=~HERE%%%TWO%%FIVE%%SIX%
::incpos
set/aPOS=~POS%NEGONE%
set/aPOS=~POS
::condition
set THINGTODO=echo AAA
call:DOIT%POS%
::decpos
set/aPOS=POS%NEGONE%
::condition
set THINGTODO=echo BBB
call:DOIT%POS%
PAUSE

:DOIT0
%THINGTODO%
:INIT
set/aNEGONE=~ZERO
set/aNEGTWO=%NEGONE%%NEGONE%
set/aONE=~NEGTWO
set/aTWO=2,FIVE=5,SIX=6

Uppercase mean variable name and used unlisted characters for readability. echo is only for debug, :: mean comment

Not sure if other way to loop, but if filename disallowed, it's also possible to use

call set RERUN=%%%ZERO%%%
%RERUN%

Enough to build BF

if(PC==0)instruction1
if(PC==0)PC=jmpaddr1
if(PC==0)rerun
PC--
if(PC==0)instruction2
if(PC==0)PC=jmpaddr2
if(PC==0)rerun
PC--
...

Answer 18

Java (maybe), 13 characters

\u0123456789c

So you know how you can do \uXXXX in Java to replace a character? I think you can replace that with that construct being used to make that construct. It turns out 0123456789abcdefu can all be constructed with only numerals and \u. The \ however requires a c, so that’s why it’s in the program.

---

Maybe you could do 12 by not replacing the slash with a \uXXXX construct. Not sure you would be able to do that, though.

Answer 19

HSPAL, 6 characters

012346

The BF interpreter linked in the esolangs article uses only the digits 0-4, plus 6, for all tokens except number literals and label IDs. It uses at most 116 distinct label IDs [the actual number is probably slightly lower, but I don't feel like counting them right now], which can be reassigned to use only the reduced 6-digit alphabet; and the BF instructions can likewise be reassigned to different code points; therefore all other digits can be excluded from the alphabet while leaving the language turing complete.

Answer 20

Decimal, 7 characters

012345D

These three commands are necessary to be Turing-complete:

• 3 - I/O
• 4 - MATH
• 5 - COND

0, 1 and 2 are used as arguments to the commands. D is like the closing parenthesis for some commands.

How it's Turing-complete:

• 310 reads a character to the stack (3=I/O, 1=from input, 2=to stack)
• The first four arguments to command 4 MATH are +, -, *, / (1, 2, 3, 4). For example, calling 41D takes DSI and DSI-1, pops them, and pushes the result of adding them together.
• Command 5 COND is a conditional. Jumps to the next COND if the DSI value is falsy.

Answer 21

Clojure, 17 bytes

loadstringch -()1

() and space are needed to do anything in Clojure, so that's in. load-string evaluates the given string. For building strings, we don't use +, instead reusing - and using negative numbers instead. Then we can apply char and str to the numbers to form our string.

Answer 22

GolFunc, 3 chars

It's time to show off my new esolang! S, and K are already built in, so we can do it in 3 characters:

.ST

Now we have no I/O, but we can just return a sequence of encoded characters and that is enough for O. Then we can put input inside of our program and we have 3 characters cabapable of I/O, looping, ANYTHING!

Answer 23

Vyxal, 6 characters

ø⟇Ė0›+

ø⟇ gets the \$n^\text{th}\$ character in the code page, Ė executes arbitrary Vyxal code, 0 is just the number 0, › increments a number, and + concatenates strings.

Proof

We base this on the fact that Vyxal is turing complete. You can increment 0 to get any positive number, then get the character with that index in the codepage. Then, you can concatenate it all together and execute the string as if it were Vyxal code.

Answer 24

Chicken, 8 characters

\n cehikn

\n is the line feed.

Proof

First, Chicken itself is Turing-complete, here is a proof.

Second, every Chicken command is made of chicken tokens and spaces, so we need cehikn.

Last, Chicken commands are separated by line feeds, so we need the line feed.

Without one of these 8 characters, the Chicken programs you can write will be none or very restricted, which is obviously not Turing-complete.

Thus, the set of these characters is the smallest set of characters for Turing-completeness in Chicken.

Answer 25

+-), 3 characters

+-)

+-) is Turing-complete because any 3 cell brainfuck program (every cell is an unbounded integer) can be translated to a +-) program. And +-) only uses three characters +-).

Answer 26

JavaScript (ES6), 5 characters

(a)=>

by lambda calculus

See here for another 5c solution without arrow

Answer 27

Binary Lambda Calculus, 2 characters (with specified encoding).

http://www.ioccc.org/2012/tromp/hint.html

The programming "word" size is two bits long. All possible symbols are used. However the program is passed as a string in which only the low bit of each symbol is significant. Therefore the only symbols we need are 0 and 1.