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.

• Unary, 1 character. sighs Feb 20, 2017 at 15:24
• @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. Feb 20, 2017 at 15:35
• @MartinEnder I'd be especially interested to see answers in languages like Java or C. Feb 20, 2017 at 15:41
• Please don't post solutions in esolangs where the solution is every valid character in the language. It's not intresting or clever. Feb 20, 2017 at 17:20
• @Pavel Not interesting or clever may mean that it shouldn't get upvoted, but certainly not that it shouldn't get posted. Feb 20, 2017 at 21:36

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.

• If this isn't named, I suggest J5h*t. Feb 23, 2017 at 2:11
• What would a good example program be? Prime test? Hello world? Feb 23, 2017 at 3:04
• My, this is so wat... delicious answer, like a good horror film. Feb 23, 2017 at 21:19
• I thought Angular1's use of toString() for dependency injection is the most creative way of using the function. Now I changed my mind. Feb 25, 2017 at 5:56
• Also, [[]]["concat"]+[] is ",". Jun 18, 2017 at 21:32

()=;


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      )

• This construction doesn't work directly; SKI aren't Turing complete in a strongly typed language like Haskell. However, I believe you can use the same technique to define fix, and SKI + fix is Turing complete, even in a strongly typed language.
– user62131
Feb 21, 2017 at 5:03
• Oh, so you prefix those definitions at the beginning of each program? Feb 21, 2017 at 12:34
• @PyRulez: yes. Per our defaults I assume that it is enough to be able to construct functions with the given character set - a full program is not required.
– nimi
Feb 21, 2017 at 16:44
• You should probably replace (==) so that it wouldn't clash with the default equality operator Feb 24, 2017 at 9:33
• @proudhaskeller: yes, if you actually want to program it would be better to rename (==), but the above code is just a prove of turing completeness.
– nimi
Feb 24, 2017 at 19:25

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.

• We should probably open issues with the transpilers validating the spec, this is a very serious issue. Feb 21, 2017 at 15:26
• I'm stunned. I needed 20 minutes to tell whether it is a joke. Feb 23, 2017 at 15:16
• @PeterA.Schneider Some googling will find that someone actually implemented a quine this way in theory, although the resulting string of 0's is possibly the largest number I've ever seen in any practical context and could never be implemented on a real machine. Feb 24, 2017 at 20:50
• That string of zeroes is actually the smallest number I've ever seen in any context whatsoever. Feb 24, 2017 at 22:01
• @MatthewRead I guess you never heard about the square of $i$ then Feb 27, 2017 at 2:23

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'])

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

• You could add some checks to see if the input program is already limited to the necessary set of characters, and if so, just cat. Apr 30, 2018 at 18:26

vim, 987 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.

• Can't you do i<C-v>1<ESC> to write <C-a> and then dd so that you can use @1 for incrementing any numbers and result in not having to use <C-a>? Feb 20, 2017 at 18:09
• Wow, this answer is incredible! +1! Feb 20, 2017 at 18:13
• @mbomb007 Actually... due to an interesting implementation detail, <C-v>10 inserts a NUL rather than \n (don't ask). In any case, yeah, it doesn't matter with regards to Turing-completeness. Feb 20, 2017 at 20:16
• Can it be shorter? golf.shinh.org/p.rb?Hello+broken+keyboard#Vim Feb 21, 2017 at 22:11
• @DevSolar Vim stores the buffer contents in C strings, which cannot contain a null byte because they use it as the terminator. Because of that, null bytes are represented by line feeds, which are not otherwise used because Vim stores each line as a separate string.
– m90
Jun 25, 2021 at 3:57

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.

• I see.. your encoding gets a quadratic blowup because your characters divide into two groups, one that can only be produced by xor'ing an even number of base characters, and another that can only be produced by an odd number, forcing you to add another glob whenever changing between them. Any chance you could divide the program into shorter evaluable pieces tied together with ^ or other base characters? Jun 2, 2017 at 4:33
• @ØrjanJohansen Yep, good job spotting that. I’m working on a solution right now. Jun 2, 2017 at 7:02
• You can make that shrinked example a TIO link Try it online! Jun 3, 2017 at 4:34
• Request: Explain this "slightly different approach" Jun 4, 2017 at 3:59

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.

• Wonderful answer. Feb 21, 2017 at 21:16

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!

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

Thanks to @Bubbler for 8 -> 5

Edit: More compact encoding in example programs.

• @GB: Zero's fairly easy to avoid using in at least x86 machine code (it's not a terribly important instruction), especially because the problem only happens if you have four zero bytes in a row.
– user62131
Feb 22, 2017 at 9:39
• @GB On a machine with 32 bit ints 0==1111111111+1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+111+111+111+111+111+11+11+11+11+11+11+11+1 Feb 22, 2017 at 9:41
• tcc lets you get away without const. tio.run/nexus/… Feb 22, 2017 at 14:31
• @GB I just realized a shorter representation of 0 is 1==11 Feb 22, 2017 at 19:18
• @wizzwizz4, it's not pure C in any case, not in any sense that makes it Turing complete. It has no C semantics whatever. Since you're anyway relying on compiler and execution environment details to get anything runnable at all, you might as well allow for an arbitrarily-named entry point. Feb 23, 2017 at 19:18

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.

• If only operator precedence would execute + or - before the %, we could remove a character. Feb 20, 2017 at 18:40
• It might be worth noting being able to translate every Python program to your reduced character set isn't necessary for Turing-completeness. Although I imagine it will be hard to get the required amount of control flow without using exec anyway. Feb 20, 2017 at 20:02
• This is not really even technically a Turning Complete language though, is it? It has the ability to call the interpreter for a Turning Complete language, which is the embedded Python interpreter. This would work in any language, regardless of whether or not it's Turning Complete, so long as it has the ability to, for instance, invoke a shell command to another interpreter. Feb 24, 2017 at 19:09
• @mmachenry Python is using its own compiler and interpreter. It's not using another separate language. And a brainfuck interpreter has been created in Python, so it's Turing Complete. Using that knowledge, your argument is false. Feb 24, 2017 at 19:39
• @mbomb007 No my argument is not false. Python is a Turning Complete language, obviously. The computation is being done by calling a Python interpreter from Python using any character you want for the inner call. The language that you're specifying the program in is merely an encoding, not a programming language. Using this, it's trivial to make literally every programming language Turing Complete by using the characters 0 and 1 and viewing the source files as binary. The spirit of the question is to find a syntactic subset of the actual language though. Mar 1, 2017 at 21:15

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!

• Surely, figuring out which of the hexadecimal digits can be omitted is the interesting part of solving this in Java? :) Feb 21, 2017 at 16:26
• @MartinEnder absolutely. I plan on working on this more when I get some time
– Poke
Feb 21, 2017 at 18:40
• And me who was ready to write something Java, 127 characters... Nice one, Poke ;) Feb 21, 2017 at 21:16
• Based on the required characters in my answer, I do not believe any other hex digits can be removed.
– user18932
Feb 22, 2017 at 4:57
• If you switch to Java 8, you can do it in 16; Java 8 allows interfaces to have static methods, allowing you to drop c (all the letters in interface are still accessible with no a or c in your hex literals).
– user62131
Feb 22, 2017 at 9:34

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 '(~

• for another challenge, someone made a program that takes any cjam program and automatically compiles it to this subset. I wish I could find it
– Zwei
Mar 15, 2017 at 1:27
• I managed to golf down the 2+2 program significantly '~((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((~'~(((((((((((((((((((((((((((((((~'~(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((~
– Zwei
Mar 15, 2017 at 23:36
• @Zwei great, that fits your name Jul 2, 2018 at 6:40

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.

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?

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

()\->=;


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

• Won't it technically be removed at compile time without main? Feb 21, 2017 at 0:38
• The simply typed SKI combinator calculus isn't Turing-complete; you need an untyped lambda calculus for that. Unfortunately, as your demonstrations mention, Haskell puts a typed interpretation on the code by default.
– user62131
Feb 21, 2017 at 2:34
• @PyRulez As per the default rules I assumed that functions are acceptable. Feb 21, 2017 at 8:37
• @ais523 The SKI combinators are just an example, using the given notation arbitrary lambda terms can be build, e.g. church numerals and functions on them. Feb 21, 2017 at 8:47
• @ais523 how many combinators does typed Lambda Calculus need to be complete? I think you just need the y combinator, right? Feb 21, 2017 at 12:33

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

• "because <...> and [...] are still in use." However, you did not remove [...]. Please fix. Jun 4, 2017 at 20:14
• Question: Is [...] really necessary? Pushing 0 can be done at the start with ({}) (but it relies on a empty stack, so 0s will have to be carefully shuffled) The main problem is being able to go down the stack without access to <...> (which can no longer be simulated) Jun 18, 2017 at 17:47

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

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\\\''

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

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.

• "Thue programs continue running until no more substitutions are possible, and this causes the Retina to work the same way" with the only exception that Retina will terminate early if one pass through the entire program fails to change the string. So you even get some simple infinite-loop detection for free. Feb 21, 2017 at 13:23
• Ah right. That doesn't affect Turing-completeness, of course (because an infinite loop that doesn't change the internal state can't contribute to a program's computational class).
– user62131
Feb 21, 2017 at 14:59

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!

• Welcome to Code Golf! This is a really clever trick to save a character! Jul 30 at 2:52
• I know the goal isn't to minimise the size of the encoded program, but it seems odd not to have 0, 12, and 14 represented using 0, 0xc and 0xe.
– Neil
Jul 30 at 5:54

Stack-based concatenative languages, 4 characters

():^


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.

• I understand you can perform stack operations with those, but don't you need at least numbers to populate that stack in order to do mathematical calculations? Or are those done in unary using one of the 4 chars? Feb 21, 2017 at 7:52
• @seshoumara: Numbers (and pretty much all other data storage) are implemented very indirectly when using this method. There's something like two or three, maybe even four, levels of abstraction before you get to something recognisable as arithmetic. This sort of thing is common in Turing-completeness proofs of very limited systems like this.
– user62131
Feb 21, 2017 at 7:58
• I was thinking of submitting an answer in dc myself, also a stack based language, but using another method involving more chars than 4. dc has no concatenation operator, but it does have the equivalent ones you mention: [ ] d x. Can dc fit into your list? Feb 21, 2017 at 8:16
• @seshoumara: Yes, it seems it has all the functionality required. I've added it and credited you.
– user62131
Feb 21, 2017 at 15:17
• Maybe you could look up FlogScript Feb 21, 2017 at 21:43

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

• This is a polyglot, the same characters can be used for ><> and its derivatives. Nice work!
– Sok
Feb 21, 2017 at 8:57
• Befunge-98 is doable in 3 with 1p- as well Feb 21, 2017 at 12:31
• @Sp3000 Of course yes! I was sure there must have been a way to get it down to 3 characters. Thanks. Feb 21, 2017 at 21:35

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

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.

• Any particular reason you can't use pairwise coprime repunits? May 30, 2017 at 19:12
• @CalculatorFeline: No, but I didn't think of them until after I already found the construction which didn't need them. It'd certainly help in golfing programs written with this character set.
– user62131
Jun 2, 2017 at 13:34
• Also, all repunits >1 are pairwise coprime (think about it) Jun 2, 2017 at 19:57
• @CalculatorFeline: No they aren't. 111 and 111111 are both divisible by 3, fairly obviously.
– user62131
Jun 2, 2017 at 20:49
• *no repunit divides another repunit Jun 2, 2017 at 23:32

Whitespace, 3 chars

STL


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

• Is this the full language, or is it a subset? Where's the proof of Turing completeness? Feb 24, 2017 at 13:47
• @BrianMinton It is the full language, The esolang wiki is VERY light on it esolangs.org/wiki/Whitespace but afaik, it is turing complete Feb 24, 2017 at 16:47

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

• The simply typed SKI combinator calculus isn't Turing-complete; you need an untyped lambda calculus for that. Unfortunately, as your demonstrations mention, OCaml puts a typed interpretation on the code by default.
– user62131
Feb 21, 2017 at 2:34
• Then I simply need a few more characters to allow the use of polymorphic variants which will allow encoding the y-combinator (and similarly the z-combinator). Feb 21, 2017 at 2:47
• What's the Z combinator? Jun 4, 2017 at 1:16
• @CalculatorFeline It is a strict variant of the y-combinator. It is necessary in OCaml because OCaml is not lazy. Here is a link to the wikipedia page: en.wikipedia.org/wiki/… Jun 24, 2017 at 7:20

Ruby, 8 chars

eval"<1+


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"


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.

• Why would you ever want a NUL byte in your program?
– Maya
Jan 18, 2018 at 18:08
• @NieDzejkob On this site, the answer to "why" is always "because we can". In this case, though, it wouldn't be the full implementation of Python if you couldn't do it, even if it just gives an error. Jan 18, 2018 at 19:53
• You wouldn't need a NUL byte for Turing Completeness; a BF interpreter can be written without one Mar 3, 2019 at 3:50
• @MilkyWay90 True, but why not account for it if you can? Mar 3, 2019 at 20:30
• It's usually a lot shorter to split up each character into its own string and add them together at the end, e.g. print() in 141 bytes
– Jo King
Jun 19, 2021 at 13:31

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.

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

• You can remove the space character by replacing any identifier z being passed as an argument with ((λ(λλ)λλ)z). Sep 26 at 5:15
• @SoupGirl but haven't you just exchanged space for z and it's still 4 distinct characters? Sep 27 at 14:07
• I use z to stand for some identifier. What I mean is you could replace (λλλ λλλλ) with (λλλ((λ(λλ)λλ)λλλλ)) Nov 11 at 23:56
• Oh! Yes I suppose that works. Well done. Nov 21 at 17:11