Fewest (distinct) characters for Turing Completeness

Question

Summary:

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

Challenge:

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

---

Examples:

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

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

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

Scoring:

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

---

Notes:

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

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

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

Answer 1

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.

Answer 2

Haskell, 4 chars

()=;

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

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

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

(===) as K:

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

and (====) as I:

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

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

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

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

Answer 3

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.

Answer 4

Python 2, 7 characters

exc="%\n

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

Constructing arbitrary strings

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

Make numbers

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

Putting it together

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

import sys

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

print output

Try it online

Answer 5

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.

Answer 6

vim, 9 8 7 6 characters

<C-v><esc>1@ad

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

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

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

3. For each character in the desired vimscript program,

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

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

   3. and re-enter insert mode with a.

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

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

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

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

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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?

Answer 11

Python 3, 8 characters

Now we can write python in only 8 characters!

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

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

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

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

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

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

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

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

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

Can we build arbitrary number through this method? No.

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

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

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

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

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

Finally, build arbitrary string and execute!

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

Answer 12

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!

Answer 13

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

Answer 14

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

Answer 15

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.

Answer 16

Haskell, 5 7 characters

()\->=;

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

Examples:

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

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

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

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

Answer 17

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

Answer 18

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

Answer 19

Incident, 2 characters

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

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

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

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

Answer 20

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

Answer 21

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.

Answer 22

Stack-based concatenative languages, 4 characters

Underload

():^

GolfScript

{}.~

CJam

{}_~

GS2

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

dc (suggested by @seshoumara)

[]dx

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

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

Answer 23

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

Answer 24

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

Answer 25

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.

Answer 26

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.

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

Answer 27

Whitespace, 3 chars

STL

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

Answer 28

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

Answer 29

Ruby, 8 chars

eval"<1+

Inspired by the Python answers

How it works

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

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

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

is actually equivalent to

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

which evaluates the string

p"o"

Answer 30

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.