153
\$\begingroup\$

Summary:

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

Challenge:

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

Examples:

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

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

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

Scoring:

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

Notes:

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

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

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

Improve this question
\$\endgroup\$
26
  • 110
    \$\begingroup\$ Unary, 1 character. sighs \$\endgroup\$
    – Dennis
    Feb 20, 2017 at 15:24
  • 5
    \$\begingroup\$ @Dennis It's not that different from Jelly or 05AB1E having a built-in for an interesting number theory problem. This challenge still seems like an interesting and non-trivial optimisation problem in any language that wasn't designed to be a tarpit. \$\endgroup\$
    – Martin Ender
    Feb 20, 2017 at 15:35
  • 11
    \$\begingroup\$ @MartinEnder I'd be especially interested to see answers in languages like Java or C. \$\endgroup\$
    – Julian Lachniet
    Feb 20, 2017 at 15:41
  • 13
    \$\begingroup\$ Please don't post solutions in esolangs where the solution is every valid character in the language. It's not intresting or clever. \$\endgroup\$
    – Pavel
    Feb 20, 2017 at 17:20
  • 30
    \$\begingroup\$ @Pavel Not interesting or clever may mean that it shouldn't get upvoted, but certainly not that it shouldn't get posted. \$\endgroup\$
    – Dennis
    Feb 20, 2017 at 21:36

82 Answers 82

Reset to default
1 2
3
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Is delayedexpansion necessary? \$\endgroup\$
    – l4m2
    Jan 20 at 10:19
  • \$\begingroup\$ @l4m2 If Batch integers were unbounded then those could be used, but maybe strings could be used instead. \$\endgroup\$
    – Yousername
    Jan 25 at 15:41
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Using these constructs, can you create unbounded data structures? They could be in the form of arrays, lists, strings, or even integers, as long as they're not limited in size by the implementation. If not, the language isn't Turing-complete. For example, in QBasic, trying to DIM an array larger than 64KB (that's 16384 SINGLE numbers) gives a Subscript out of range error. (This is different from running out of memory, which will happen with any language and is considered an implementation difficulty rather than a limitation of the language.) \$\endgroup\$
    – DLosc
    Feb 24, 2017 at 21:21
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ I feel like + isn't necessary since, for example, if you wanted to add one you could do ~:/::--- \$\endgroup\$
    – EdgyNerd
    Sep 14, 2019 at 11:13
  • \$\begingroup\$ ::--- works for that \$\endgroup\$
    – EdgyNerd
    Sep 14, 2019 at 11:15
  • \$\begingroup\$ Actually wait, ::--- doesn't actually work, oops \$\endgroup\$
    – EdgyNerd
    Sep 14, 2019 at 11:18
  • \$\begingroup\$ can we continue this in the Keg chat room? \$\endgroup\$
    – EdgyNerd
    Sep 14, 2019 at 11:20
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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--
...
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

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!

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!

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!

Pascal (FPC), 29 28 distinct characters

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

progam ;cedusbl.i"\01234567n

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

program p;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!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
1
  • 5
    \$\begingroup\$ I don't think you need 3. I/O isn't required for turing completeness \$\endgroup\$
    – 12Me21
    Feb 8, 2019 at 17:27
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
-2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ OBVIOUSLY it's just 2 chars. It's BITS. \$\endgroup\$
    – Joao-3
    Mar 25 at 20:10
1 2
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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