105
\$\begingroup\$

Summary:

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

Challenge:

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


Examples:

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

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

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

Scoring:

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


Notes:

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

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

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

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

49 Answers 49

76
\$\begingroup\$

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      )
\$\endgroup\$
  • 16
    \$\begingroup\$ 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. \$\endgroup\$ – user62131 Feb 21 '17 at 5:03
  • \$\begingroup\$ Oh, so you prefix those definitions at the beginning of each program? \$\endgroup\$ – PyRulez Feb 21 '17 at 12:34
  • \$\begingroup\$ @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. \$\endgroup\$ – nimi Feb 21 '17 at 16:44
  • 1
    \$\begingroup\$ You should probably replace (==) so that it wouldn't clash with the default equality operator \$\endgroup\$ – proud haskeller Feb 24 '17 at 9:33
  • \$\begingroup\$ @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. \$\endgroup\$ – nimi Feb 24 '17 at 19:25
61
+50
\$\begingroup\$

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.

\$\endgroup\$
  • 15
    \$\begingroup\$ If this isn't named, I suggest J5h*t. \$\endgroup\$ – CalculatorFeline Feb 23 '17 at 2:11
  • 1
    \$\begingroup\$ What would a good example program be? Prime test? Hello world? \$\endgroup\$ – CalculatorFeline Feb 23 '17 at 3:04
  • 3
    \$\begingroup\$ My, this is so wat... delicious answer, like a good horror film. \$\endgroup\$ – ceased to turn counterclockwis Feb 23 '17 at 21:19
  • 4
    \$\begingroup\$ I thought Angular1's use of toString() for dependency injection is the most creative way of using the function. Now I changed my mind. \$\endgroup\$ – Sunny Pun Feb 25 '17 at 5:56
  • 1
    \$\begingroup\$ Here's an example: pastebin.com/QGbjmB5Y \$\endgroup\$ – Esolanging Fruit May 8 '17 at 19:02
55
\$\begingroup\$

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.

\$\endgroup\$
  • 43
    \$\begingroup\$ We should probably open issues with the transpilers validating the spec, this is a very serious issue. \$\endgroup\$ – Captain Man Feb 21 '17 at 15:26
  • 5
    \$\begingroup\$ I'm stunned. I needed 20 minutes to tell whether it is a joke. \$\endgroup\$ – Peter A. Schneider Feb 23 '17 at 15:16
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Darren Ringer Feb 24 '17 at 20:50
  • 10
    \$\begingroup\$ That string of zeroes is actually the smallest number I've ever seen in any context whatsoever. \$\endgroup\$ – Matthew Read Feb 24 '17 at 22:01
  • 1
    \$\begingroup\$ LOL, well, if you do something silly like defining your only symbol as an additive identity... :p \$\endgroup\$ – Darren Ringer Feb 24 '17 at 23:12
37
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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>? \$\endgroup\$ – Cows quack Feb 20 '17 at 18:09
  • 4
    \$\begingroup\$ Wow, this answer is incredible! +1! \$\endgroup\$ – DJMcMayhem Feb 20 '17 at 18:13
  • \$\begingroup\$ @KritixiLithos That does end up working after a bit of restructuring, thanks! \$\endgroup\$ – Doorknob Feb 20 '17 at 18:47
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Doorknob Feb 20 '17 at 20:16
  • 1
    \$\begingroup\$ Can it be shorter? golf.shinh.org/p.rb?Hello+broken+keyboard#Vim \$\endgroup\$ – mbomb007 Feb 21 '17 at 22:11
32
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – mbomb007 Apr 30 '18 at 18:26
32
+100
\$\begingroup\$

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, with the expected effect.

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

By xoring those strings 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Ørjan Johansen Jun 2 '17 at 4:33
  • \$\begingroup\$ @ØrjanJohansen Yep, good job spotting that. I’m working on a solution right now. \$\endgroup\$ – Grimy Jun 2 '17 at 7:02
  • \$\begingroup\$ You can make that shrinked example a TIO link Try it online! \$\endgroup\$ – Ørjan Johansen Jun 3 '17 at 4:34
  • 7
    \$\begingroup\$ Request: Explain this "slightly different approach" \$\endgroup\$ – CalculatorFeline Jun 4 '17 at 3:59
25
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wonderful answer. \$\endgroup\$ – Patrick Stevens Feb 21 '17 at 21:16
23
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ If only operator precedence would execute + or - before the %, we could remove a character. \$\endgroup\$ – mbomb007 Feb 20 '17 at 18:40
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Feb 20 '17 at 20:02
  • \$\begingroup\$ 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. \$\endgroup\$ – mmachenry Feb 24 '17 at 19:09
  • \$\begingroup\$ @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. \$\endgroup\$ – mbomb007 Feb 24 '17 at 19:39
  • \$\begingroup\$ @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. \$\endgroup\$ – mmachenry Mar 1 '17 at 21:15
23
\$\begingroup\$

C (unportable), 24 18 13 characters

aimn[]={};,1+

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[]={111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+11111+11111+11111+11111+11111+11111+11111+11111+111+11+11+11+11+11+11+1+1,1111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+11111+11111+11111+11111+11111+11111+1111+1111+1111+111+111+111+111+111+111,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+111111+111111+111111+111111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+111+11+11+11+11+11+11+1+1+1+1,111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+111111+111111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+11+11+11+11+1+1+1+1,111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+1111+1111+1111+111+111+111+111+111+11+11+11+11+11+11+1+1+1+1+1+1,111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+111+111+111+111+111+111+11+11+11+11+11+11+11+1,1111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+1+1+1+1+1+1+1+1+1,1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+111111+111111+111111+111111+11111+11111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+11+11+1+1+1+1+1,1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+1111+1111+1111+1111+1111+111+11+1+1+1+1+1,1111111111+1111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+111+111+111+111+1+1+1+1+1+1+1,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+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+11+11+11+1+1+1,1111111111+111111111+111111111+111111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+111111+111111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+1+1+1+1+1+1,111111+111111+11111+11111+11111+11111+11111+11111+11111+1111+1111+1111+1111+1111+1111+1111+1111+111+111+111+11+11+11+11+11+11+11+11+11+11,11111111+11111111+11111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+111+111+111+11+11+11+11+11+11+11+1+1+1,111111111+111111111+111111111+111111111+111111111+111111111+111111111+11111111+11111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+111+111+11+11+11+1,111111111+111111111+11111111+11111111+1111111+1111111+1111111+1111111+1111111+1111111+111111+111111+111111+111111+111111+11111+11111+11111+11111+11111+11111+11111+11111+11111+1111+1111+111+11+11+1+1+1+1+1,11111+11111+11111+11111+1111+1111+1111+1111+111+111+111+111+111+111+111+111+111+11+11+11+1+1+1+1+1};

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – user62131 Feb 22 '17 at 9:39
  • 2
    \$\begingroup\$ @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 \$\endgroup\$ – ceilingcat Feb 22 '17 at 9:41
  • 3
    \$\begingroup\$ tcc lets you get away without const. tio.run/nexus/… \$\endgroup\$ – Dennis Feb 22 '17 at 14:31
  • 8
    \$\begingroup\$ @GB I just realized a shorter representation of 0 is 1==11 \$\endgroup\$ – ceilingcat Feb 22 '17 at 19:18
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – John Bollinger Feb 23 '17 at 19:18
20
\$\begingroup\$

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.

\$\endgroup\$
19
\$\begingroup\$

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

\$\endgroup\$
19
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Won't it technically be removed at compile time without main? \$\endgroup\$ – PyRulez Feb 21 '17 at 0:38
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – user62131 Feb 21 '17 at 2:34
  • \$\begingroup\$ @PyRulez As per the default rules I assumed that functions are acceptable. \$\endgroup\$ – Laikoni Feb 21 '17 at 8:37
  • \$\begingroup\$ @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. \$\endgroup\$ – Laikoni Feb 21 '17 at 8:47
  • \$\begingroup\$ @ais523 how many combinators does typed Lambda Calculus need to be complete? I think you just need the y combinator, right? \$\endgroup\$ – PyRulez Feb 21 '17 at 12:33
18
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Zwei Mar 15 '17 at 1:27
  • 1
    \$\begingroup\$ I managed to golf down the 2+2 program significantly '~((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((~'~(((((((((((((((((((((((((((((((~'~(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((~ \$\endgroup\$ – Zwei Mar 15 '17 at 23:36
  • \$\begingroup\$ @Zwei great, that fits your name \$\endgroup\$ – Chromium Jul 2 '18 at 6:40
18
\$\begingroup\$

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!

\$\endgroup\$
  • 3
    \$\begingroup\$ Surely, figuring out which of the hexadecimal digits can be omitted is the interesting part of solving this in Java? :) \$\endgroup\$ – Martin Ender Feb 21 '17 at 16:26
  • \$\begingroup\$ @MartinEnder absolutely. I plan on working on this more when I get some time \$\endgroup\$ – Poke Feb 21 '17 at 18:40
  • 6
    \$\begingroup\$ And me who was ready to write something Java, 127 characters... Nice one, Poke ;) \$\endgroup\$ – Olivier Grégoire Feb 21 '17 at 21:16
  • \$\begingroup\$ Based on the required characters in my answer, I do not believe any other hex digits can be removed. \$\endgroup\$ – user18932 Feb 22 '17 at 4:57
  • 3
    \$\begingroup\$ 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). \$\endgroup\$ – user62131 Feb 22 '17 at 9:34
17
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ "because <...> and [...] are still in use." However, you did not remove [...]. Please fix. \$\endgroup\$ – CalculatorFeline Jun 4 '17 at 20:14
  • \$\begingroup\$ 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) \$\endgroup\$ – CalculatorFeline Jun 18 '17 at 17:47
16
\$\begingroup\$

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

\$\endgroup\$
12
\$\begingroup\$

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

\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ "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. \$\endgroup\$ – Martin Ender Feb 21 '17 at 13:23
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – user62131 Feb 21 '17 at 14:59
9
\$\begingroup\$

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"
\$\endgroup\$
9
\$\begingroup\$

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

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

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

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – user62131 Feb 21 '17 at 2:34
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – Devin Lehmacher Feb 21 '17 at 2:47
  • \$\begingroup\$ What's the Z combinator? \$\endgroup\$ – CalculatorFeline Jun 4 '17 at 1:16
  • \$\begingroup\$ @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/… \$\endgroup\$ – Devin Lehmacher Jun 24 '17 at 7:20
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Any particular reason you can't use pairwise coprime repunits? \$\endgroup\$ – CalculatorFeline May 30 '17 at 19:12
  • \$\begingroup\$ @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. \$\endgroup\$ – user62131 Jun 2 '17 at 13:34
  • \$\begingroup\$ Also, all repunits >1 are pairwise coprime (think about it) \$\endgroup\$ – CalculatorFeline Jun 2 '17 at 19:57
  • \$\begingroup\$ @CalculatorFeline: No they aren't. 111 and 111111 are both divisible by 3, fairly obviously. \$\endgroup\$ – user62131 Jun 2 '17 at 20:49
  • \$\begingroup\$ *no repunit divides another repunit \$\endgroup\$ – CalculatorFeline Jun 2 '17 at 23:32
7
\$\begingroup\$

Whitespace, 3 chars

STL

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

\$\endgroup\$
  • \$\begingroup\$ Is this the full language, or is it a subset? Where's the proof of Turing completeness? \$\endgroup\$ – Brian Minton Feb 24 '17 at 13:47
  • 2
    \$\begingroup\$ @BrianMinton It is the full language, The esolang wiki is VERY light on it esolangs.org/wiki/Whitespace but afaik, it is turing complete \$\endgroup\$ – Cruncher Feb 24 '17 at 16:47
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Why would you ever want a NUL byte in your program? \$\endgroup\$ – NieDzejkob Jan 18 '18 at 18:08
  • \$\begingroup\$ @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. \$\endgroup\$ – mbomb007 Jan 18 '18 at 19:53
  • \$\begingroup\$ You wouldn't need a NUL byte for Turing Completeness; a BF interpreter can be written without one \$\endgroup\$ – MilkyWay90 Mar 3 at 3:50
  • \$\begingroup\$ @MilkyWay90 True, but why not account for it if you can? \$\endgroup\$ – mbomb007 Mar 3 at 20:30
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – seshoumara Feb 21 '17 at 7:52
  • \$\begingroup\$ @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. \$\endgroup\$ – user62131 Feb 21 '17 at 7:58
  • \$\begingroup\$ 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? \$\endgroup\$ – seshoumara Feb 21 '17 at 8:16
  • \$\begingroup\$ @seshoumara: Yes, it seems it has all the functionality required. I've added it and credited you. \$\endgroup\$ – user62131 Feb 21 '17 at 15:17
  • \$\begingroup\$ Maybe you could look up FlogScript \$\endgroup\$ – mbomb007 Feb 21 '17 at 21:43
5
\$\begingroup\$

Pyke, 5 characters

0h.CE

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

Explanation of the code:

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

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

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

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

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

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

Attempted proof that Pyke is Turing Complete.

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

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

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

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

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

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

Try it here!

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

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

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

The (almost) final solution can be tried here!

Explanation of Brainf*ck interpreter

First lets separate the program into parts:

  • The initialisation:

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

​​ ​ ​

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

​​ ​ ​

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

​​ ​ ​

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

​​ ​ ​

~c\.qI~LZ@.CpK) - The code for input 
~c\.qI        ) - if c == ".":
      ~LZ@      -    L[Z]
          .C    -   chr(^)
            pK  -  print(^)
  • Shift Left/Right: <>: ​​ ​ ​

​​ ​ ​

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

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

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

​​ ​ ​

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

- And ]: ​​ ​ ​

​​ ​ ​

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

tinylisp, 5 characters

(q d)

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

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

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

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

A more readable version

(load lib/utilities)

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

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

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

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

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

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

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

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

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

Passing func1 and func2 to S2 returns the list/function

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

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

((func1 arg) (func2 arg))

which implements the S-combinator.

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

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

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

\$\endgroup\$
5
\$\begingroup\$

Racket (Scheme), 4 characters

(λ)

Using only λ, parenthesis, and space, 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.

((λ (λλ) (λλ λλ)) (λ (λλ) (λλ λλ)))
\$\endgroup\$
4
\$\begingroup\$

Stacked, 5 chars

{!n:}

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

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

I combinator: {!n}

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

K combinator: {!{:n}}

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

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

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

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

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

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

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

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

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

With an explanation:

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

And therefore, this is the S combinator.

\$\endgroup\$
  • \$\begingroup\$ {n nn nnn:nnn{!n}!nn!nnn{!n}!n!!} contains spaces. \$\endgroup\$ – CalculatorFeline Jun 4 '17 at 1:20
  • \$\begingroup\$ @CalculatorFeline Did you read the sentence before that? Ok, this looks a little more complicated. So, a lambda takes arguments, separated by non-identifier characters. Thus, the lambda in the header is equivalent to: \$\endgroup\$ – Conor O'Brien Jun 4 '17 at 1:29
  • \$\begingroup\$ Oh. (Note to self: Stop being an idiot.) \$\endgroup\$ – CalculatorFeline Jun 4 '17 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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