Desmos, 12 characters

\f_(){}-=:^,

To preface my explanation, I am including characters that you need in order to paste a valid equation into Desmos, so I include things like \ to that curly brackets work, and _ in order to write subscripts.

The characters f, _, {, }, and = allow for infinite variables, since you can have a variable f_{fff} = whatever, and just increase the number of f's in the curly brackets to make a different variable. \ also allows Desmos to accept the existence of piecewise functions, and : allows us to test boolean expression, which is helpful for creating valid base cases for a recursive function. Speaking of functions, ( and ) let us take in a parameter for a function, and , allows us to take in multiple. An empty \{\} evaluates to 1, and being able to make 1, along with the ^, and - operator lets us create all other real numbers. Addition like f+f_{f} mimicked by f{}--f_{f}, and division is simply a^{-\{\}}b, which is essentially the same as a^{-1} * b, or in other words, b/a.

Here is a link to some things I made in this very strange version of Desmos.

Python (+ PyPi), 7 characters: import

This one is a bit controversial, but let me explain.

Python allows you to upload packages to PyPi, which can be installed with pip install and then used in code.

To pull this off, you write whatever code in another Python file, making sure there is no main guard in the code. When uploading it, name the module using only the letters import (e.g. poirtoim).

Then, install the package, and in the actual file with the main code, write this, replacing the module name with whatever your module name is:

import poirtoim

And your Turing-complete code is run!

C (unportable), 24 18 13 characters

+,1;=aimn[]{}

This covers all programs of the form

main[]={<sequence of constants>};

...where the sequence of constants (of the form 1...+1...+1...) contains the machine code representation of your program. This assumes that your environment permits all memory segments to be executed (apparently true for tcc [thanks @Dennis!] and some machines without NX bit). Otherwise, for Linux and OSX you may have to prepend the keyword const and for Windows you may have to add a #pragma explicitly marking the segment as executable.

As an example, the following program written in the above style prints Hello, World! on Linux and OSX on x86 and x86_64.

main[]={11111111111111+1111111111111+111111111111+111111111111+111111111111+111111111111+111111111111+11111+1111+1111+1111+1111+1111+111+111+1,1111111111111111+1111111111111111+11111111111+1111111111+11111111+11111111+111111+1111+111+111+11+11+1+1+1+1,111111111111111+11111111111+1111111111+1111111111+1111111111+1111111+1111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+11+11+1,111111111111111111+11111111111111111+111111111111+111111111111+111111111+111111+111111+111111+111111+1111+111+11+11+11+11+11+11+11+11+11+1+1+1+1,11111111111111111+111111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111+1111+1111+11+11+11+1+1+1+1,111111111111111111+11111111111111+1111111111111+1111111111111+111111111111+111111111111+11111111111+111111+111111+111111+111111+1111+11+11+11+1+1+1+1+1,11111111111111+1111111111+1111111111+1111111111+1111111111+111111111+1111111+1111111+111111+111111+111111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+11+1+1+1,111111111111+111111111111+11111111111+11111111111+11111111111+11111111111+1111111111+1111111+1111111+1111111+11111+11111+11111+111+11+11,111111111111111+11111111111111+1111111111+111111111+111111111+111111111+1111111+111111+111111+11111+11111+11111+11111+11111+1111+1,1111111111111+1111111111111+1111111111+111111111+11111111+111111+111111+111111+111111+111111+111111+111111+11111+111+111+111+11+11+11+11+11+1+1,111111111111111111+11111111111111+11111111111+11111111111+1111111111+1111111111+1111111111+111111111+11111111+1111111+111111+111111+1111+1111+1+1,1111111111111111+111111111111+11111111111+11111111111+11111111+111111+111111+111111+111111+111111+1111+1111+1111+1111+1111+111+111+111+111+111+111+11+11+11+11+1+1+1+1,111111111111111111+11111111111111111+1111111111111111+11111111111+111111111+11111111+1111111+1111111+111111+11111+1111+111+111+111+11+1+1+1+1+1+1+1+1+1,11111111111111111+11111111111111111+11111111111111111+11111111111111+1111111111111+11111111111+11111111111+1111111+1111+1111+1111+1111+1111+1111+1+1+1+1+1,111111111111111111+111111111111+11111111111+111111111+111111+1111+1111+1111+11+11+11+1+1+1+1+1+1+1+1+1,11111111111+11111111111+11111111111+1111111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+111+111+1+1,1111111111111111+1111111111111111+11111111111111+1111111111111+111111111+111111111+11111111+1111111+111111+11111+11111+11111+11111+111+111+11+11+11,11111111111111111+11111111111111111+1111111111111+111111111+111111111+11111111+111111+111111+111111+111111+111111+111111+11111+111+111+111+11+11+11+11+11+1,111111111+11111+11111+111+1};

Try it online!

C (gcc) (unportable), 24 18 13 8 characters

+1;=aimn

It is possible to build any program using fewer than 13 distinct characters by abusing the linker and laying out the machine code in such a way that it spans several scalar variables. This technique is much more sensitive to toolchain particulars. The following is the above program converted to this format for gcc

main=11111111111111+1111111111111+111111111111+111111111111+111111111111+111111111111+111111111111+11111+1111+1111+1111+1111+1111+111+111+1;mainn=1111111111111111+1111111111111111+11111111111+1111111111+11111111+11111111+111111+1111+111+111+11+11+1+1+1+1;mainnn=111111111111111+11111111111+1111111111+1111111111+1111111111+1111111+1111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+11+11+1;mainnnn=111111111111111111+11111111111111111+111111111111+111111111111+111111111+111111+111111+111111+111111+1111+111+11+11+11+11+11+11+11+11+11+1+1+1+1;mainnnnn=11111111111111111+111111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111+1111+1111+11+11+11+1+1+1+1;mainnnnnn=111111111111111111+11111111111111+1111111111111+1111111111111+111111111111+111111111111+11111111111+111111+111111+111111+111111+1111+11+11+11+1+1+1+1+1;mainnnnnnn=11111111111111+1111111111+1111111111+1111111111+1111111111+111111111+1111111+1111111+111111+111111+111111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+11+1+1+1;mainnnnnnnn=111111111111+111111111111+11111111111+11111111111+11111111111+11111111111+1111111111+1111111+1111111+1111111+11111+11111+11111+111+11+11;mainnnnnnnnn=111111111111111+11111111111111+1111111111+111111111+111111111+111111111+1111111+111111+111111+11111+11111+11111+11111+11111+1111+1;mainnnnnnnnnn=1111111111111+1111111111111+1111111111+111111111+11111111+111111+111111+111111+111111+111111+111111+111111+11111+111+111+111+11+11+11+11+11+1+1;mainnnnnnnnnnn=111111111111111111+11111111111111+11111111111+11111111111+1111111111+1111111111+1111111111+111111111+11111111+1111111+111111+111111+1111+1111+1+1;mainnnnnnnnnnnn=1111111111111111+111111111111+11111111111+11111111111+11111111+111111+111111+111111+111111+111111+1111+1111+1111+1111+1111+111+111+111+111+111+111+11+11+11+11+1+1+1+1;mainnnnnnnnnnnnn=111111111111111111+11111111111111111+1111111111111111+11111111111+111111111+11111111+1111111+1111111+111111+11111+1111+111+111+111+11+1+1+1+1+1+1+1+1+1;mainnnnnnnnnnnnnn=11111111111111111+11111111111111111+11111111111111111+11111111111111+1111111111111+11111111111+11111111111+1111111+1111+1111+1111+1111+1111+1111+1+1+1+1+1;mainnnnnnnnnnnnnnn=111111111111111111+111111111111+11111111111+111111111+111111+1111+1111+1111+11+11+11+1+1+1+1+1+1+1+1+1;mainnnnnnnnnnnnnnnn=11111111111+11111111111+11111111111+1111111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+111+111+1+1;mainnnnnnnnnnnnnnnnn=1111111111111111+1111111111111111+11111111111111+1111111111111+111111111+111111111+11111111+1111111+111111+11111+11111+11111+11111+111+111+11+11+11;mainnnnnnnnnnnnnnnnnn=11111111111111111+11111111111111111+1111111111111+111111111+111111111+11111111+111111+111111+111111+111111+111111+111111+11111+111+111+111+11+11+11+11+11+1;mainnnnnnnnnnnnnnnnnnn=111111111+11111+11111+111+1;

Try it online!

C (gcc) (unportable), 24 18 13 8 5 characters

+1;=$

It is possible to represent any program with 5 distinct characters +1;=a by replacing main with a shorter entry point.

Try It Online!

Thanks to @Bubbler for 8 -> 5

Edit: More compact encoding in example programs.

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!

B (ybc), 26 24 18 17 distinct characters

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

main(){uto ;=1+&}

The following is a "Hello, World!" program that compiles and runs on x86 (32 bit) Linux.

main(){auto a;auto aa;auto aaa;auto aaaa;auto aaaaa;auto aaaaaa;auto aaaaaaa;auto aaaaaaaa;aaaaaaaa=1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+111+111+11+1;aaaaaaa=11+1+1;aaaaaa=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;aaaaa=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;aaaa=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;aaa=11111111+11111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+11+11+11+11+11+11+1+1+1+1+1+1+1;aa=1111111111+111111111+111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+11111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+1+1+1+1+1;a=11111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+1111+111+111+11+11+11+11+1+1+1+1+1+1;(&aaaaaaaa)();}

Try it online!

Thanks to @WeirdGlyphs for -1.

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!

JavaScript (ES6), 5 characters

(a)=>

by lambda calculus

See here for another 5c solution without arrow

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.

tinylisp, 4 3 characters

(q)

My starting point for the challenge is @DLosc's Answer where he presents a set of tinylisp functions that only use the built-ins d and q. I am going further by using only q. The argument is similar - that we can build a program using the S and K combinators which are known to be Turing Complete.

Instead of d (which is very convenient) - it allows us to reference a function by name - we use a set of re-write rules. Starting with an S-Expression containing only S, K & I which is our program, we apply the re-write rules in turn, replacing the left-hand-side with the right-hand-side. The end result is a program that uses only the built-in q and parameters which are strings of q's.

Update

Inspired by @emanresuA's comment, I was able to make space optional in the re-write rules by following these steps:

1. Replacing q with (q(()(qq)qq)) as needed
2. Replacing x with (q((qq)qq)x) as needed
3. Replacing functions with lists of atoms using list and q

Re-write Rules

I -> ((S K) K)

K ->
  (list 
    (list ((q(()(qq)qq)) qqq))
    (list ((q(()(qq)qq)) list) (list ((q(()(qq)qq)) q) (list ((q(()(qq)qq)) qqqq))) (list ((q(()(qq)qq)) list) (list ((q(()(qq)qq)) q) ((q(()(qq)qq)) q)) ((q(()(qq)qq)) qqq)))
  )


S ->
  (list
    (list ((q(()(qq)qq)) qqq))
    (list ((q(()(qq)qq)) list) (list ((q(()(qq)qq)) q) (list ((q(()(qq)qq)) qqqq))) (list ((q(()(qq)qq)) list) (list ((q(()(qq)qq)) q) 
      ((q(()(qq)qq)) S2)) (list ((q(()(qq)qq)) list) (list ((q(()(qq)qq)) q) ((q(()(qq)qq)) q)) ((q(()(qq)qq)) qqq)) (list ((q(()(qq)qq)) q) ((q(()(qq)qq)) qqqq)))
    )
  )


S2 ->
  (list
    (list ((q(()(qq)qq)) qqq) ((q(()(qq)qq)) qqqq))
    (list ((q(()(qq)qq)) list) (list ((q(()(qq)qq)) q) (list ((q(()(qq)qq)) qqqqq))) (list ((q(()(qq)qq)) list) 
      (list ((q(()(qq)qq)) q) ((q(()(qq)qq)) S3)) (list ((q(()(qq)qq)) list) (list ((q(()(qq)qq)) q) ((q(()(qq)qq)) q)) 
      ((q(()(qq)qq)) qqq)) (list ((q(()(qq)qq)) list) (list ((q(()(qq)qq)) q) ((q(()(qq)qq)) q) ) ((q(()(qq)qq)) qqqq)) (list ((q(()(qq)qq)) q) ((q(()(qq)qq)) qqqqq)))
    )
  )


S3 ->
  (list 
    (list ((q(()(qq)qq))qqq) ((q(()(qq)qq)) qqqq) ((q(()(qq)qq)) qqqqq))
    (list (list ((q(()(qq)qq)) qqq) ((q(()(qq)qq)) qqqqq)) (list ((q(()(qq)qq)) qqqq) ((q(()(qq)qq)) qqqqq)))
  )


list -> (q(qqq ((q((qq)qq))qqq) ))

Example

There are two programs. If all goes well, we expect them to evaluate to the same expression, which serves as a test.

Original Code

K
(I K)

After re-writing

((q(qqq ((q((qq)qq))qqq) )) 
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqq))
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqqq))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(()(qq)qq)) q)) ((q(()(qq)qq)) qqq)))
  )



(((((q(qqq ((q((qq)qq))qqq) ))
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqq))
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqqq))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) 
      ((q(()(qq)qq)) ((q(qqq ((q((qq)qq))qqq) ))
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqq) ((q(()(qq)qq)) qqqq))
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqqqq))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) 
      ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(()(qq)qq)) ((q(qqq ((q((qq)qq))qqq) )) 
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq))qqq) ((q(()(qq)qq)) qqqq) ((q(()(qq)qq)) qqqqq))
    ((q(qqq ((q((qq)qq))qqq) )) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqq) ((q(()(qq)qq)) qqqqq)) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqqq) ((q(()(qq)qq)) qqqqq)))
  ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(()(qq)qq)) q)) 
      ((q(()(qq)qq)) qqq)) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(()(qq)qq)) q) ) ((q(()(qq)qq)) qqqq)) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(()(qq)qq)) qqqqq)))
    )
  ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(()(qq)qq)) q)) ((q(()(qq)qq)) qqq)) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(()(qq)qq)) qqqq)))
    )
  ) ((q(qqq ((q((qq)qq))qqq) )) 
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqq))
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqqq))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(()(qq)qq)) q)) ((q(()(qq)qq)) qqq)))
  )) ((q(qqq ((q((qq)qq))qqq) )) 
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqq))
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqqq))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(()(qq)qq)) q)) ((q(()(qq)qq)) qqq)))
  )) ((q(qqq ((q((qq)qq))qqq) )) 
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqq))
    ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) qqqq))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) (q(qqq ((q((qq)qq))qqq) ))) ((q(qqq ((q((qq)qq))qqq) )) ((q(()(qq)qq)) q) ((q(()(qq)qq)) q)) ((q(()(qq)qq)) qqq)))
  ))

As a final step, we should remove line-feeds and spaces, however I've left the line-feeds and spaces in for clarity.

The TIO link contains the above code, where you can see the outputs from the two code fragments are the same, as expected.

Try it online!

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

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.

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.

Vyxal, 3 characters

`/¢

This answer has been several months in the making. I've spent a lot of time trying to find a 3-character Turing-Complete subset of Vyxal, and honestly this answer was somewhat obvious.

As I showed here, the Vyxal builtin ¢ on its own is Turing-Complete, as it can interpret a variant of Thue. However, that answer takes input in a very specific format; here we need to construct the input within the program itself.

Essentially, ¢ takes two lists of strings and a string to perform replacements on, and repeatedly applies replacements until the string doesn't change, which is sufficient for Turing-Completeness provided the strings are sufficiently complex. Thue requires at least two different symbols to be Turing-Complete (then arbitrarily many symbols can be generated by concatenatng the two).

So, we need some way to construct arbitrary strings / string lists that contain more than two distinct symbols. That's what the other two characters are for. `abc` delimits a string of characters abc, and / splits a string by another string. By splitting by a constant string (which then can't be used) we can construct arbitrary sets of rules. There's just one snag.

As I said before, Thue needs to have two distinct symbols to be Turing-Complete. However, in strings we can only have the symbols /¢, and we need to use one to split by. This is further complicated by that, in strings, Vyxal decompresses non-unicode characters into common words and expressions - ¢¢ becomes eyes and ¢ becomes [^aeiou]. For the sake of simplicity I'm just going to use ¢¢ and pretend ¢ doesn't exist.

In short, we need to construct three symbols out of / and ¢¢, such that no concatenation of any of them can contain any of them, ensuring they can be concatenated without causing problems. I came up with the set //¢¢//, ¢¢¢¢/¢¢¢¢, ¢¢/¢¢/¢¢, although something simpler probably exists.

With all of that, we can create arbitrarily complex replacement systems and emulate the behaviour of any Thue program, which is sufficient for Turing-Completeness! To do so, we push an initial string containing some combination of ¢¢¢¢/¢¢¢¢ and ¢¢/¢¢/¢¢, then two sets of rules containing some combination of //¢¢//, ¢¢¢¢/¢¢¢¢, ¢¢/¢¢/¢¢ and split them by //¢¢//, then simply run ¢. Here's a extremely-overcomplicated binary-to-unary converter with some vague explanations of what's going on, and it's possible to expand this approach to emulate any possible Thue program.

I feel like three characters is optimal for this, and I can't imagine how a two-character solution would work.

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.

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!

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.

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

PHP 7, 5 characters

(^.9)

https://github.com/arxenix/phpfuck

How it works

• 9^99 -> 106
  • use xor to generate numbers
• (9).(9) -> '99'
  • use . to concat numbers into strings
• '09'^'1069'^'99' -> '80'
  • xor 2 strings to get a string
• '80'^0 -> 80
  • (ab)use type juggling to cast a string to an int
• Using a combination of the above tricks, you can get all of the digits 0-9
• Can construct any string /[0-9]+/ by concatenating digits
• Can obtain any number by casting to int
• Constructing arbitrary strings requires a bit more work...
  • (99999999999...) -> INF
    • 309 9s gives us INF
  • (INF).(9) -> 'INF9'
    • Can now obtain char values in /[a-zA-Z]/ range!
    • e.g. 'INF9'^'00'^'33'^'99' -> 'st'
  • the only primitive we have for initially obtaining strings is concat, which gives us a length-2 string
  • we can generate /[a-z]{2,}|[A-Z]{2,}/ , but getting single-character strings is not possible
• 'funcname'(param)
  • call functions by simply calling their string name
  • function names are case-insensitive
• strtok(0) -> false
  • call strtok on a number to get false
  • === ('st'+'rt'+'OK')(0)
• (9).false -> '9'
  • concat number with false to get a length-1 string
• 'rw'^'99'^'9' -> 'r'
  • extract first char of any string with xor
• Can now build arbitrary strings /[a-zA-Z]/
• 'CHr'(num)
  • generate other characters (e.g. spaces)
• Can now build any string at all! /.*/
• str_getcsv("a,b") -> ["a", "b"]
  • create string arrays by parsing a CSV
• func(...["a", "b"])
  • use spread operator to pass multiple arguments to a function
• create_function("", "PAYLOAD")()
  • use create_function to create a function w/ arbitrary PHP code and then call it
• Final payload looks like: 'create_function'(...str_getcsv(',"$PAYLOAD"'))

Previous Work

PHPFuck by splitline - using 7 different characters ([+.^])

Racket (Scheme), 3 characters

(λ)

Using only λ and parenthesis we can directly program in the Lambda Calculus subset of Scheme. We reuse the λ character for all identifiers by concatenating them together to provide an arbitrarily large number of unique identifiers.

As an example, here is the classic Omega combinator, which loops forever.

((λ (λλ) (λλ λλ)) (λ (λλ) (λλ λλ)))

edit: And as per @SoupGirl's comment, the spaces can be substituted out for the identity function (λ(λλ)λλ) which would effectively eliminate the need for space but using the parens for a lexical break between function and argument yet only use λ and parens and be functionally equivalent. Thus for the same Omega above we have.

((λ(λλ)(λλ(λ(λλ)λλ)λλ))(λ(λλ)(λλ(λ(λλ)λλ)λλ)))

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.

Knight, 4 characters

EA1+

Similar to many other answers here, the plan is to build a string representing Knight code using ASCII, 1, and +, and then use EVAL to run the resulting string as Knight code.

To build the string, we will build each individual character with A, 1, and +. Then, we will concatenate each character together using +.

To build each character, we can simply just keep adding combinations of 111, 11, and 1 until the desired codepoint is reached, which we can then use A to convert the codepoint to a character. Though you may notice that if you actually tried to create a number with just + and 1, you will need to include a space between at least one of the pairs of operands. For example, to create a !, you will have to do A+11+11 11; if you removed the space, then 1111 will be treated as a single number and you won't have enough arguments for one of the +'s.

To bypass that problem, we will take advantage of coercion. By adding a number with ASCII 1 (making sure the number is the first argument), A1 will be coerced to 0, which will not affect the sum. The reason for using A1 is to remove the need for spaces in the code. We can add all the numbers together as usual, but we will add one extra + at the end, which adds a number (1, 11, 111) to A1. But because 1 and A1 can be differentiated as two different values without a space, we can write, for example, +1A1 instead of +1 A1. Now, to create a !, you can do A+11+11+11A1.

Now that we have a strategy for building any character, we can now go on to concatenate all of them together into one string using +. We can do so with the following template (parentheses are just for formatting purposes):

(+ ... +) (A+...+1A1) (A+...+1A1)...

Then we can put E at the beginning to EVAL the string.

One final thing to note is the event that there is only one character in the string. Then we might have something like EA+11+11+11+11+1+1+1+1A1 for evaluating 0, but EA will be parsed as one function instead of two, so it might look like we need a space there. But we can simply concatenate a whitespace character like a space, which fixes the problem.

Here some Python code which can convert any inputted Knight code into equivalent Knight code using only the characters EA1+: Try It Online!

Python 3, 8 characters

Now we can write python in only 8 characters!

Previous works have found that any python codes can be reduced into 9 characters. Such as: exc('%1+) and exchr(+1).

Their core ideas are both using exec() to execute a python string. Then use python formatting '%c'%(number) to build other characters. Finally generate arbitrary number by some arithmetic, e.g. +1+1 here.

Execute Python in 8 characters: exc('%0)

Basically, we can continue the previous ideas of exec() and formatting by '%c'.

However, previous works were trapped by generating arbitrary number. As they have to include new characters but not make full use of existing characters.

How to build numbers? Remember that hex number is also number.

There already have existing number character(ce in hex) and arithmetic characters(%).

Thus, we can include only character 0 to build hex numbers such as 0xEECC00(capitalization for visual purpose). With all the numbers of 0xXXXX where X refer to '0CE' we can get numbers by modulo operation such as:

0xC0C0E % 0xEC = 98
0xEC % 0xC0 = 44

Can we build arbitrary number through this method? No.

It can be easily proved that '0CE' are all even numbers. Modulo with even numbers can only get even numbers. And unfortunately, All decimal odd numbers, '1', '3', '5', '7', '9' have odd ASCII codes.

Is there no hope? Remember that hex number is also number again!

Coincidentally, hex odd numbers, 'b'=98, 'd'=100, 'f'=102 have even ASCII codes. Now everything is clear.

First, we can use 0xCE to generate even numbers. It is hard to prove that we can get any big number by 0xCE%, but I have enumerate all even numbers from 2-128, which is enough for us.

Then we can use '%c'%(0xC0C0E % 0xEC) to get 'b'. And get arbitrary number by '0xBCE'.

Finally, build arbitrary string and execute!

github: https://github.com/kuangkzh/PyFuck

Zsh, 8 characters

$#< (){}

• <<<string prints string
• (){body} args is an anonymous function, which is immediately called with args
• <<<$# outputs the number of arguments to a function
• So we can use (){<<<$#} $ $ $ to output 3 (for example)
• ${(#)var} gets the character with the codepoint stored in var
• ${(#)$(command)} gets the character with the codepoint that is the result of command
• We can combine these to generate arbitrary characters, e.g. ${(#)$((){<<<$#} $ $ $)} is \x03

Hence, we can construct the string eval:

${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}

And use that to execute any arbitrary code. Here is a demonstration that outputs Hello, World (3311 bytes):

${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)} ${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}${(#)$((){<<<$#} $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $)}

Attempt This Online!

$#(){} are integral to this method, but I think there might be a way to remove or <. Unfortunately I can't find one without adding a different character instead.

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.

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.

Emmental, 3 characters

#5?

Every character can be represented with these characters and '?' can execute them. For example, a program printing 'H':

##5#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555??#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?###5#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555??##5#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555??#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555??#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555?#5#555??

Try it online!

ARM assembler (gas), 14 12 chars

Newline and space are included.

 bdlrst:[],

This gives us exactly what we need for Turing completeness without self modifying code:

• 3 registers: sl (r9), sb (r10), and lr, the minumum for RISC without immediates
• Subtraction via rsb. Note that this is reversed subtraction, so it is x = z - y.
• Conditional branching via rsbs/tst and bls/blt (as well as conditional instructions)
• Arbitrary value generation by ldr(s)b reg,label and using encoded branch offsets (see below). Can generate [-128,255].
• Virtually unbounded memory storage via ldr and str, something the other ARM answer didn't address _{(pun intended).}

Even though we only have subtraction and shifting and no immediates, what we can do is read the encoding of a branch instruction, using only labels.

b encoding

 31 30 29 28  27 26 25 24 23 22 21 20 .... 0
[   cond    ][1][0][1][0][ (offset - 8) / 4 ]

(The offset - 8 is a weird quirk where pc actually points two instructions ahead).

For example:

foo:
     b       next
     nop
     nop
next:

will be encoded as so (ARM instructions are little endian):

00000000 <foo>:
   0: 01 00 00 EA   b       <foo+0x8> // imm = #4
   4: 00 00 A0 E1   nop               // (mov r0, r0)
   8: 00 00 A0 E1   nop               // (mov r0, r0)

Therefore, if we wanted to get the value 1 into sl, we could do this:

    ldrb  sl, get_one
get_one:
    b     next // (pc + 4), [01]00 00 EA
    (not executed)
    (not executed)
next:

Similarly, -1 can be done like so:

    ldrsb sl, get_minus_one
get_minus_one:
    b     next // (pc - 4), [FF]FF FF EA
next:

Therefore, to prove Turing completeness, here is a Brainfuck prologue and translation. Labels are given readable names, but in actual code it would be a bunch of bdlrst gibberish and there will be no comments. I/O is done by read/write to a magic port of address 0.

While this must be in a RWX section to initialize the tape, the instructions that will be overwritten will not be executed, therefore it does not count as self modifying code. The only requirement when assembled is that pc is set to the first instruction.

///// Prologue

prologue:
        // tape setup
        bl      tape_end            // jump to end of tape, set lr to first cell
        rsb     sb, sb, sb          // nop 
tape_start:
        // 8160 filler instructions to be overwritten
tape_end:
        // code starts here
get_one:
        b       next                // [01]00 00 EA
get_7:
        b       <get_7+36>          // not writing that label
get_minus_one:
        b       next                // [FF]FF FF EA
next:
        // clear tape
        ldrb    sb, get_minus_one   // sb = 255 (zero extended)
        ldrb    sl, get_7           // sl = 7
        lsl     sb, sb, sl          // sb = sb << sl = 255 << 7 = 32640
clear:
        ldrsb   sl, get_one         // sl = 1
        rsbs    sb, sl, sb          // sb = sb - 1, set flags
        rsb     sl, sl, sl          // sl = sl - sl = 0
        strb    sl, [lr, sb]        // store 0
        bls     end_clear           // if zero, jump to end of clear loop
        b       clear
end_clear:

///// Instruction translation

// >
        ldrsb   sl, get_minus_one   // sl = -1
        rsb     lr, sl, lr          // lr = lr - sl (lr = lr + 1)

// <
        ldrsb   sl, get_one         // sl = 1
        rsb     lr, sl, lr          // lr = lr - sl (lr = lr - 1)


// +
        ldrb    sb, [lr]            // load cell from tape
        ldrsb   sl, get_minus_one   // sl = -1
        rsb     sb, sl, sb          // sb = sb - sl (sb = sb + 1)
        strb    sb, [lr]            // store cell to tape

// -
        ldrb    sb, [lr]            // load cell from tape
        ldrsb   sl, get_one         // sl = 1
        rsb     sb, sl, sb          // sb = sb - sl (sb = sb - 1)
        strb    sb, [lr]            // store cell to tape

// [
loop_start:                         // label for start
        ldrb    sb, [lr]            // load cell from tape
        rsb     sl, sl, sl          // sl = sl - sl = 0
        rsbs    sb, sl, sb          // sb = sb - sl (sb = sb - 0), set condition codes (TST will not set C flag)
        bls     loop_end            // If sb was zero, the "lower or same" cond will be set, jump to end
loop_body:

// ]
        b       loop_start          // Jump to beginning of loop
loop_end:                           // Label for end

// .
        rsb     sl, sl, sl          // sl = nullptr
        ldrb    sb, [lr]            // load from tape
        strb    sb, [sl]            // store to I/O port

// ,
        rsb     sl, sl, sl          // sl = nullptr
        ldrb    sb, [sl]            // load from I/O port
        strb    sb, [lr]            // store to tape

Literally every GAS dialect, 9 chars

Again, newline and space

 01.bety

The boring answer which allows encoding ANY opcode manually using .byte 0b10101010.

TI-Basic, 15 characters

^{(TI-83 Family)}

While End(-1:ʟ→

^{Note that TI-Basic is token-based instead of character-based. - represents the subtraction symbol, not the negative sign. ) is not needed because TI-Basic automatically closes all parentheses when it reaches a : or →. The minimum distinct tokens would be 9 tokens: While , End, (, -, 1, :, ʟ, →, and any capital letter or theta.}

With these characters, you can use:

• While for conditional branching and looping (checks if the expression is nonzero)
• End to end a While loop
• W and E as number variables
• 1, -, and ( for constructing integers (e.g. 1-1 is 0, 1 is 1, 1-(1-1-1 is 2, 1-(1-1-1-1 is 3, 11-1-1 is 9, etc.) and doing operations (- can be used for addition and subtraction, and ( can be used for implied multiplication)
• : for separating commands and can be replaced with a newline
• → to store values into number variables and into list elements
• ʟ, W, E, and 1 to reference lists (which can store up to 999 numbers or 99 on a TI-83); you can construct 242 possible list names from W, E, and 1
• ( to get an element from a list

This is Turing-complete because you can translate brainf*ck (without , and . and with 999 or 99 cells), which is Turing-complete, with these characters:

_{W stores the position of the pointer, ʟE stores all the cells, and E is a temporary variable. The TI-83 versions use 99 cells instead of 999 cells.}

Here is a program that prints a list of the first 99 Fibonacci numbers:

1→ʟE(1:1→ʟE(1-(1-1-1:111-11-1-1-1→W:While W:ʟE(111-11-1-1-W→E:E-(1-1-ʟE(111-11-1-W→ʟE(111-11-W:W-1→W:End:ʟE

80386 machine code, 10 bytes

4c 44 fe 24 04 0c 0f 85 90 c3

We are assuming an environment where the system calls this program with plenty of stack space accessible by decrementing esp, and a ret with the initial esp will end this program. At start, esp will hold the address to return. A predefined size of data stored upwards from esp + 4 will be the input, and a predefined size of data stored downwards from esp - 1 will be the output.

Since Brainfuck is turing complete, implementing a Brainfuck-style computing model will also be turing complete. The following Brainfuck operators can be easily translated.

>  dec esp        ; 4c
<  inc esp        ; 44
+  inc byte [esp] ; fe 04 24
-  dec byte [esp] ; fe 0c 24

Brainfuck has [ and ] for looping and conditional branching. To implement ], we first need to compare the stored value to zero.

inc byte [esp]
dec byte [esp]

This is a nice trick from @Bubbler that effectively does a compare-to-zero. Sometimes, you can also omit the comparison right after a dec.

80386 has two conditional jumps when the zero flag was not set.

jnz rel8  ; 75
jnz rel32 ; 0f 85

While jnz rel8 has a shorter encoding, I'm not sure if it's enough to make the program turing complete, so we are instead using jnz rel32. Then, the relative offset can really be any byte without care, so we need,

nop ; 90

to pad the code so that the relative offset only consists of the usable bytes.

Finally to end the program,

ret ; c3

Here is an example program that takes two non-zero numbers as input, and outputs the sum.

sum:
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
.loop0:
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    inc byte [esp]    ; fe 04 24
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    dec byte [esp]    ; fe 0c 24
    
    ; A LOT of `nop`s ; 90
    
    jnz .loop0        ; 0f 85 fe fe fe fe
    inc esp           ; 44
.loop1:
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    inc byte [esp]    ; fe 04 24
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    dec byte [esp]    ; fe 0c 24
    
    ; A LOT of `nop`s ; 90
    
    jnz .loop1        ; 0f 85 fe fe fe fe
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    ret

Baba is You, 18 characters

Plus 3 objects in the game.

TEXISMOVLPDWNFRGHY

A Rule 110 implementation can be made with only these characters. This is based on This writeup by Matthew Rodriguez.

All the rules and explanation:

--- Always Active Rules ---
TEXT IS MOVE   - Makes the 'IS' move.
MIRROR IS TELE - When 'IS' moves into the mirror, it teleports to the other
                 mirror, like a `for` loop.
PIPE IS STOP   - Prevent text other than 'IS' from moving.

--- Rules that are activated once in a loop ---
ME           (IS) LOVE/PIXEL
MOON         (IS) IT/TILE    - 'ME' and 'MOON' are construction objects,
                               and together they represent the value 
                               1. Each cycle, they turn to three probes
                               ('LOVE', 'IT', 'TILE') and a visual object
                               ('PIXEL').

LOVE/IT/TILE (IS) MOVE/DOWN  - The three probes move down, ready to create
                               the next generation according to Rule 110.

IT           (IS) MOVE/LEFT  - 'IT' moves to the left, representing xx1.

TILE         (IS) MOVE/RIGHT - 'TILE' moves to the right, representing 1xx.
                               'LOVE' stays, representing x1x.

LONELY LOVE  (IS) LINE       - 'LOVE' without 'IT' or 'TILE' represents a
                               010 pattern, which results in 'LINE' which
                               represents the value 1. 

LONELY IT    (IS) LINE       - 'IT' without 'LOVE' or 'TILE' is the 001
                               pattern which results in 1.

LOVE ON IT   (IS) VINE       
IT ON VINE   (IS) EMPTY      - Create 'VINE' which represents x11 where
                               we do not know the value of x yet. 

VINE ON TILE (IS) EMPTY      - 111 results in 0.
LONELY TILE  (IS) EMPTY      - Remove the tile as well.

VINE/TILE    (IS) LINE       - Any remaining 'VINE' is 011, which results
                               in 1. Any remaining 'TILE' is either 101 or
                               110, which both result in 1 as well.

LOVE/IT      (IS) EMPTY      - Clean up any remaining probes.
LINE         (IS) ME/MOON    - Turns 'LINE' into construction objects.

Here is a screenshot of the initial state of the level.

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

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

Perl, 5 characters

<>^es

As with other scripting languages, the idea is to eval arbitrary strings. However, our character set doesn’t include quotes or concatenation operators, so constructing arbitrary strings is gonna be way more complex. Note that eval^" would be much simpler to deal with, but has one more character.

Our main tool is s<^><CODE>ee, which evals CODE, then evals its output. More e can be added, each one causing the output of the previous one to be evaled.

We get strings using <>, which is the glob operator except when it isn’t. The first character can’t be < (otherwise it looks like the << operator), the angle brackets need to be balanced, and there must be at least one non-letter character (otherwise it’s interpreted as the readline operator).

^ is the xor operator, and it can be used on strings, doing character-per-character bitwise xor. By xoring strings from our character set together, we can get any combination of characters from ^B^V^S(*-/9;<>HJMOY[`\^begqstv, as long as we accept having some garbage around (the first three of those are control chars).

For example, suppose we want to get "v99". One way to get v99 is "><<" ^ "e>>" ^ "see" ^ "^^^", but we can’t represent those strings due to the constraints on <>. So instead, we use:

<^<<^>><>>^<^^^^^<>>^<^^^^^^e>^<^^^^^^^>^<^^^^^e>^<^^^^e^>^<e^^es>^<^ee^^>^<^<^^^^^>>^<^<>^^^^>^<^^^^^^^e>^<^^^^^^^^>

The above yields Y9;v99;, which, when eval-ed, yields the same result as a plain v99 (namely, the character with ASCII code 99).

Thus we can use the entire ^B^V^S(*-/9;<>HJMOY[`\^begqstv charset to generate our arbitrary string, then convert it as above and stick it in a s<><CODE>eeee to execute it. Unfortunately, this charset is still very limited, without any obvious way to perform concatenation.

But fortunately, it contains the star. This lets us write *b, which evaluates to the string "*main::b". Then, *b^<^B[MMH^V^SY> (^B, ^V and ^S are literal control characters) gives us (6, $&);, which, when eval-ed again, returns the value of Perl’s match variable, $&. This lets us use a limited form of concatenation: we can repeatedly prepend things to $_ using s<^><THINGS>e, and then use s<\H*><*b^<^B[MMH^V^SY>>eee to eval $_ (\H matches anything but horizontal whitespace; we use it instead of the dot, which isn’t in our charset).

Using 9-/, we can easily generate all digits. Using digits, v, and concatenation, we can generate arbitrary characters (vXXX yields the character with ASCII code XXX). And we can concatenate those, so we can generate arbitrary strings. So it looks like we can do anything.

Let’s write a complete example. Suppose we want a program that prints its own PID. We start with the natural program:

say$$

We convert it to v-notation:

s<><v115.v97.v121.v36.v36>ee

We rewrite this using only ^B^V^S(*-/9;<>HJMOY[`\^begqstv (whitespace is for readability only and doesn’t affect the output):

s<^><
    s<^><9*9-9-9-9-9-9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><9*9-9-9-9-9-9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><99-99/-9-99/-9>e;
    s<^><v>;
    s<v\H\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><99-9/9-9/9>e;
    s<^><v>;
    s<v\H\H><*b^<^B[MMH^V^SY>>eee;
    s<^><999/9-9/-9-9/-9-9/-9-9/-9>e;
    s<^><v>;
    s<v\H\H\H><*b^<^B[MMH^V^SY>>eee;
    s<\H*><*b^<^B[MMH^V^SY>>eee;
>eee;

Finally, we convert the above program to only <>^es: pastebin. Sadly, this crashes Perl with Excessively long <> operator, but that’s just a technical limitation and shouldn’t be taken into account.

Phew, that was quite the journey. It’d be really interesting to see someone come up with a set of 5 characters that makes things simpler.

EDIT: by using a slightly different approach, we can avoid hitting the length limit on <>. Fully functional brainfuck interpreter using only <>^es: Try it online!. Automated Perl to <>^es transpiler: pastebin.

05AB1E, 5 4 bytes

.gBV

-1 distinct byte thanks to @ovs.

Explanation:

• .g: Pushes the amount of items currently on the stack
• g: Pop the current item, and push its length
• B: Pops the top two items on the stack, and do base-conversion
• .V: Pops and evaluates the top string as 05AB1E code

Using the .g + g we can create any positive number. Using B we can convert combinations of two numbers to a string of characters from the 05AB1E codepage. And using .V we can evaluate those characters as 05AB1E code.

One thing to note when creating such programs: according to the 05AB1E source code, the order of the characters used in the base-conversion up to 256 is: 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzǝʒαβγδεζηθвимнт\nΓΔΘιΣΩ≠∊∍∞₁₂₃₄₅₆ !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~Ƶ€Λ‚ƒ„…†‡ˆ‰Š‹ŒĆŽƶĀ‘’“”–—˜™š›œćžŸā¡¢£¤¥¦§¨©ª«¬λ®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿ. So a slightly different order than the 05AB1E codepage (which makes sense, since we start with digits and letters for the base-conversion).

To generate a program, we basically push loads and loads of .g, until the integer that is pushed is of length 255. Then we can use one more .g plus the g to push 255, after which the B will convert the large integer to base-255, resulting in the program string, which we eval with .V.
When generating these programs, it will likely have loads of prepended no-ops (e.g. spaces, newlines, w, etc.), and I would advice to always add a leading )\ as well to clean the entire stack of integers from the numerous .g, so implicit input and stack manipulation is available as well.

Here a generator program given a 05AB1E program string as input, where the huge number of the output is replaced with that many .g, and the D> is replaced with one additional .g.

Try it online:

Here a few example programs using these five bytes (again, where the huge number and D> would then be replaced with that many .g in the actual program):

Try it online: 2+2 (YY+).
Try it online: Check if the input is a prime number (p).
Try it online: Print "Hello, World!" (”Ÿ™,‚ï!).
Try it online: Print the infinite Fibonacci sequence (∞<Åf).

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!

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.

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.

Self-modifying Brainfuck, 2 characters

<+

Using these characters we can modify the end of the program in a way that it executes normal Brainfuck code.

Start by choosing the Brainfuck program, put [>] in the begining, that way the pointer will start where it should be. The number of bytes will be the number of + in the end of our code. Next we need the ascii values of the characters used in the bf code minus 43. These are how much we need to add to each +. For each number in our list we print < followed by that number of +, but start by the end of the list. Put everything together and it should do the same thing the bf code does.

Exemple: a bf cat ,[.,]

It becomes [>],[.,].

Now it has 8 bytes, so we should end the smbf code with ++++++++.

The ascii values are 91, 62, 93, 44, 91,46, 44 and 93. Subtracting 43 we get 48, 19, 50, 1, 48, 3, 1 and 50.

50: <++++++++++++++++++++++++++++++++++++++++++++++++++
 1: <+
 3: <+++
48: <++++++++++++++++++++++++++++++++++++++++++++++++
 1: <+
50: <++++++++++++++++++++++++++++++++++++++++++++++++++
19: <+++++++++++++++++++
48: <++++++++++++++++++++++++++++++++++++++++++++++++

Putting this before the ++++++++ gives the final smbf code:

<++++++++++++++++++++++++++++++++++++++++++++++++++<+<+++<++++++++++++++++++++++++++++++++++++++++++++++++<+<++++++++++++++++++++++++++++++++++++++++++++++++++<+++++++++++++++++++<++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Try it online!

Execution:

<++++++++++++++++++++++++++++++++++++++++++++++++++  # Add 50 to the last byte of this code, now it ends with +++++++++++++]
<+                                                   # Add 1 to the byte to the left of that, now it ends with ++++++++++++,]
<+++                                                 # +++++++++++.,]
<++++++++++++++++++++++++++++++++++++++++++++++++    # ++++++++++[.,]
<+                                                   # +++++++++,[.,]
<++++++++++++++++++++++++++++++++++++++++++++++++++  # ++++++++],[.,]
<+++++++++++++++++++                                 # +++++++>],[.,]
<++++++++++++++++++++++++++++++++++++++++++++++++    # ++++++[>],[.,]
[>]                                                  # This was originally +++ ,but now it tells the pointer to go to the right until it leaves the code
,[.,]                                                # Execute the Brainfuck code

Here is a GolfScript program where you input a Brainfuck code and it outputs a Self-modifying Brainfuck code that does the same, using only < and +.

'[>]'\+.,:l{'<'\)43-'+'*\}\*'+'l*

Try it online!

Scala, 12 chars

(),:;=>[]def

Using these characters, you can encode the SKI calculus. I replaced the semicolons with newlines for readability:

def>[d,e,f]:(d=>(e=>f))=>(d=>e)=>(d=>f)=(dd:d=>e=>f)=>(ee:d=>e)=>(ff:d)=>dd(ff)(ee(ff))
def>>[d,e]:d=>e=>d=(dd:d)=>(ee:e)=>dd
def>>>[d]:d=>d=(>[d,d=>d,d])(>>[d,d=>d])(>>[d,d])

(Ab-)using the fact that you can call a method >, which will be seperated from the def by the parser to save the space.

Borrowed from here and optimised for this challenge.

Setanta, 14 characters

adghimnort(){}

Provides a way to encode the SKI combinator calculus as shown:

i := gniomh(g){toradh(g)}
k := gniomh(g){toradh(gniomh(n){toradh(g)})}
s := gniomh(g){toradh(gniomh(n){toradh(gniomh(i){toradh(g(i)(n(i)))})})}

Then inline i, k, and s as needed.

Whispers v1, 7 characters

> 1+'⍎

The main idea is to build an arbitrary Python expression using + (addition or string concat) and ' (chr) and ⍎ (eval) it. So the proof is in two parts: constructing an arbitrary string, and making sure that Python's eval (as opposed to an arbitrary program) is Turing-complete.

Python eval is Turing-complete

Unlike exec, we can't use many syntactic keywords like while and even def. But we have lambda expressions, and it turns out that we can implement untyped lambda calculus. As a minimal example, the following expression is an infinite loop:

(lambda a:a(a))(lambda a:a(a))

To make it more explicit, here are SKI combinators:

S = lambda l:lambda a:lambda m:l(m)(a(m))
K = lambda l:lambda a:l
I = lambda l:l

> 1+'\n is enough to construct an arbitrary string

Now to actual Whispers code. The lines starting with single > are constant lines, and those with double >> reference other expressions using line numbers. We will only use 1, 11, 111 for constant lines, and construct the required charcodes using addition. The following sets up three numbers for the string "123" (charcodes 49, 50, 51):

> 1
> 11
>> 2+2  // 22
>> 3+3  // 44
>> 1+1  // 2
>> 5+5  // 4
>> 4+6  // 48
>> 7+1  // 49
>> 8+1  // 50
>> 9+1  // 51

Then we apply ' (chr) to each of the charcodes:

>> '8   // "1"
>> '9   // "2"
>> '10  // "3"

Finally, we concat and eval them.

>> 11+12
>> 14+13
>> ⍎15

We successfully created the string "123" and passed it to eval. Now the only problem is that we used all digits to reference lines. It can be easily circumvented by inserting dummy syntactically valid lines > 1 so that we can reference meaningful lines with repunits (so the line number n will be translated to the number containing n copies of 1):

> 1  // valid line 1
> 1    // from line 2...
> 1
...
> 1    // ...to line 10 are dummy lines
> 11 // valid line 11
> 1    // from line 12...
...
> 1    // ...to line 110 are dummy lines
>> 11+11 // valid line 111
...

7 chars is (likely) minimal, at least in v1

I checked the whole source code, and all one-char functions except ⍎ do not have mutable state at all. There are looping constructs like While, but using it alone requires at least 8 chars > While1. Therefore, the approach using ⍎ must be minimal (where 7-char solution is already known).

For TC-ness in Python eval, we need at least lambd :(), which is already 9 chars, and chr is definitely needed to create them without them in the source code. There is no 1-char solution to create those charcodes, and 1+ shares + with string concatenation. Therefore using 1+' as the core chars is the minimal way to build a string that enables TC-ness.

I didn't read all of v2 and v3 source code, but I believe the 7-char solution is likely minimal on those too.

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.

Binary Lambda Calculus, Binary Mode, 3 characters (ascii-encoded)

HR.

Interpreted as incomplete segments of Binary Lambda Calculus, writing \ for lambda, * for application and De Bruijn indices for variables:

H = 01001000 = * \ 1 \
R = 01010010 = * * \ 1
. = 00101110 = \ 1 3

Suppose x and y are valid terms.

Then,

  H x
= * \ 1 \ x
= \ x

  R x y
= * * \ 1 x y
= * x y

  R .
= * .
= * \ 1 3
= 3

Thus we can use H as \, R as *, and R. as 3.

For 2 and 1, suppose we have any valid term z.

Then,

* \ 3 z = 2

* \ 2 z = 1

(Free variables get decremented in beta-reduction with De Bruijn indices)

As for the choice of z, we can use z = \ \ \ 3 (or if we allow free variables in our program, we can just use 3).

Finally, to show we don't need more than 3 variables, we can implement SKI combinator calculus:

I = \ 1
K = \ \ 2
S = \ \ \ * * 3 1 * 2 1

Written using our 3 characters, these are

I = HRHRHR.HHHR.HHHR.
K = HHRHR.HHHR.
S = HHHRRR.RHRHR.HHHR.HHHR.RRHR.HHHR.RHRHR.HHHR.HHHR.

Which can be applied to each other in arbitrary ways using R.

C (gcc), 19 bytes

main*fort(){}-=1[];

My implementation is Turing-complete because it can emulate another Turing-complete language.

32-bit cell Brainfuck interpreter (no I/O) using the commands as UTF-32 characters from the first command-line argument:

itr;nat;arr[111111-11111];rra=111-11-1-1-1-1-1-1-1;ora=111-11-1-1-1-1-1-1-1-1-1;aro=111-11-11-11-11-1-1-1-1-1-1-1;rar=111-11-11-11-11-1-1-1-1-1;min=111-11-11-11-11-11-11;aff=111-11-11-11-11-11-11-1-1;main(i,a)int**a;{for(i-=1;a[1][i];i-=-1){if(a[1][i]==aff)arr[itr]-=-1;if(a[1][i]==min)arr[itr]--;if(a[1][i]==aro)itr--;if(a[1][i]==rar)itr-=-1;if((a[1][i]==ora)*(arr[itr]==1-1))for(nat=1;nat;){i-=-1;nat-=-(a[1][i]==ora);nat-=a[1][i]==rra;}if((a[1][i]==rra)*(1-(arr[itr]==1-1)))for(nat=1;nat;){i-=1;nat-=-(a[1][i]==rra);nat-=a[1][i]==ora;}}}

aff is +.
min is -.
aro is <.
rar is >.
ora is [.
rra is ].

Note that I can't figure out how to run it yet but it should theoretically work.

Java (5 or later), 15 characters

02367?\abcdeitu

We've had a few previous answers in Java. The basic approach in all of them is to a) identify a minimal Turing-complete subset of the language, and b) find a minimal way to express the constructs of that language in Java's syntax.

Hexagraph notation

Let's look at b) first. As explained in @Poke's answer above, Java has a hexagraph syntax (analogous to C's trigraph syntax) to allow arbitrary characters that might not exist in your character set to be included in your program. For example, a newline could be written as a literal newline, but it could also be written as the hexagraph \u000a; the hexagraph consists of \u followed by four hexadecimal digits, specifying the character's Unicode codepoint. Unlike C's trigraphs, which can only be used for a few awkward characters, a Java hexagraph can be used for absolutely any Basic Multilingual Plane character we might happen to need (including printable ASCII characters).

The previous records, 17 by @Poke, and 16 by @Poke and me, were based on taking relatively normal-looking Java programs and simply trying to hexagraph every character in them: your character set is then based on which nybbles occur in the codepoints you're using. If a nybble occurs in two different codepoints, it typically saves character set entries to include that nybble in the character set, so you can construct the codepoint with it. One minor improvement for this entry is that if a nybble only occurs in a single codepoint, we may as well include that codepoint in our character set directly: the resulting programs will end up slightly shorter.

Of the 16 nybbles, this entry manages to omit 2 entirely: 5, and 8. 4, 9, and f are also omitted; each is only needed to write a single character (t = U+0074, i = U+0069, and ? = U+003F respectively), and including that character directly leads to shorter and "more readable" programs. One final saving is available from a/1: we don't need a as a nybble to write any character, we do need to be able to produce U+0061, a's codepoint, but we don't need 1 for any other codepoint. So a and 1 are redundant with each other: we need at least one of them, but don't need both; and omitting a/1, 5, and 8 from our base set of 18 characters \u0123456789abcdef gives us our final character set.

Of course, this means that we have to avoid many more missing characters than in the other entries. In particular, we can no longer create the boilerplate for a main method (which must have a parameter of type String; S = U+0053 contains the forbidden nybble 5). So we're going to need a radically different way of running a Java program.

Java as an interpreter

Java is normally a compiled language; a typical workflow is to use the compiler javac to compile your Java source files into one or more .class files, and then the JVM java to run those source files, and take the output of java as the output of the program. None of your code actually runs at compile time, so the output of javac is typically regarded as uninteresting.

Nonetheless, javac does contain some nontrivial functionality; Java is, after all, a fairly complex language. We can take a single Boolean of output from the compiler javac by checking to see if there are compile errors, looking at its exit code: if the program has errors, that will produce a different output from if the program doesn't have errors. Of course, Java being a compiled language, an erroring program might not seem particularly useful from a Turing-completeness point of view: if it has errors, it won't actually run, so how could it be Turing-complete? However, it turns out that type-checking Java programs is in of itself a Turing-complete operation; all we need to be able to do is to be able to compile programs from some Turing-complete language into Java's type system, in such a way that, in order to determine whether the resulting program is valid Java or not, the type-checker will have no choice but to run the program we compiled.

The Subtyping Machine

The Subtyping Machine is an esoteric programming language that was "back-derived" (by Radu Grigore in 2017) from Java's type system, looking at the algorithm that Java actually uses to determine whether an expression has the correct type or not. Here's an example I wrote of what this sort of program looks like:

interface xx {}
interface A<x> {}
interface B<x> {}
interface d<x> extends
  A<s<? super X<? super B<? super s<? super X<? super d<x>>>>>>>,
  B<x>, xx {}
interface X<x> extends xx {}
interface s<x> extends xx {}

class x {
  d<? super X<? super d<? super X<? super d<? super X<? super s<xx>>>>>>> xc;
  A<? super s<? super X<? super d<xx>>>> xd = xc;
}

The bulk of the program is basically just a lot of interfaces extending each other with contravariant generic type parameters. If you have A<x> extends B<…<? super x>>, and you're trying to see whether an expression starting A<…> can be stored in a variable of type B<…>, what ends up happening is that the first type ends up getting potentially much more complicated as the generic parameter is expanded, and then the resulted B<…> wrappers cancel, but (because the types are contravariant) the two parameters basically swap roles within the type-checking algorithm. The result is a type-checking problem that could potentially be more complex than the problem we started with; the operation effectively boils down to popping two stacks and then pushing onto one of them based on the value popped. You have to push onto the two stacks alternately, but that isn't a major issue, so we effectively end up with a two-stack machine, and two stacks are enough for Turing-completeness. Full details of how the language operates are in the link at the start of this section.

Minimizing the character set of The Subtyping Machine

Now that we have a Turing-complete operation that can be run by java, thus avoiding the need for the public static void main(String[] a) boilerplate that's required for the benefit of javac (but not java), the final step is to reduce its character set as far as possible.

There are some characters that are absolutely necessary. To use this technique, we need to be able to declare interfaces (interface … {}) and contravariant type parameters (<? super …>), which already ties up many of our nybbles. The main problem I encountered in this solution was in trying to avoid the nybble 8, most notably used by ( = U+0028 and x = U+0078. (1/a end up not being used for anything important, e.g. they're merged in @Poke's answer just as they are here; and 5 turns out to be used only for e=U+0065 and u=U+0075, but fortunately both those characters are needed for other reasons, e as nybble and u because it's part of the \u hexagraph introducer, so we never need to write them as hexagraphs. Unlike in the previous record-holder, c is unavoidable because we need it for <=U+003c, pretty much unavoidable for any type-system-based approach.)

Avoiding parentheses is a little annoying, but not that hard; in fact, I did it in the example program above. The reason they'd be helpful is that once we declare a bunch of interfaces extending each other, we actually need to cause the type checker to type-check something; Radu Grigore's original program did this by defining a function. The approach I used above works by defining two variables and assigning one to the other, which will also force the type-checker to be involved; fortunately, neither ==U+003d nor ;=U+003b uses a forbidden nybble.

Avoiding x is harder; despite being pretty rare as letters go, it's needed to spell extends, the keyword Java normally uses to introduce a subtyping relationship. That might at first seem impossible to avoid, but we do have an alternative; when a class extends an interface, Java uses the keyword implements instead, which despite being longer doesn't contain any problematic characters. So as long as we can divide our program into classes and interfaces, with the only hardcoded subtyping relationships being between a class and an interface, we can make the program work. (We also have to use the class keyword, but that contains only letters we already have: interface implements.) There are several possible approaches that work, but one simple approach is to ensure that classes and interfaces always alternate within the two types being compared; that means that at any point in time, we're always comparing a class with an interface (and because we unwrap both stacks one level at a time and the direction of a comparison is reversed with every step, we're always checking to see whether a class implements an interface rather than the other way round, which is impossible in Java).

My compiler from The Subtyping Machine to compile-time Java proves the Turing-completeness of this 15-character subset of Java by being capable of compiling to it; use the -jj option and it'll output in this subset, rather than in more readable Java (by doing things like choosing a class/interface split that avoids the use of the extends keyword – in a marginally more sophisticated way than is described above – and changing variable names to only use the letters that exist in the character set, and of course hexagraphing any character that needs to be).

I was hoping to produce a more complex example, but I've spent enough time on this as it is, so I thought I may as well post it. After all, it shaves one character off the best known character set via ridiculous means, and isn't that what this question is all about?

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.

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.

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.

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

Java 7, 18 17 characters

\bcdefu0123456789

All java source code can be reduced to unicode code points. "a" is not needed since it's only used for *:jJzZ. Asterisk is used for multiplication or block comments. Multiplication is just repeated addition and you can use single line comments instead (or just omit them). The colon is used for ternary operators, which you can use an if statement for instead, and foreach loops, which can be replaced with normal for loops. j and z aren't a part of any keywords in java.

Attempting to remove any other character requires us to add at least one of the characters required in Java boiler plate class a{public static void main(String[]a){}}. See below:

1 -> a (which has already been removed)
2 -> r (required for "String")
3 -> S (required for "String")
4 -> t (required for "static")
5 -> S (required for "String")
6 -> v (required for "void")
7 -> g (required for "String")
8 -> ( (required for "main(String[]a)"
9 -> i (required for "static")
b -> { (required for "class a{")
c -> l (required for "class")
d -> } (required for "(String[]a){}}")
e -> n (required for "main")
f -> o (required for "void")

Here's an example with a Hello World program Try it online!

Java 8, 16 characters

\bdefu0123456789

Thanks to ais523 for pointing this out. Java 8 allows interfaces to have static methods which means we can drop "c" because we don't need it for the "l" in "class". "c" is used for ,<lL\| so we do end up losing a bit more java functionality than when we removed "a" but we still have enough to be turing complete. Try it online!

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.

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)

///, 2 characters

/\

It was proven Turing Complete when someone wrote a Bitwise Cyclic Tag interpreter using it.

Shortened to 3 characters thanks to @Leo and @ETHproductions.

Shortened to 2 characters thanks to @ØrjanJohansen

PowerShell, 15 14 characters

+[char](1)|iex

Thanks to @Erik-the-Outgolfer for seeing that we don't need the " marks.

I'm reasonably confident this is the smallest set we can have. Similar to the Python answers, this constructs up a program one character at a time (via things like [char](1+1+1+1+1...+1+1) to get the appropriate ASCII value) and then evaluating the string via |iex. For example, here is an example program that is equivalent to "Test: "+(3+4). As a result, we can construct literally any PowerShell program with this method, and this is therefore Turing-Complete.

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.

J language, 7 char

To acheive Turing completeness, J can make do with the following 6 characters, plus space.

".u:1b

1b is a prefix for numbers meaning they are expressed in unary, so that e.g. 1b1111 1b11 is the array 4 2. This can represent every positive integer.

Then, u: converts ASCII character codes to characters, and ". evaluates a string as J code. This allows full access to the language.

Is this minimal?

Probably. What I have is pretty darn lean.

No proper subset of these characters is sufficient, though there are a couple of equivalent sets like do u:1b and ".1b {a.

J has no good facilities for doing something overly clever like embedding some lambda calculus or tag system, either, so I don't think a different strategy has a better shot, but I won't rule out the chance that I'm overlooking something sneaky.

PHP 7, 6 characters

'().;^

The idea is that it's possible to execute arbitrary code using the following construction:

('create_function')('','<code>')();

eval wouldn't work here, because it's a language construct and cannot be called using variable functions.

create_function and the code could be written as a concatenation of bitwise XORs of available characters:

(<char1_1>^<char1_2>^...).(<char2_1>^<char2_2>^...)...

Using ().;^ for <charX_Y>, we can get

()./:;<=JKLMXY^_bcdepqvw

and some unprintable characters. It's not enough, but now we can call 'eXp'() and get some numeric characters too:

''.'eXp'('eXp'('')) -> 1
''.'eXp'('eXp'('eXp'(''))) -> 2.718281828459
''.'eXp'('eXp'('eXp'('eXp'('eXp'(''))))) -> 3814279.1047602

It gives us 1, 2 and 3 (other characters will be ignored by XOR, if the other string is one character long). From ().;^123 we can now generate all the ASCII charset.

Try it online

ARM7 assembly - 8 bytes

CRS15,

And space and newline

With these characters, one can construct the following:

• Registers R1, R5, and R15 (R15 is the instruction pointer)
• The instruction RSC (Reverse Subtract with Carry)
• The condition code CC (do if carry clear)
• Any decimal number consisting of the numerals 1 and 5

These allow for data manipulation (subtract two registers), memory manipulation (specify destination as an address made up of 1s and 5s), and conditional jumping (R15 as the destination of a subtract with a condition code).

Comma, space, and newline are syntactic requirements of assemblers and cannot be avoided (in most cases).

One may be apt to point out that ARM does not have infinite pointers, and thus cannot be Turing complete. True, however no computer is Turing complete, and all of these languages are limited by their implementation. It is entirely possible to extend the ARM specification to allow for larger addresses. Ultimately, you'd have to let this one slide, and assume the best for the challenge.

Also, I admit to not knowing the minimum version of ARM this works in; I picked the one I know works

BitCycle, 8 characters

AB>/+~

plus space and newline.

My first demonstration of BitCycle's Turing-completeness was a Bitwise Cyclic Tag interpreter. But it turns out I can avoid quite a few extra characters by instead constructing a reduction, this time from a cyclic tag system.

Consider any cyclic tag system, which consists of an ordered list of productions: strings of 0's and 1's (possibly including the empty string). Encode it as a string of 0's, 1's, and semicolons, with a semicolon following each production. For instance, the example from the Esolangs article, with productions (011, 10, 101), would be represented as 011;10;101;. Then translate each element to a block of BitCycle instructions as follows:

0

    >>      ~ 
     +~ ~     
  > +         
    > ~       
        > A~  
B /    ~   >> 






   +   ~    ~ 

1

    >>      ~ 
     +~ /     
  > +         
    > ~       
      >   A~  
B /    ~   >> 






   +   ~    ~ 

;

    . 




B / > 






    . 

(The . characters here are placeholders and don't affect the function of the program. They should be replaced with spaces in the actual reduction.)

Concatenate these blocks side-by-side according to the three-character representation of the cyclic tag system. Then wrap the concatenation in this looping construct:

> ... ~

~     ~

where ... represents the rest of the program, the > is on the same line as the B collectors, and the ~ ~ don't have anything but spaces in between them.

To test this, insert a ? before the > in the wrapper and give the input string as a command-line argument. For example, here's the cyclic tag system 1;0;:

       >>      ~           >>      ~         
        +~ /                +~ ~             
     > +                 > +                 
       > ~                 > ~               
         >   A~                > A~          
?> B /    ~   >> B / > B /    ~   >> B / > > ~

 ~                                           ~

       1           ;       0           ;     


      +   ~    ~          +   ~    ~         

I will add a detailed explanation if people are interested--just leave a comment. Right now it's past my bedtime. :)

Java, 30 26 characters

 ()+-.0;=Sacdefgimnorstv{}

Taking a different approach from the other (more clever) Java answer, this one uses "regular" characters.

Java (like most languages) offers many facilities above and beyond what is required to be Turing-complete: basic arithmetic, jumps, and declaring variables (memory on the tape). The only types of jumps necessary are the simple if and for statements.

I started by writing a small program shell (main method), then adding statements that implement the bare minimum set that represents a Turing-complete subset of Java. I did so in a way that used the fewest characters possible, and came up with this:

interface S {

  static void main(String... s) {
    int r = 0;
    r++;
    int t = p;
    t--;
    if (t == 0) {
      r--;
    }
    for(;;) {
      t++;
      r++;
    }
  }
}

Removing all whitespace except for one space (0x20), sorting, and removing duplicates provides the string above.

These characters allow:

• if conditionals.
• Variable assignments.
• Comparing variables against each other and zero.
• for loops, including infinite loops (for(;;))
• Adding and subtracting arbitrary numbers via repeated unary increment and decrement.

In other words, I have reduced Java to a slightly more readable version of Brainfuck.

Python 2, 7 characters

exc="%\n

Any Python 2 program can be encoded using these 7 characters (\n is newline).

Constructing arbitrary strings

We can perform concatenation by repeatedly applying the substitution operator % on a single string. For example, if a=1, b=2, c=3, "%d%%d%%%%d" % a % b % c will give us the string "123". Luckily, the letters in exec give us access to %x and %c which are basically hex() and chr(). With %c, we can construct any string as long as we have the necessary numbers that represent the characters. We can then execute this string as python code using the exec keyword.

Make numbers

We can get access to 0 and 1 right off the bat with comparisons (==). Through a combination of concatenating digits and modulo, it is possible to construct the number 43 which represents + in ASCII. This allows us to construct the numbers we need for our code.

Putting it together

I omitted several details in this explanation as they are not essential in understanding how programs under these constraints can be written. Below is a Python 2 program I wrote that converts any python program into a functionally equivalent version that only uses these 7 characters. The techniques used are inspired by this submission on anarchy golf by k. Some simple tricks are also used to keep the size of the generated programs within reasonable limits.

import sys

var = {
    43: 'e',
    'prog': 'x', # the program will be stored in this variable
    'template': 'c',
    0: 'ee',
    1: 'ex',
    2: 'ec',
    4: 'xe',
    8: 'xx',
    16: 'xc',
    32: 'ce',
    64: 'cc',
    'data': 'cx', # source program will be encoded here
}

unpacker = 'exec"".join(chr(eval(c))for c in {}.split())'.format(var['data'])

source = sys.stdin.read()
charset = sorted(list(set(source+unpacker)))
codepoints = map(ord, charset)

output = (
    # create template for joining multiple characters
    '{}="%c%%c%%%%c%%%%%%%%c"\n'.format(var['template']) +

    # create 1
    '{0}={1}=={1}\n'.format(var[1], var['template']) +

    # create 0
    '{}={}==""\n'.format(var[0], var['template']) +

    # create 3
    # store it at var[43] temporarily
    (
        'exec"{0}=%x%%x"%{2}%{2}\n' +
        'exec"{0}%%%%%%%%=%x%%x%%%%x"%{1}%{2}%{1}\n'
    ).format(var[43], var[0], var[1]) +

    # create 4
    # this step overwrites the value stored at var[0]
    (
        'exec"{1}=%x%%x"%{0}%{1}\n' +
        'exec"{1}%%%%=%x%%x"%{2}%{0}\n'
    ).format(var[43], var[0], var[1]) +

    # create 43
    'exec"{0}=%x%%x"%{1}%{0}\n'.format(var[43], var[0])
)

# create powers of 2
for i in [2, 4, 8, 16, 32, 64]:
    output += 'exec"{0}={1}%c{1}"%{2}\n'.format(var[i], var[i/2], var[43])

for i, c in enumerate(codepoints):
    # skip if already aliased
    if c in var:
        continue

    # generate a new name for this variable
    var_name = ''
    if i < 27:
        for _ in range(3):
            var_name += 'exc'[i%3]
            i /= 3
    else:
        i -= 27
        for _ in range(4):
            var_name += 'exc'[i%3]
            i /= 3
    var[c] = var_name

    # decompose code point into powers of two
    rem = c
    pows = []
    while rem:
        pows.append(rem&-rem)
        rem -= rem&-rem

    # define this variable
    front = 'exec"{}={}'.format(var[c], var[pows.pop()])
    back = '"'
    for i, p in enumerate(pows):
        front += '%'*(2**i) + 'c' + var[p]
        back += '%' + var[43]
    output += front + back + '\n'

# initialise the unpacker
output += 'exec"""{}=""\n"""\n'.format(var['prog'])
i = 0
length = len(unpacker)
while i < length:
    if (length-i) % 4 == 0:
        # concat 4 characters at a time
        w, x, y, z = [var[ord(unpacker[i+j])] for j in range(4)]
        output += 'exec"{}%c={}%%{}%%{}%%{}%%{}"%{}\n'.format(var['prog'], 
                    var['template'], w, x, y, z, var[43])
        i += 4
    else:
        output += 'exec"""{}%c="%%c"%%{}"""%{}\n'.format(var['prog'],
                    var[ord(unpacker[i])], var[43])
        i += 1

# encode source data
output += var['data'] + '="""'
output += '\n'.join(var[ord(c)] for c in source)
output += '"""\n'

# execute the program
output += 'exec"exec%c{}"%{}'.format(var['prog'], var[32])

print output

Try it online

Haskell, 5 7 characters

()\->=;

As a functional language Haskell of course has lambdas, so simulating the lambda calculus is easy. The syntax for lambdas is (\variable->body)argument so we need at least the characters ()\->.
Additionally, we need an unlimited amount of variable symbols to be able to build arbitrary lambda expressions. Luckily we don't need any new characters for this, because (>), (>>), (>>>), ..., are all valid variable names. In fact every combination of \-> inside parenthesis is a valid variable name, with the exception of just \ and ->, which are reserved for lambda expressions, and --, which starts a line comment.

Examples:

• S = (\(>)(\\)(-)->(>)(-)((\\)(-))) types to (t2 -> t -> t1) -> (t2 -> t) -> t2 -> t1
• K = (\(>)(-)->(>)) types to t -> t1 -> t
• I = (\(>)->(>)) types to t -> t

Edit: However, as ais523 has pointed out in the comments, this construction implements typed lambda calculus, which by itself is not Turing-complete because it lacks the ability to enter infinite loops. To fix this, we need some function that performs recursion. So far we used unnamed lambdas, which can't call themselves, because, well, they don't have a name. So we have to add the characters = and ; to implement a fix function:

(>)=(\(-)->(-)((>)(-)));   -- equivalent to: f =(\ x -> x ( f  x ));

With this declaration our lambda calculus becomes Turing complete, however having added = and ;, we don't need lambdas anymore, as you can see in nimi's answer which uses just ()=;.

JavaScript (ES6), 5 characters

Thanks to @ETHproductions and @ATaco for helping with this; this was a group project, and although the original idea was mine, many of the details are theirs. See the chat discussion where this JavaScript subset was developed here.

[]+=`

It's fairly well established that any Javascript program can be written with the characters ([]()+!), but 5 characters is not enough. However, this isn't a challenge about writing arbitrary JavaScript. It's a challenge about writing a Turing-complete language, and using the fact that Turing-complete languages don't need access to the DOM, or even interactive I/O, it turns out that we can write a program with all the functionality required, even without any ability to run an eval or an equivalent.

Basic bootstrapping

JavaScript is very flexible with types. So for example, [] is an empty array, but +[] is 0, and []+[] is the null string. Notably, the fact that we can produce 0 with this character set makes it possible to simulate the effect of parentheses for grouping; (a) can be written as [a][+[]]. We can use this sort of trick to produce various characters using only +[]:

• [][+[]] is undefined (being the first element of an empty array); so
• []+[][+[]] is "undefined" (the stringification of undefined); so
• [[]+[][+[]]] is ["undefined"] (wrapping that in an array); so
• [[]+[][+[]]][+[]] is "undefined" (its first element); so
• [[]+[][+[]]][+[]][+[]] is "u" (its first letter).

u is one of the easiest characters to create, but similar techniques let us create a range of other characters. The same link as before gives us the following list of characters accessible with +[] (this is the same list as for +[](), excluding , because it's the only construction that uses parentheses for a purpose other than grouping/precedence):

0123456789acdefinotuvyIN (){}.

We can't spell very many useful words out of this set of characters (remember that this is the set of characters we can produce as strings; we don't get to execute them without some sort of eval). As such, we need another character. We'll use =, because it'll come in useful later, but for the time being, we'll use it to spell the comparison operator ==. That allows us to produce false and true, which can be stringified and indexed into, and immediately let us add lrs to the characters we can include into strings.

By far, the most important word that this lets us spell, that we couldn't before, is constructor. Now, JavaScript has a property access syntax that looks like this:

object.property

but you can also write it like this:

object["property"]

and nothing's preventing us using a calculated property, rather than a string literal. We can thus do something along the lines of

object["c"+"o"+"n"+"s"+"t"+"r"+"u"+"c"+"t"+"o"+"r"]

(with the letters generated as described above; the code quickly gets very long!); that's equivalent to object.constructor, which lets us access the constructors of arbitrary objects.

There are several tricks we can do with this. From the mundane to the fantastic:

• The constructor of an object is a function. Notably, it has a name, and that name is part of the stringification of the function. So for example, we can do [[]+[]][+[]]["constructor"] to get at the constructor for a string, whose name is String, and then stringify it to get at the capital S character. This expands our alphabet a bit, and we're going to need some of the new characters later.

• All arrays have the same constructor; []["constructor"] == []["constructor"] is true (unlike [] == [], which is false). This might seem minor, but it's very important, because it gives us a method of storing values persistently; we can set a random property on the constructor, and read it back later. (This is one of the reasons we're using = in particular, rather than one of the other ways to generate true and false.) For example, we can evaluate [[]["constructor"]["a"]=[]], and later on read []["constructor"]["a"] and get back the same array we stored there.

  This fulfils one of the requirements we need for Turing-completeness, the ability to store and retrieve arbitrary amounts of data. We can create a cons cell using a two-element array, taking values from our constructor-property storage, and then store it back in place of one of those values, letting us build up arbitrarily large data structures in memory; and we can access it this storage by doing the reverse, tearing it down piece by piece until the data we want becomes accessible. Reading is destructive, but that's acceptable because we have more than one place to store data, so we can copy it as we read it and then place the copy back in the original location.

• It allows us to get at the constructor for a function (there are plenty of functions we can access with our limited alphabet; []["find"], i.e. Array.find, is the most easily accessible, but there are others). Why is that useful? Well, we can actually use it for the intended purpose of a constructor, and construct functions! Unfortunately, with our character set, we can't pass the Function constructor a computed string. However, the use of ` does let us pass it a string literal (e.g. []["find"]["constructor"]`function body goes here`); this means that we can define custom values of function type with any behaviour when executed, so long as we can express that behaviour entirely using []+=. For example, []["find"]["constructor"]`[]+[]` is a fairly boring function that computes the null string, discards it, and exits; that function isn't useful, but more complex ones will be. Note that although the functions can't take parameters or return values, those aren't problems in practice as we can use the constructor-property storage to communicate from one function to another. Another restriction is that we can't use ` in the body of a function.

  Now, we can define custom functions, but what's holding us back at this point is the difficulty we have in calling them. At the top level of the program, we can call a function with ``, but being able to call functions only from the top level doesn't let us do any sort of loop. Rather, we need functions to be able to call each other.

  We accomplish this with a rather nifty trick. Remember the capital S we generated earlier? That lets us spell "toString". We aren't going to call it; we can convert things to strings by adding [] to them. Rather, we're going to replace it. We can use constructor storage to define persistent arrays that stick around. We can then assign our created functions to the arrays' toString methods, and those assignments will also stick around. Now, all we have to do is a simple +[] on the array, and suddenly, our custom-defined function will run. This means that we can use the characters +=[] to call functions, and therefore our functions can call each other – or themselves. This gives us recursion, which gives us loops, and suddenly we have everything we need for Turing-completeness.

Here's a rundown of a set of features that gives Turing-completeness, and how they're implemented:

• Unbounded storage: nested arrays in constructor storage
• Control flow: implemented using if and recursion:
  • if: convert a boolean into a number, and index into a 2-element array; one element runs the function for the then case when stringified, the other element runs the function for the else case when stringified
  • Recursion: stringify an appropriate element of the constructor storage
• Command sequencing: [a]+[b]+[c] evaluates a, b, and c left-to-right (at least on the browser I checked)

Unfortunately, this is fairly impractical; not only is it hugely large given that strings have to be constructed character-by-character from first principles, it also has no way to do I/O (which is not required to be Turing-complete). However, if it terminates, it's at least possible to look in the constructor storage manually afterwards, so it's not impossible to debug your programs, and they aren't completely noncommunicative.

tinylisp, 5 characters

(q d)

Using only the macros def and quote, we can implement the S and K combinators, which are Turing-complete. (Thanks to Qwerp-Derp for the inspiration.) Here it is all on one line:

(d dd (q (qq qq)))  (d dq (q ((qq) (dd (q (qqq)) (dd (q q) qq)))))  (d dqq (q ((qq) (dd (q (qqq)) (dd (q dqqd) (dd (q q) qq) (q qqq))))))  (d dqqd (q ((qq qqq) (dd (q (qqqq)) (dd (dd (dd (q q) qq) (q qqqq)) (dd (dd (q q) qqq) (q qqqq)))))))

The functions dq and dqq are the K and S combinators, respectively. They expect their arguments curried: i.e., for SKK you have to do ((dqq dq) dq), not (dqq dq dq). dd is a helper function that makes a list out of its arguments (a reimplementation of the list function in the standard library). dqqd is a partially curried helper function for dqq that takes arguments f and g (as opposed to dqq that takes only f).

Try it online! (with some test cases that implement the I combinator and the argument-reversing combinator S(K(SI))K).

A more readable version

(load lib/utilities)

(def K
 (lambda (x)
  (list (q (y)) (list (q q) x))))

(def S
 (lambda (f)
  (list (q (g)) (list (q S2) (list (q q) f) (q g)))))

(def S2
 (lambda (f g)
  (list (q (x)) (list (q S3) (list (q q) f) (list (q q) g) (q x)))))

(def S3
 (lambda (f g x)
  ((f x)
   (g x))))

Functions in tinylisp are simply lists with two elements: the parameters and the function body. For example, the function ((y) (q (1 2 3))) takes one argument, y, and returns the list (1 2 3) (which had to be quoted to prevent evaluation). So to return this function from another function, we only need to build the correct list. This is what K does. If we pass the list (1 2 3) to K, it is bound to K's parameter x, and we get:

(list (q q) x) -> literal q followed by value of x -> (q (1 2 3))
(list (q (y)) ...) -> literal (y) followed by the above -> ((y) (q (1 2 3)))

which is a function that takes one argument and always returns (1 2 3), as desired.

S and its helper functions work the same way. Passing func1 to S returns the list/function

((g) (S2 (q func1) g))

Passing func1 and func2 to S2 returns the list/function

((x) (S3 (q func1) (q func2) x))

And finally, passing func1, func2, and arg to S3 evaluates

((func1 arg) (func2 arg))

which implements the S-combinator.

To get from this more-readable form to the 5-character version, we replace the library macro lambda with the direct method of defining functions as lists: (lambda (x) (expr)) -> (q ((x) (expr))). We also reimplement list and call it dd:

(d dd    Define dd
 (q      to be this list (which acts as a lambda function):
  (qq     Take a list of variadic args qq
   qq)))  and return the arglist

Then it's just a matter of renaming all the functions and arguments to use only ds and qs.

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.

Mathematica, 5 4 characters

I[]

 is a private-use Unicode character, which acts as an operator for Function that lets you write literals for unnamed functions with named arguments. The character looks a lot like ↦ in Mathematica, so I'll be using that one for the rest of this answer for clarity.

Using these, we can implement the S, K and I combinators of combinatory logic:

I -> II↦II
K -> II↦III↦II
S -> II↦III↦IIII↦II[IIII][III[IIII]]

One syntactic issue with these is that ↦ has very low precedence which will be a problem if we try to pass arguments to these combinators. You would normally fix that by wrapping a combinator C in parentheses like (C), but we don't have parentheses. However, we can use I and [] to wrap C in some other magic that has sufficiently high precedence that we can use it later on:

I[C][[I[[]]I]]

Finally, to write an application A x y z (where A is a combinator "parenthesised" as shown above, and x,y,z may or may not be parenthesised, or may be bigger expressions), we can write:

A[x][y][z]

That leaves the question of how the parenthesis-equivalent actually works. I'll try to explain it roughly in the order I came up with it.

So the thing we have syntactically to group something is the brackets []. Brackets appear in two ways in Mathematica. Either as function invocations f[x], or as an indexing operator f[[i]] (which is really just shorthand for Part[f, i]). In particular that means that neither [C] nor [[C]] is valid syntax. We need something in front of it. That can in theory be anything. If we use the I we already have we can get I[C] for instance. This remains unevaluated, because I isn't a unary function (it's not a function at all).

But now we need some way to extract C again, because otherwise it won't actually be evaluated when we try to pass an argument x to it.

This is where it comes in handy that f[[i]] can be used for arbitrary expressions f, not just lists. Assuming that f itself is of the form head[val1,...,valn], then f[[0]] gives head, f[[1]] gives val1, f[[-1]] gives valn and so on. So we need to get either 1 or -1 to extract the C again, because either I[C][[1]] or I[C][[-1]] evaluates to C.

We can get 1 from an arbitrary undefined symbol like x, but to do that, we'd need another character for division (x/x gives 1 for undefined x). Multiplication is the only arithmetic operation which we can perform without any additional characters (in principle), so we need some value that can be multiplied up to give -1 or 1. This ends up being the reason why I've specifically chosen I for our identifiers. Because I by itself is Mathematica's built-in symbol for the imaginary unit.

But that leaves one final problem: how do we actually multiply I by itself? We can't just write II because that gets parsed as a single symbol. We need to separate these tokens without a) changing their value and b) using any new characters.

The final bit of a magic is a piece of undocumented behaviour: f[[]] (or equivalently Part[f]) is valid syntax and returns f itself. So instead of multiplying I by I, we multiply I[[]] by I. Inserting the brackets causes Mathematica to look for a new token afterwards, and I[[]]I evaluates to -1 as required. And that's how we end up with I[C][[I[[]]I]].

Note that we couldn't have use I[]. This is an argumentless invocation of the function I, but as I said before I isn't a function, so this will remain unevaluated.

Unlambda, 3 characters

sk`

It's a turing tarpit of course.

Tildehyph, 2 characters

~-

The language uses only two characters a tilde and a hyphen. The easy answer why Tildehyph is Turing-complete is the fact that there is a Brainfuck interpreter created in it and Brainfuck is proven to be Turing-complete.

Nock, 6 characters

[ ]012

Nock is a minimal virtual machine based on combinator reduction. It's memory model is a binary tree of bignums, and the spec gzips to 340 bytes. There's a trivial transformation from Nock operations to the SKI combinators, which I stole from the Urbit examples library (which seems to originate from this reddit discussion):

S = [[1 1 2] [1 0 1] [1 1] 0 1]
K = [[1 1] 0 1]
I = [0 1]

A more interesting way to do this would be to re-compile Nock with the Nock 4 operator, which is increment, to create the other operators. [4 1 1] is 2, [4 4 1 1] is 3, etc. S could alternatively be defined [[1 4 1 1] [1 0 1] [1 1] 0 1], for example. I think that you still need a non-synthesized 2 operator in order to apply functions and reduce the 4, though.

Befunge-98, 3 characters

As far as I know, Befunge-98 is supposed to be turing complete, so we just need to show how any Befunge-98 program can be generated using just three characters. My initial solution relied on the following four characters:

01+p

We can get any positive integer onto the stack by adding multiple 1 values together with the + command, and for zero we simply use 0. Once we have the ability to push any number we want, we can then use the p (put) command to write any ASCII value to any location in the Befunge playfield.

However, as Sp3000 pointed out, you can actually get by with just the three characters:

1-p

Any negative number can be calculated by starting with 1 and then repeatedly subtracting 1 (for example, -3 would be 11-1-1-1-). Then any positive number can be represented by subtracting 1-n from 1, where 1-n is a negative number which we already know how to handle (for example, 4 = 1-(-3), which would be 111-1-1-1--).

We can thus use our three characters to write a kind of bootloader that slowly generates the actual code we want to execute. Once this loader is finished executing, it will wrap around to the start of the first line of the playfield, which should at that point hold the start of our newly generated code.

As an example, here's a bootloader that generates the Befunge code necessary to sum 2+2 and output the result: 22+.@

And for a slightly more complicated example, this is "Hello World": "!dlroW olleH"bk,@

APL, 9 characters

⍎⎕UCS(≢⍬)

Why this is Turing-complete:

• ≢ is length, ⍬ is the empty list, and a list can be expressed simply by naming its elements, i.e. ⍬⍬⍬ is a list of three empty lists. This way, all numbers can be formed. ≢⍬ is 0, ≢≢⍬ is 1, and from then on ≢⍬⍬⍬... is N, where N is the amount of ⍬s.
• () are used to change evaluation order. List construction works with anything, so this way (≢⍬)(≢⍬⍬)(≢⍬⍬⍬) evaluates to [0,2,3].
• ⎕UCS gives a string of Unicode characters given a list of numbers. We can now generate any text we want.
• ⍎ is evaluate.

Brain-Flak, 6 characters

(){}[]

Brain-Flak is a minimalist language with only 8 available characters. However it can be proven that there exists a subset of Brain-Flak that is also Turing complete using only 6 characters.

First thing we will do is implement a Minsky Machine with only one stack of Brain-Flak. If we can prove that a Minsky Machine is possible with only one stack we can show that Brain-Flak is Turing complete without the <> and [] nilads. This wont save any characters immediately but will in the future when we show that <...> is not necessary.

A Minsky Machine is a type of Turing complete automaton that has a finite number of unbounded registers and two instrutions:

• Increment the a register

• If non-zero decrement otherwise transition to a specified instruction

To set up a goto structure in Brain-Flak we can use the following snippet:

(({}[()])[(())]()){(([({}{})]{}))}{}{(([({}{}(%s))]{}))}{}

This will decrement the counter and run %s if zero. A bunch of these chained together will allow us to put a number on the stack that will indicate which line we want to goto. Each of these will decrement the top of the stack but only one of them will actually run the code.

We use this as a wrapper for all of our Minsky Machine instructions.

Incrementing a particular register is pretty easy without switching the stack. It can be achieved with this string formula:

"({}<"*n+"({}())"+">)"*n

For example to increment the 3rd register we would write the following code:

({}<({}<({}<({}())>)>)>)

Now we just have to implement the second operation. Checking if a number is zero is pretty simple in Brain-Flak:

(({})){(<{}%s>)}{}

will only execute %s if the TOS is zero. Thus we can make our second operation.

Since Minsky Machines are Turing complete Brain-Flak is also Turing complete without the use of the <> and [] operations.

However we have not reduced the number of characters yet because <...> and [...] are still in use. This can be remedied with simple substitution. Since <...> is actually equivalent to [(...)]{} in all cases. Thus Brain-Flak is Turing complete without the use of the < and > characters (plus all the no-ops).

Haskell, 4 chars

()=;

With ()= we are able to define S, K and I. The definitions must be separated by either ; or a NL.

We define (==) as S (the second line shows a more readable version):

((=====)==(======))(=======)=(=====)(=======)((======)(=======))
( a     == b      ) c       = a      c       ( b       c       )

(===) as K:

(=====)===(======)=(=====)
 a     === b      = a

and (====) as I:

(====)(=====)=(=====)
(====) a     = a 

Luckily (==), (===), (====), etc. are valid function/parameter names.

As @ais523 points out, SKI isn't enough in a strongly typed language like Haskell, so we need to add a fixpoint combinator (=====):

(=====)(======)=(======)((=====)(======))
(=====) f      = f      ((=====) f      )

Stack-based concatenative languages, 4 characters

Underload

():^

GolfScript

{}.~

CJam

{}_~

GS2

• backspace, tab, @, space (I knew GS2 used unprintables a lot, but this is ridiculous…)

dc (suggested by @seshoumara)

[]dx

Underload has been proven Turing-complete with only the use of ():^ (thanks to Esolang's resident mathematician Ørjan). The proof is far too long to explain here, but if you're interested, you can read about it here.

The commands in question are () (place code literal on the stack), : (duplicate top stack element), and ^ (evaluate top of stack). These commands are fairly common in stack-based languages (especially concatenative languages), and so I've given something of a collection of them above; these languages are all Turing-complete in 4 characters for the same reason as Underload.

><>, 3 characters

><> is doable in 3 with 1p-, which do:

1          Push 1
p          Pop y, x, c and put the char c in cell (x, y) of the codebox
-          Subtraction: pop y, x and push x-y

p provides reflection, modifying the 2D source code by placing chars into the codebox. With 1-, you can push any number onto the stack since 1- subtracts one and 111-1-- (x-(1-1-1) = x+1) adds one.

Once all the 1p- commands have executed, the instruction pointer wraps around, allowing it to execute the "real" code.

An example program that calculates the Fibonacci numbers (from this answer) is:

111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11-11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1--11-p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11-1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--11p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1-1--1p111-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1--111-1-1-1-1-1-1-1-1-1-1-1-1-1-1--1p

Try it online! Once all the 1p- commands have executed, the codebox looks like this:

01aa+v1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1- ...
@+&1->:?!;&:nao:

Barring everything after the v on the first line, this is a standard Fibonacci ><> program.

Ruby, 8 chars

eval"<1+

Inspired by the Python answers

How it works

• eval can be used to execute an arbitrary string.
• "<1+ is the minimum set of characters required to build any string

A string in ruby can be built using the empty string as a starting point, and appending ascii characters to it, so for example:

eval ""<<111+1<<11+11+11+1<<111<<11+11+11+1

is actually equivalent to

eval ""<<112<<34<<111<<34

which evaluates the string

p"o"

bash, 9 characters

01456\$ '

Bash has a syntax $'\nnn' for entering characters with their octal ascii values. We can enter the eval command in this format as $'\145\166\141\154'. We first turn the desired result into its octal values. We then convert any octal values using digits other than 0, 1, 4, 5, and 6 into expressions evaluating to said octal values using $(()) and subtraction, appending an eval to the front. In our final step, we add another eval and convert the parentheses and minus sign into their octal values. Using this method we can execute any bash command, so this subset is turing complete.

Example:

dc becomes

$'\144\143' which becomes

$'\145\166\141\154' \$\'\\144\\$((144-1))\' which becomes

$'\145\166\141\154' $'\145\166\141\154' $'\$\\\'\\\\144\\\\$\050\050144\0551\051\051\\\''

Retina, 3 characters

{`

and newline.

First off, we need newline to be able to do substitutions (necessary unless we want to fit the whole program into one regex, which would need more characters); and ` and { are the least character-intensive way to do loops. It turns out we don't need anything else.

Our target language to implement is a deterministic variant of Thue (the nondeterminism isn't necessary for Turing-completeness; it's possible to write a Thue program to work correctly regardless of which evaluation order is used). The basic idea is to compile pattern::=replacement into

`pattern
replacement

(which is a direct Retina translation of the Thue; alternatively, if you know Retina but not Thue, you can use it as a method of learning how Thue works); as an exception, the very first pattern is preceded by {` instead (in order to place the entire program into a loop; Thue programs continue running until no more substitutions are possible, and this causes the Retina to work the same way).

Of course, this means that we need to prove Thue Turing-complete with just { and ` in the patterns and replacement, but that's simple enough; we replace a character with ascii code n with `, n+1 {, and another `. It's clearly impossible for a pattern to match anywhere but at character boundaries, so this will end up doing the same thing as the original program.

Brachylog, 5 characters

~×₁↰|

This subset of characters allows us to implement a version of Fractran in which the only numbers that can appear are products of repunits (i.e. products of numbers that can be written in decimal using only the digit 1). ~× (with an integer as subscript) divides the current value by that integer, but only if it divides exactly (otherwise it "fails" and looks for another case to run; | separates the cases). × lets us multiply by an integer. So using ~×₁| we can implement one step of a Fractran execution. Then ↰ lets us recurse, running the whole program again on the new current value. Here's an example of a very simple Fractran program (11111111111111111111111/111) translated to Brachylog.

So is this Turing complete? All we need to make Fractran Turing complete is a sufficiently large quantity of prime numbers (enough to write an interpreter for a Turing complete language in Fractran itself). There are five proven and four suspected repunit primes, in addition to, quite possibly, ones that haven't been discovered yet. That's actually more than we need in this case. The program checks the possibilities left to right, so we can use one prime as an instruction pointer, and two more as counters, demonstrating Turing completeness with only three primes (a good thing too, because it lets us use the repunits with 2, 19, and 23 digits, without having to resort to the proven-but-annoyingly-large repunits with 317 or 1031 digits, which would make the source code fairly hard to write). That makes it possible to implement a Minsky machine with two counters (enough for Turing-completeness).

Here's how the compilation works specifically. We'll use the following two commands for our Minsky machine implementation (this is known Turing complete), and each command will have an integer as a label:

• Label L: If counter {A or B} is zero, goto X. Otherwise decrement it and goto Y.
• Label L: Increment counter {A or B}, then goto Z.

We choose which command to run via placing powers of 11 in the denominator, highest powers first; the exponent of 11 is the label of the command. That way, the first fraction that matches will be the currently executing command (because the previous ones can't divide by all those 11s). In the case of a decrement command, we also place a factor of 1111111111111111111 or 11111111111111111111111 in the denominator, for counter A or B respectively, and follow it up with another command without that factor; the "decrement" case will be implemented by the first command, the "zero" case by the second. Meanwhile, the "goto" will be handled by an appropriate power of 11 in the numerator, and "increment" via a factor of 1111111111111111111 or 11111111111111111111111 in the numerator. That gives us all the functionality we need for our Minsky machine, proving the language Turing complete.

OCaml, 9 characters

fun->()`X

These characters are sufficient to implement the SKI Combinator Calculus in OCaml. Notably we are able to avoid the use of space with sufficient parenthesis. Unfortunately lambda expressions in OCaml require the fun keyword so a more terse solution is not possible. The same letters can be used to build arbitrary variable names if more complex lambda expressions are desired however.

S Combinator:

fun(f)(u)(n)->f(n)(u(n)) with type ('a -> 'b -> 'c) -> ('a -> 'b) -> 'a -> 'c

K Combinator:

fun(f)(u)->u with type 'a -> 'b -> 'b

I Combinator:

fun(f)->f with type 'a -> 'a

As noted by ais523 it is insufficient to simply encode SKI. Here is an encoding for Z using polymorphic variants to manipulate the type system. With this my subset should be turing complete.

Z Combinator:

fun(f)->(fun(`X(x))->(x)(`X(x)))(`X(fun(`X(x))y->f(x(`X(x)))y))

with type (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b

Incident, 2 characters

It doesn't matter which two characters you pick, either; any combination of two octets is Turing-complete in Incident.

Actually proving this is much more difficult than you might expect, and at the time of writing, the discussion page on Esolang about Incident is devoted to the problem. I'll try to give a summary of the simplest known proof below, though.

Before the proof, some background. Incident infers the tokens used in the program by looking at the source (a token is a string that appears exactly three times in the source, isn't a substring of another token, and doesn't overlap with another potential token). As such, any program can be converted to use pretty much any character set by changing what the tokens are; the language is Turing-complete (and has completeness for I/O, too!), despite being incredibly difficult to program in, so "all" you need is a method of encoding tokens so that they work with just two characters.

And now, here's a summary of the proof (which was found by Ørjan, Esolang's resident mathematician). The idea is that we encode a token using two copies of one character (say 1) in a large sea of the other character (say 0). The distance between the 1s differs for each token, but is always a multiple of 4. Then for the padding between the tokens, we use an extra list of 0s with a 1 in the middle, but the number of 0s on each side of the 1 is not a multiple of 4, but rather a number unique to that particular incidence of the program that doesn't appear elsewhere in the program. That means that each 1…1 within the padding can only ever appear twice, so won't be part of a token; each intended token contains exactly two 1s, and no bogus token can contain more than one 1. Then we just add some padding to the side to remove all possible tokens containing one 1 or zero 1s by adding at least four copies of them.

Stacked, 5 chars

{!n:}

This is surprisingly short. If Stacked can implement each of the SKI combinations, then it is Turing Complete. Recap:

• I combinator - the identity function. x -> x
• K combinator - the constant function. x -> y -> x
• S combinator - the substitution function. (x, y, z) -> x(z)(y(z))

I combinator: {!n}

Now, for the stacked specifics. {! ... } is an n-lambda. It is a unary function whose argument is implicitly n. Then, the last expression is returned from the function. Thus, {!n} is a function that takes an argument n and yields n.

K combinator: {!{:n}}

Now, {:...} is a function that takes no arguments, and returns .... Combining this with our n-lambda formation, we get (adding whitespace for clarity):

{! { : n } }
{!         }   n-lambda. arguments: (n)
   { : n }     lambda.   arguments: ()
       n       yields n.

S Combinator: {n!nn!nnn:nnn{!n}!nn!nnn{!n}!n!!}

Ok, this looks a little more complicated. So, a lambda takes arguments, separated by non-identifier characters. Thus, the lambda in the header is equivalent to:

{n nn nnn:nnn{!n}!nn!nnn{!n}!n!!}

This is a lambda that takes three arguments, n, nn, and nnn. Let's replace these with x, y, and z for clarity:

{x y z:z{!n}!y!z{!n}!x!!}

The two {!n}! are just identity function to again avoid whitespace, where ! means "execute". So, again, reducing:

{x y z:z y!z x!!}

With an explanation:

{x y z:z y!z x!!}
{x y z:         }  three arguments
       z y!        apply `y` to `z` -- `y(z)`
           z x!    apply `x` to `z` -- `x(z)`
               !   apply `x(z)` to `y(z)` -- `x(z)(y(z))`

And therefore, this is the S combinator.

Pyke, 5 characters

0h.CE

This is capable of producing an infinitely large number, turning it into a string and then evaluating it as Pyke code.

Explanation of the code:

0 - Add 0 to the stack. This is required to start a number

h - Increment the number before. By repeating this an arbitrary amount of times, you can create numbers that are infinitely big. Pyke supports bignums as it is written in Python, which uses them as a default.

.C - Turn a number into a string using the following algorithm: (Github link)

def to_string(num):
    string = ""
    while num > 256:
        num, new = divmod(num, 256)
        string = chr(new) + string
    string = chr(num) + string
    return string

By this point, we can create an arbitrary amount of strings and natural numbers in Pyke with arbitrary values. Numbers can be created in the form corresponding to the regex 0(h)* and strings can be created with 0(h)*.C. They can be interweaved with each other to create an arbitrary mixture of strings and integers.

E - evaluate a string as Pyke code. This uses the same environment as the Pyke code already running so will share things like the input.

Attempted proof that Pyke is Turing Complete.

One of the simplest ways of showing a language is turing complete is by implementing Brainf*ck in it. This is probably much harder in Pyke than many other languages because it's list and dictionary operations are pretty much non-existent due to the lack of needing them in the area Pyke is designed to run in: code-golf.

Firstly we create an interpreter for brainf*ck and encode it using our algorithm above to create a number and then express that number with 0 and h. We then create the string containing the code to be ran in exactly the same way. If we were to leave it at that, we would have the stack as

string containing brainf*ck code
string containing brainf*ck interpreter

This means the code has to be in the opposite form as the Pyke stack is first in last out.

Now for the fun part: the brainf*ck interpreter with a whopping 216 bytes!

Q~B"><ht.,".:=B;Z]1=L;W~Bo@D=c"ht"{I~c~LZ@EZ]1~LR3:=L)~c\,qIz.oZ]1~LR3:=L)~c\.qI~LZ@.CpK)~c"<>"{I~c"<>""th".:ZE=ZZ1_qI0=Z~L0"":0]10:=L)Z~LlqI~L~Ll"":1_]10:=L))~c\[qI~LZ@0qI\]~B~o>@~o+h=o))~c\]qI~o\[~B~o<_@-t=o)~o~BlN

Try it here!

If you want to try the code in semi-completed but editable form, try it here!

To convert from a string into a number, you can use the following Python code:

def conv(string, t=0):
    t *= 256
    t += ord(string[0])
    if len(string) != 1:
        return conv(string[1:], t)
    return t

The (almost) final solution can be tried here!

Explanation of Brainf*ck interpreter

First lets separate the program into parts:

• The initialisation:

​

Q~B"><ht.,".:=B;Z]1=L; - The initialisation part
Q~B"><ht.,".:          - input.replace("><+-.,[]", "><ht.,")
                       - replace the characters in brainf*ck with some modified ones. 
                       - this means we can `eval` the add and subtract bits easily.
             =B;       - set `B` to this.
                       - The `B` variable contains the instructions
                Z]1=L; - set `L` to [0]
                       - `L` contains the stack, initialised with 0

• The main loop: ​​ ​ ​

​​ ​ ​

W~Bo@D=c !code! ~o~BlN - The main loop
W                      - do
 ~Bo@D=c               -  c=B[o++]
                       -  the c variable is used to store the current character.
                ~o~BlN - while
                ~o     -   o 
                     N -  ^ != V 
                  ~Bl  -   len(B)
                       -  this stops the program running once it's finished.

• The instructions
  • Increment/Decrement: +- ​​ ​ ​

​​ ​ ​

"ht"{I~c~LZ@EZ]1~LR3:=L) - The bit that does incrementing and decrementing
"ht"{I                 ) - if c in "ht"
        ~LZ@             -  L[Z]
                         -  `Z` contains the current stack pointer
      ~c    E            -  eval current character with ^ as an argument
                         -  returns the contents of `Z` either incremented or decremented
             Z]1~LR3:=L  - L[Z] = ^

• Input: ,: ​​ ​ ​

​​ ​ ​

~c\,qIz.oZ]1~LR3:=L) - The code for output 
~c\,qI             ) -  if character == ",":
      z.o            -    ord(input)
         Z]1~LR3:=L  -   L[Z] = ^

• Output: .: ​​ ​ ​

​​ ​ ​

~c\.qI~LZ@.CpK) - The code for input 
~c\.qI        ) - if c == ".":
      ~LZ@      -    L[Z]
          .C    -   chr(^)
            pK  -  print(^)

• Shift Left/Right: <>: ​​ ​ ​

​​ ​ ​

~c"<>"{I~c"<>""th".:ZE=Z - main part 
~c"<>"{I                 - if "<>" in c:
        ~c"<>""th".:     -  c.replace("<>", "th")
                    ZE=Z -  Z = eval(char, Z)

Z1_qI0=Z~L0"":0]10:=L) - lower bound check
Z1_qI                ) - if Z == -1:
     0=Z               -  Z = 0
        ~L0"":         -  L.insert("", 0)
              0]10:=L  -  L[0] = 0

Z~LlqI~L~Ll"":1_]10:=L) - upper bound check
Z~LlqI                ) - if Z == len(L):
        ~Ll"":          -  L.insert("", len(L))
      ~L      1_]10:=L  -  L[-1] = 0

• The conditionals: [: ​​ ​ ​

​​ ​ ​

~c\[qI~LZ@0qI\]~B~o>@~o+h=o)) - Code for `[`
~c\[qI                      ) - if c == "[":
      ~LZ@0qI              )  -  if L[Z] == 0:
               ~B~o>          -     B[o:]
             \]     @         -    ^.find("]")
                     ~o+h=o   -   o = o + ^ + 1

- And ]: ​​ ​ ​

​​ ​ ​

~c\]qI~o\[~B~o<_@-t=o) - Code for `]`
~c\]qI               ) - if c == "]":
          ~B~o<_       -    reversed(B[:o])
        \[      @      -   ^.find("[")
      ~o         -t=o  -  o = o - ^ -1

Python 2, 8 characters

exc'%~-0

These characters allow the translation/execution of any Python program using format strings and exec. Though being able to translate any program isn't required for Turing-completeness, this is the fewest characters I know that make it TC anyway. That it's so powerful is just a bonus.

A double quotation mark as well as any single digit besides zero could also be used. (Now that I think about it, 1 would definitely be better, resulting in shorter programs, since you could use 1, 11, and 111, as well.)

Here is the program print:

exec'%c%%c%%%%c%%%%%%%%c%%%%%%%%%%%%%%%%c'%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0%-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~0

Try it online

The base program requires

exec''

Each character x added to the program requires (char - count):

• % - 2**(n-1)
• c - 1
• - - ord(x)*2
• ~ - ord(x)*2
• 0 - 1

The exception to this is that certain optimizations/shortcuts could be taken to make the encoded program shorter, such as using %'0' for the character 0 instead of 48 -~, etc.

Practical uses (AKA golfing): I used this tactic to solve this challenge without using an additional handicap character.

Credit for the character list and an encoder program: here

For information on finding a lower bound on the resulting program size (without optimizations), see this comment.

The number of bytes required goes up O(2**n), so this method is not recommended for golfing. A quine using this source restriction would be insanely long.

Retina, 6 characters

$%`{¶

As well as linefeeds (0x0A).

On one hand I'm surprised that I was able to get it this low. On the other hand, I'm very unhappy with the inclusion of %¶. Each of $`{ is reused for two or even three purposes, but %¶ together serve only one purpose. That makes them seem rather wasteful and slightly destroys the elegance of the approach. I hope that there's a way to beat this construction.

On to the proof. I'm going to describe a simple way to translate cyclic tag systems to Retina using the above characters.

First off, we'll be using ` and { for the binary alphabet instead of 0 and 1. These are convenient, because they don't need to be escaped in a regex, but they have meaning either for Retina or in substitution syntax. I'm using ` for 0 and { for 1, but this choice is arbitrary. Furthermore, we're going to reverse the string (and the productions) in memory, because working with the last character lets us use $ and $` instead of ^ and $', maximising character reuse.

If the initial word is denoted by S and the ith (reversed) production is called pi, the resulting program will look like this:

S
{`

{$
¶p1$%``
``$

{$
¶p2$%``
``$

{$
¶p3$%``
``$

...

This construction inevitably grows in memory each time a production is applied, and it is unlikely to terminate – in fact, at the point where the cyclic tag system would terminate (when the working string becomes empty), the behaviour of the resulting Retina program becomes basically undefined.

Let's look at what the program does:

S

We start by initialising the working string to the initial word.

{`

This wraps the remainder of the program in a that runs until it fails to change the resulting string (hey, naive built-in infinite-loop detection for free...). The two linefeed there aren't really necessary, but they separate the loop more clearly from the individual productions. The rest of the program goes through each of the productions, and due to the loop we're effectively processing them cyclically over and and over.

Each production is processed by two stages. First we deal with the case that the leading (or in our case trailing) symbol is {, in which case we use the production:

{$
¶pi$%``

The regex only matches if the string ends in {. If that is the case, we replace it with:

• A linefeed (¶). We'll only ever be working with the last line of the working string, so this effectively discards the working string so far (which is why the memory usage of the program will grow and grow).
• The current production (pi), which we're hereby prepending to the working string (where the cyclic tag system appends it).
• The previous remaining working string ($%`). This is why we need to insert the ¶: $%` picks up everything left of the match, but only on the same line. Hence, this doesn't see all the junk we've left from earlier productions. This trick lets us match something at the end of the working string to insert something at the beginning of the working string, without having to use something like (.+) and $1 which would significantly blow up the number of characters we need.
• A single backtick (`). This effectively replaces the { (1-symbol) we matched with a ` (0-symbol) so that the next stage doesn't need to know whether we already processed the current production or not.

The second part of each production is then the trivial case where the production is skipped:

``$

We simply delete a trailing `. The reason we need two ` on the first line is that Retina considers the first backtick to be the divider between configuration and regex. This simply gives it an empty configuration so that we can use backticks in the regex itself.

vim, 9 8 7 6 characters

<C-v><esc>1@ad

We can build and execute an arbitrary vimscript program as follows:

1. Use the sequence aa<C-v><C-v>1<esc>dd@1<esc>dddd to obtain a <C-a> in register 1.

2. Enter insert mode with a, then insert an a, which will be used to re-enter insert mode in a macro later.

3. For each character in the desired vimscript program,

   1. use <C-v><C-v>1<esc> to insert the literal sequence <C-v>1,

   2. use @1 (which is <C-a><cr>, in which the final <cr> is a no-op due to being on the last line) as many times as necessary to increment the 1 until the ASCII value of the desired character is reached,

   3. and re-enter insert mode with a.

4. Delete the line (along with a trailing newline) into the 1 register with <esc>dd.

5. Execute the result as vim keystrokes by using @1, then <esc>dd to delete the line entered by the trailing newline from the previous step.

6. Run the resulting arbitrary sequence of bytes with dd@1. If it begins with a :, it will be interpreted as vimscript code, and it will be run due to the trailing newline from dd.

I'm not convinced this is a minimal character set, but it's quite easy to prove to be Turing-complete.

Python 3, 9 characters

exc('%1+)

See my Python 2 answer for a basic explanation. This answer builds on that one.

Instead of simply using the same characters as Python two with the addition of (), we are able to drop a character since we now have the use of parentheses. Programs will still have the basic shape of

exec('%c'%stuff)

but we shorten program length by using + instead of -, and then we can remove ~ by using 1 instead of 0. We can then add 1, 11, and 111 to get the ASCII values required.

The program print() becomes the following at its shortest:

exec('%c%%c%%%%c%%%%%%%%c%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%c'%(111+1)%(111+1+1+1)%(11+11+11+11+11+11+11+11+11+1+1+1+1+1+1)%(11+11+11+11+11+11+11+11+11+11)%(111+1+1+1+1+1)%'('%')')

Try it online

You may be thinking to yourself, how does one create a NUL byte without 0? Fear not, young grasshopper! for we have the ability to use % for math as well, creating zero with 1%1.

CJam, 3 characters

Removed ) as per Martin Ender's suggestion

'(~

Similar to the Python one given as an example.

Using '~ you can obtain the ~ character. Then using (, you can decrement it in order to get whatever character you want (~ is the last printable ASCII character). ~ evals any string as normal CJam code. Strings can be constructed by obtaining the character [ (through decrementing ~), eval'ing it, putting some sequence of other characters, then eval'ing the character ]. Through this, you can build and execute any CJam program using only these three characters.

Calculating 2+2 using only '(~

Labyrinth, 5 characters

~{}

Plus linefeeds (0x0A) and spaces (0x20).

I'm going to sketch a proof in the form of a reduction from Smallfuck (a reduced Brainfuck-variant that uses 1-bit cells). Note that Smallfuck itself is not Turing-complete because the language specifies that its tape has to be finite, but we're going to assume a variant of Smallfuck with an infinite tape, which would then be Turing-complete (as Labyrinth has no memory restrictions by design).

An important invariant throughout this reduction will be that every program (or subprogram) will result in a Labyrinth program (or subprogram) that starts and ends on the same row, and spans an even number of columns.

Labyrinth has two stacks which are initially filled with an infinite (implicit) amount of 0s. { and } shift the top value between these stacks. If we consider the top of the main stack to be the current "cell", then these two stacks can be seen as the two semi-infinite halves of the infinite tape used by Smallfuck. However, it will be more convenient to have two copies of each tape value on the stacks, to ensure the invariant mentioned above. Therefore < and > will be translated to {{ and }}, respectively (you could swap them if you like).

Instead of allowing the cell values 0 and 1, we're using 0 and -1, which we can toggle between with ~ (bitwise negation). The exact values don't matter for the purposes of Turing-completeness. We have to change both copies of the value on the stack, which gives us an even-length translation again: * becomes ~}~{.

That leaves the control flow commands []. Labyrinth doesn't have explicit control flow, but instead the control flow is determined by the layout of the code. We require the spaces and linefeeds to do that layouting.

First, note that ~~ is a no-op, as the two ~ effectively cancel. We can use this to have arbitrarily long paths in the code, as long as their length is even. We can now use the following construction to translate AA[BB]CC into Labyrinth (I'm using double letters so that the size of each snippet in Labyrinth is even, as guaranteed by the invariant):

      ~~~~
      ~  ~~~
AA~~..~~~~ ~CC
   ~     ~
   ~     ~
   ~     ~
   ~~~BB~~

Here, .. is a suitable number of ~ which matches the width of BB.

Again, note that the width of the construction remains even.

We can now go through how this loop works. The code is entered via the AA. The first ~~ does nothing and lets us reach the junction. This roughly corresponds to the [:

• If the current cell value is zero, the IP continues straight ahead, which will ultimately skip BB. The .. part is still a no-op. Then we reach a single ~ at another junction. We now know that the current value is non-zero, so the IP does take the turn north. It goes around the bend at the top, until it reaches another junction after six ~. So at that point the current value is still non-zero and the IP takes the turn again to move east towards the CC. Note that the three ~ before the CC return the current value to 0, as it should be when the loop was skipped.
• If the current cell value at the beginning of the loop is non-zero, the IP takes the turn south. It runs six more ~ before reaching BB (which do nothing), and then another six ~ before reaching the next junction. This roughly corresponds to the ].
  • If the current cell is zero, the IP keeps moving north. The next ~ makes the value non-zero, so that the IP takes this second junction, which merges the path with the case that the loop was skipped completely. Again, the three ~ return the value to zero before reaching CC.
  • If the current cell is non-zero, the IP takes the turn west. There are ~ before the next junction, which means that at this point the current value is zero so that the IP keeps going west. Then there will be an odd number of ~ before the IP reaches the initial junction again, so that the value is returned -1 and the IP moves south into the next iteration.

If the program contains any loops, then the very first AA needs to be extended to the top of the program so that the IP finds the correct cell to start on:

~     ~~~~
~     ~  ~~~
AA~~..~~~~ ~CC
   ~     ~
   ~     ~
   ~     ~
   ~~~BB~~

That's that. Note that programs resulting from this reduction will never terminate, but that is not part of the requirements of Turing-completeness (consider Rule 101 or Fractran).

Finally, we're left with the question whether this is optimal. In terms of workload characters, I doubt that it's possible to do better than three commands. I could see an alternative construction based on Minsky machines with two registers, but that would require =() or =-~, having only one stack-manipulation command but then two arithmetic commands. I'd be happy to be proven wrong on this. :)

As for the layout commands, I believe that linefeeds are necessary, because useful control flow is impossible on a single line. However, spaces aren't technically necessary. In theory it might be possible to come up with a construction that fills the entire grid with ~{} (or =() or =-~), or makes use of a ragged layout where lines aren't all the same length. However, writing code like that is incredibly difficult, because Labyrinth will then treat every single cell as a junction and you need to be really careful to keep the code from branching when you don't want it to. If anyone can prove or disprove whether omitting the space is possible for Turing-completeness, I'd be happy to give out a sizeable bounty for that. :)

Whitespace, 3 chars

STL

S is space, T is tab, and L is newline.

Unary, 1 character

0

The choice of character doesn't really matter; the length of the program defines the brainfuck program it transpiles to. While the spec mandates 0 characters, most transpilers don't seem to check this.