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

72 Answers 72

6
\$\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\$
6
\$\begingroup\$

Self-modifying Brainfuck, 2 characters

<+

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

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

Exemple: a bf cat ,[.,]

It becomes [>],[.,].

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

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

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

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

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

Try it online!

Execution:

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

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

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

Try it online!

\$\endgroup\$
5
\$\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\$
3
  • \$\begingroup\$ {n nn nnn:nnn{!n}!nn!nnn{!n}!n!!} contains spaces. \$\endgroup\$ Jun 4, 2017 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\$ Jun 4, 2017 at 1:29
  • \$\begingroup\$ Oh. (Note to self: Stop being an idiot.) \$\endgroup\$ Jun 4, 2017 at 2:58
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\$

Java, 30 26 characters

 ()+-.0;=Sacdefgimnorstv{}

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

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

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

interface S {

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

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

These characters allow:

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

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

\$\endgroup\$
10
  • 1
    \$\begingroup\$ You need some way to create an infinite loop, for Turing completeness. I suspect you can do it via recursion (or for(;;)), but you probably need to mention that in your submission; manually unrolling an infinite loop is of course impossible, so the current explanation doesn't work. \$\endgroup\$
    – user62131
    Feb 22, 2017 at 5:16
  • \$\begingroup\$ You can use interface instead of class, which allows you to drop the public. \$\endgroup\$
    – corvus_192
    Feb 24, 2017 at 16:11
  • \$\begingroup\$ Also, replace the [] with ... to save another character. \$\endgroup\$
    – corvus_192
    Feb 24, 2017 at 16:12
  • \$\begingroup\$ @corvus_192 thanks, good catches. [] could be useful in a state machine, but is not strictly necessary. To use it, however, I would need to add w to support new. \$\endgroup\$
    – user18932
    Feb 24, 2017 at 16:25
  • 1
    \$\begingroup\$ Actually, you can do it all with decrement and unary minus. Have one variable as -1. Plus is not needed. \$\endgroup\$ Sep 21, 2017 at 7:12
5
\$\begingroup\$

05AB1E, 5 4 bytes

.gBV

-1 distinct byte thanks to @ovs.

Explanation:

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

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

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

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

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

Try it online:

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

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

\$\endgroup\$
6
  • \$\begingroup\$ The great thing about this is that it can even run arbitrary assembly! You generate a string like so: '‚«™"ÿ.cmd"’File.‡í"_",elem(ÿ("®È",["<your assembly here>"]),0);ÿ"nasm",["-felf64","_"];ÿ"ld",["_.o"];ÿ"./a.€Ä"’.E and then .V it. \$\endgroup\$
    – Makonede
    Jun 3, 2021 at 18:56
  • \$\begingroup\$ ...And also I wish whoever attempts this good luck on their journey to the edge of the universe to ask the aliens who created this universe politely for some more space in the universe for your RAM. \$\endgroup\$
    – Makonede
    Jun 3, 2021 at 20:56
  • 1
    \$\begingroup\$ @Makonede I've reverted your change of the '(and J for efficiency)'. Although correct, it isn't used in any of the four example programs and might only confuse readers of my answer. \$\endgroup\$ Jun 4, 2021 at 6:43
  • \$\begingroup\$ I think you can actually do this with g instead of X and +: Create a very large number with repeated .g and take the length g as the base for B. Though it will be quite a bit more effort to generate such programs. \$\endgroup\$
    – ovs
    Nov 15, 2021 at 16:20
  • 1
    \$\begingroup\$ My idea was to generate the entire program with a single call to B and the run it with .V. Here is a generator program. The large constant and the D> is replaced by many .g's, then the program only needs the characters .BVg. (The base in the generator program might need to be adjusted to find a solution) \$\endgroup\$
    – ovs
    Nov 16, 2021 at 8:51
5
\$\begingroup\$

TI-Basic, 15 characters

(TI-83 Family)

While End(-1:ʟ→

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

With these characters, you can use:

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

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

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

brainf*ck symbol Limited TI-Basic equivalent
(initialization) TI-83: 111-11-1→W:While W:1-1→ʟE(111-11-W:W-1→W:End:1→W:
non-TI-83: 1111-111-1→W:While W:1-1→ʟE(1111-111-W:W-1→W:End:1→W:
+ 1-(1-1-ʟE(W→ʟE(W:1→E:While E(1-(1-1-111-111-11-11-11-(1-1-ʟE(W:1-1→E:End:While E:1-1→E:E→ʟE(W:End:
- 1→E:While EʟE(W:1-1→E:E-(1-ʟE(W→ʟE(W:End:While E:1-1→E:1-(1-111-111-11-11-11→ʟE(W:End:
< TI-83: 1-1-(1-W→W:1→E:While EW:1-1→E:End:While E:1-1→E:111-11-1→W:End:
non-TI-83: 1-1-(1-W→W:1→E:While EW:1-1→E:End:While E:1-1→E:1111-111-1→W:End:
> TI-83: 1-(1-1-W→W:1→E:While E(111-11-W:1-1→E:End:While E:1-1→E:1→W:End:
non-TI-83: 1-(1-1-W→W:1→E:While E(1111-111-W:1-1→E:End:While E:1-1→E:1→W:End:
[ While ʟE(W:
] End:

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

1→ʟE(1:1→ʟE(1-(1-1-1:111-11-1-1-1→W:While W:ʟE(111-11-1-1-W→E:E-(1-1-ʟE(111-11-1-W→ʟE(111-11-W:W-1→W:End:ʟE
\$\endgroup\$
5
\$\begingroup\$

Zsh, 8 characters

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

Hence, we can construct the string eval:

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

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

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

Attempt This Online!

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

\$\endgroup\$
4
\$\begingroup\$

APL, 9 characters

⍎⎕UCS(≢⍬)

Why this is Turing-complete:

  • is length, is the empty list, and a list can be expressed simply by naming its elements, i.e. ⍬⍬⍬ is a list of three empty lists. This way, all numbers can be formed. ≢⍬ is 0, ≢≢⍬ is 1, and from then on ≢⍬⍬⍬... is N, where N is the amount of s.
  • () are used to change evaluation order. List construction works with anything, so this way (≢⍬)(≢⍬⍬)(≢⍬⍬⍬) evaluates to [0,2,3].
  • ⎕UCS gives a string of Unicode characters given a list of numbers. We can now generate any text we want.
  • is evaluate.
\$\endgroup\$
4
  • \$\begingroup\$ ≢≢⍬ does not look right. Should it be ≢⍬⍬? \$\endgroup\$ May 30, 2017 at 19:23
  • \$\begingroup\$ @CalculatorFeline: no, ≢⍬⍬ is 2. ⍬⍬ is the list containing two empty lists, and its length () is 2. ≢≢⍬ is 1, because is the empty list, its length () is 0, and the length of that () is 1. ≢≢⍬ = ≢0 = 1.Try it yourself: tryapl.org/… \$\endgroup\$
    – marinus
    May 31, 2017 at 20:12
  • 1
    \$\begingroup\$ Save a character: ⍎⎕AV[≢],). One-based indexing obviates the need for any "zeroth" character. \$\endgroup\$
    – Adám
    Jun 2, 2017 at 14:21
  • \$\begingroup\$ Change any code to an expression consisting of those 8 chars: Try it online! \$\endgroup\$
    – Adám
    Jun 2, 2017 at 15:36
4
\$\begingroup\$

ARM7 assembly - 8 bytes

CRS15,

And space and newline

With these characters, one can construct the following:

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

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

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

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

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

\$\endgroup\$
4
\$\begingroup\$

PowerShell, 15 14 characters

+[char](1)|iex

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

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

\$\endgroup\$
2
  • \$\begingroup\$ I don't think you need the ", I tried removing them in your example program. \$\endgroup\$ Feb 26, 2017 at 9:35
  • \$\begingroup\$ @EriktheOutgolfer You're right -- thanks! Must be a difference in behavior for newer versions of PowerShell, since previous versions would try to mathematically add the chars together, rather than concatenate. \$\endgroup\$ Feb 27, 2017 at 13:53
4
\$\begingroup\$

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

HR.

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

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

Suppose x and y are valid terms.

Then,

  H x
= * \ 1 \ x
= \ x

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

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

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

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

Then,

* \ 3 z = 2

* \ 2 z = 1

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

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

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

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

Written using our 3 characters, these are

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

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

\$\endgroup\$
4
\$\begingroup\$

Scala, 12 chars

(),:;=>[]def

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

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

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

Borrowed from here and optimised for this challenge.

\$\endgroup\$
2
  • \$\begingroup\$ I don't think you need to have a computer science degree to know whether something is Turing-Complete... \$\endgroup\$ Feb 21, 2017 at 23:36
  • \$\begingroup\$ @DLosc Right, you'd have to add either a newline or a semicolon. \$\endgroup\$
    – corvus_192
    Feb 24, 2017 at 16:02
4
\$\begingroup\$

ARM assembler (gas), 14 12 chars

Newline and space are included.


 bdlrst:[],

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

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

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

b encoding

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

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

For example:

foo:
     b       next
     nop
     nop
next:

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

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

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

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

Similarly, -1 can be done like so:

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

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

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

///// Prologue

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

///// Instruction translation

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

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


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

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

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

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

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

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

Literally every GAS dialect, 9 chars

Again, newline and space


 01.bety

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

\$\endgroup\$
3
\$\begingroup\$

Nock, 6 characters

[ ]012

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

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

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

\$\endgroup\$
3
\$\begingroup\$

Tildehyph, 2 characters

~-

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

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I'd like to know who downvoted this. \$\endgroup\$ Feb 21, 2017 at 22:09
  • 3
    \$\begingroup\$ @Challenger5 I don't see any point in an answer that removes no characters from the languages existing character set. Its just as boring as the Unary answer. \$\endgroup\$
    – Wheat Wizard
    Feb 22, 2017 at 1:22
  • 2
    \$\begingroup\$ And yet the Unary answer gets 21 upvotes? \$\endgroup\$
    – G B
    Feb 22, 2017 at 8:47
  • 3
    \$\begingroup\$ @GB: The Unary answer shouldn't have been upvoted according to the normal advice. However, SE rules also say you shouldn't downvote something just because it's been incorrectly upvoted. \$\endgroup\$
    – user62131
    Feb 22, 2017 at 9:36
  • 1
    \$\begingroup\$ @user62131 Then why downvote this answer? \$\endgroup\$
    – MilkyWay90
    Mar 3, 2019 at 3:54
3
\$\begingroup\$

BitCycle, 8 characters

AB>/+~

plus space and newline.

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

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

0

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






   +   ~    ~ 

1

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






   +   ~    ~ 

;

    . 




B / > 






    . 

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

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

> ... ~

~     ~

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

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

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

 ~                                           ~

       1           ;       0           ;     


      +   ~    ~          +   ~    ~         

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

\$\endgroup\$
3
\$\begingroup\$

J language, 7 char

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

".u:1b

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

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

Is this minimal?

Probably. What I have is pretty darn lean.

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

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

\$\endgroup\$
1
  • 9
    \$\begingroup\$ Why not just put the space in the list? \$\endgroup\$
    – mbomb007
    Feb 21, 2017 at 21:45
3
\$\begingroup\$

///, 2 characters

/\

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

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

Shortened to 2 characters thanks to @ØrjanJohansen

\$\endgroup\$
6
  • 6
    \$\begingroup\$ I'm fairly sure that /// is Turing-complete with just forward slash and backslash, but I'm not sure if that's actually been proven anywhere. This can likely be minimized, anyway. \$\endgroup\$
    – user62131
    Feb 24, 2017 at 18:10
  • \$\begingroup\$ I think that at least characters ()|PD01 are used only for convenience in that code (it could be written without them, but it would be longer and it would be harder to encode the input to the tag). I don't know this language well enough, but i'm guessing that `/\` could very well be enough, since with just those two characters you can build an infinite set of words. \$\endgroup\$
    – Leo
    Feb 24, 2017 at 18:11
  • \$\begingroup\$ () are also only used for convenience. You could write the entire thing using only \/. \$\endgroup\$ Feb 24, 2017 at 18:13
  • \$\begingroup\$ Thanks. I am very new to this language, so I wouldn't know this. \$\endgroup\$
    – sporklpony
    Feb 24, 2017 at 19:39
  • 2
    \$\begingroup\$ Hi, author here. Even the . is just for convenience, everything other than slash and backslash is expanded before entering the main loop. \$\endgroup\$ Feb 27, 2017 at 2:52
3
\$\begingroup\$

C (gcc), 19 bytes

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

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

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

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

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

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Why is t needed? \$\endgroup\$
    – ceilingcat
    Mar 14, 2020 at 21:39
  • \$\begingroup\$ @ceilingcat For int. I guess I was tuning it to my example too much. \$\endgroup\$
    – S.S. Anne
    Mar 14, 2020 at 22:01
3
\$\begingroup\$

Setanta, 14 characters

adghimnort(){}

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

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

Then inline i, k, and s as needed.

\$\endgroup\$
3
\$\begingroup\$

Emmental, 3 characters

#5?

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

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Unlambda, 3 characters

sk`

It's a turing tarpit of course.

\$\endgroup\$
2
\$\begingroup\$

Skull, 9 characters

[]{}|:NUM

So Skull is an interesting language. You need NUM to set number mode. This adds to the amount of characters you need as you have to use one at the beginning of your programs. Also I mean that is the entire language except for 3 other characters.

{ x [ y ] } Increment or decrement the specified cell (x) by the specified number (y)
{ x { While the specified cell (x) is not 0...
} } End while
| x | Print out the specified cell (x) to the screen

This is a simple program doing addition (4+2)

:NUM:       // set mode to NUM
{0[+4]}      // set cell 0 to 4
{1[+2]}      // set cell 1 to 2
{0{         // while cell 0 is not 0
  {0[-1]}   // subtract cell 0 by 1
  {1[+1]}   // add 1 to cell 1
}}          // end while
|1|         // print cell 1 (6)
\$\endgroup\$
7
  • 1
    \$\begingroup\$ ASCII or ASKII? \$\endgroup\$ Feb 20, 2017 at 17:23
  • \$\begingroup\$ @NoOneIsHere Opps! Thanks for that. \$\endgroup\$ Feb 20, 2017 at 21:31
  • \$\begingroup\$ You don't need to print something to be Turing complete, so I think you can drop the ASC. \$\endgroup\$
    – Laikoni
    Feb 20, 2017 at 22:25
  • \$\begingroup\$ @Laikoni nice! That will cut this down! \$\endgroup\$ Feb 20, 2017 at 22:26
  • \$\begingroup\$ This also needs a Turing proof. \$\endgroup\$ Feb 24, 2017 at 13:48
2
\$\begingroup\$

Baba is You, 18 characters

Plus 3 objects in the game.

TEXISMOVLPDWNFRGHY

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

Screenshot of the level design

All the rules and explanation:

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

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

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

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

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

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

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

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

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

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

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

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

Level initial state

\$\endgroup\$
2
  • \$\begingroup\$ Interestingly, the 'Baba Make Level' update has made Game of Life a lot easier to implement. You can now write sentences like 'near rock and rock' and it requires two distinct rocks to be nearby for it to be true. Based on this, MutantVampire/Laxxius from the Baba is You Discord server has reduced the character set down to 9: cdn.discordapp.com/attachments/923018331097825283/… \$\endgroup\$
    – Patashu
    Mar 24 at 23:25
  • 2
    \$\begingroup\$ random 8 has gotten it down to 8 characters (adeinrst) + 3 objects (ear, it, reed): cdn.discordapp.com/attachments/923018331097825283/… \$\endgroup\$
    – Patashu
    Mar 25 at 3:05
2
\$\begingroup\$

80386 machine code, 10 bytes

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

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

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

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

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

inc byte [esp]
dec byte [esp]

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

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

jnz rel8  ; 75
jnz rel32 ; 0f 85

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

nop ; 90

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

Finally to end the program,

ret ; c3

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

sum:
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
.loop0:
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    inc byte [esp]    ; fe 04 24
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    dec byte [esp]    ; fe 0c 24
    
    ; A LOT of `nop`s ; 90
    
    jnz .loop0        ; 0f 85 fe fe fe fe
    inc esp           ; 44
.loop1:
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    inc byte [esp]    ; fe 04 24
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    inc esp           ; 44
    dec byte [esp]    ; fe 0c 24
    
    ; A LOT of `nop`s ; 90
    
    jnz .loop1        ; 0f 85 fe fe fe fe
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    dec esp           ; 4c
    ret
\$\endgroup\$
3
  • 2
    \$\begingroup\$ We have both even and odd (at least one of 75 or 85) byte values, so for any loop length we can pad the loops using >< (4c 44) dummy pair, saving nop (1 byte). inc/dec also sets the zero flag, so you can use a dummy +- pair in place of an explicit cmp (saves 3 bytes). \$\endgroup\$
    – Bubbler
    Feb 17 at 7:38
  • 1
    \$\begingroup\$ @Bubbler Nice suggestion! I applied the inc/dec trick, but for using nop, only 0f 85 or jnz rel32 is used, so I think nop is still needed for padding. I'm not sure, but jnz rel8 might be too short for certain problems. \$\endgroup\$
    – xiver77
    Feb 17 at 7:58
  • \$\begingroup\$ What about ladder-based programming ( cs.cmu.edu/~tom7/abc/paper.pdf )? It made due with 8-bit offsets, and I think it is TC. \$\endgroup\$ Feb 20 at 3:53
2
\$\begingroup\$

Batch, 25 characters


 !%-/1:=abcdefgilnopstxy

(Includes newline and space.)

With these characters, you can translate brainf*ck (without , and .), which is Turing-complete:

brainf*ck Command | Limited Batch Equivalent
------------------|--------------------------------
initialization    | setlocal enabledelayedexpansion
                  | set/at=1-1
                  | set/al=111--111--11--11--11
                  | set/an=1--1--1
                  | set/an=%n%%t%%t%%t%%t%
------------------|--------------------------------
+                 | if !c%t%!==%l% set/ac%t%=-1
                  | set/ac%t%-=-1
------------------|--------------------------------
-                 | set/ac%t%-=1
                  | if !c%t%!==-1 set/ac%t%=%l%
------------------|--------------------------------
<                 | set/at-=1
                  | if %t%==-1 set/at=%n%
------------------|--------------------------------
>                 | if %t%==%n% set/at=-1
                  | set/at-=-1
------------------|--------------------------------
[                 | :l
                  | if !c%t%! lss 1 goto:e
------------------|--------------------------------
]                 | :e

t stores the pointer position, and c_ stores the value of the cell at index _. Labels :l and :e will need to be renamed accordingly for nested brackets.

\$\endgroup\$
1
\$\begingroup\$

SmileBASIC, 9 charcaters

(space)$+=@GOT[]

$ - required for string variables
+ - for concatenating strings
= - assignment
@ - labels and label string literals (@ABC = "@ABC", when used in an expression)
GOT - used for GOTO, variable names, and label names
[] - accessing characters in strings
space - separator

Here is a Bitwise Cyclic Tag interpreter (some spaces replaced with line breaks for readability)

Program is encoded as G=0, O=10, T=11, and the data string uses T and O as 1 and 0.

G$=@<program here>
G$[O]=O$
T$=@<initial data here>
T$[O]=O$

GOTO @G
@TO @OO
G$=G$+G$[O]
G$[O]=O$
@G
GOTO O$+@G[O]+G$[O]+T$[O]
@GO @GT
T$[O]=O$
GOTO @OO
@TT @OT
T$=T$+G$[O]
GOTO @OO
\$\endgroup\$
1
  • \$\begingroup\$ Using these constructs, can you create unbounded data structures? They could be in the form of arrays, lists, strings, or even integers, as long as they're not limited in size by the implementation. If not, the language isn't Turing-complete. For example, in QBasic, trying to DIM an array larger than 64KB (that's 16384 SINGLE numbers) gives a Subscript out of range error. (This is different from running out of memory, which will happen with any language and is considered an implementation difficulty rather than a limitation of the language.) \$\endgroup\$
    – DLosc
    Feb 24, 2017 at 21:21
1
\$\begingroup\$

Turing Machine But Way Worse - 4 characters

0 1\n (The \n should be replaced with an actual newline)

States can be represented in binary and everything else uses a 0 or 1.

Spaces separate different parts of a command and newlines separate commands.

\$\endgroup\$
1
\$\begingroup\$

Perl 6, 9 characters

~^<>.EVAL

The goal here is to EVALuate arbitrary strings. To do this, we can use the ~^ to bitwise xor strings into other strings, as long as we have enough characters, as well as the <<>> to delimit the actual strings themselves. There's some fiddling in avoiding syntax errors when using <>, but we can generally use the characters .EVAL~^ to produce more characters.

For example, if you wanted to create the string 4*9, you could do:

<<...>>~^<<VEV>>~^<<LAA>>

And to evaluate that, you wrap it in more <<>>s and EVAL it a few times:

say <<<<...>>~^<<VEV>>~^<<LAA>>>>.EVAL.EVAL

Try it online!

Unfortunately, we can't get the full range of ASCII with just xors, so we can use ~& inside the evaluated strings, in the form 'string'~&'string'. This gets us a Turing complete subset of ASCII, but not all of it, so for convenience we can xor it once more to get a full subset.

For reference, a full program will go through 5 EVAL stages before executing:

<<<<........EE............................>>~^<<.E.....EVVE.....E.....................>>~^<<.V.....VLLVEEE..V....E.....E..EEEE..E.>>~^<<EL.....L~~LLVV.ELE.VEL.....L..LLLL.ELE>>~^<<L^.....^^^^~~L.V^L~^L~EE..E~~^~~~~^^~L>>>>
(<< ........EE............................ >>~^<< .E.....EVVE.....E..................... >>~^<< .V.....VLLVEEE..V....E.....E..EEEE..E. >>~^<< EL.....L~~LLVV.ELE.VEL.....L..LLLL.ELE >>~^<< L^.....^^^^~~L.V^L~^L~EE..E~~^~~~~^^~L >>)
'/.....//wm_.=/'~&'wEE..Ew~^wwww^5w'
'..'~^'weW5'
say 1

Here is a full program generator that can handle ASCII characters, and an example Hello World! program.

\$\endgroup\$

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.