108
\$\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\$
  • 90
    \$\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
  • 21
    \$\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

51 Answers 51

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 (5 or later), 15 characters

02367?\abcdeitu

We've had a few previous answers in Java. The basic approach in all of them is to a) identify a minimal Turing-complete subset of the language, and b) find a minimal way to express the constructs of that language in Java's syntax.

Hexagraph notation

Let's look at b) first. As explained in @Poke's answer above, Java has a hexagraph syntax (analogous to C's trigraph syntax) to allow arbitrary characters that might not exist in your character set to be included in your program. For example, a newline could be written as a literal newline, but it could also be written as the hexagraph \u000a; the hexagraph consists of \u followed by four hexadecimal digits, specifying the character's Unicode codepoint. Unlike C's trigraphs, which can only be used for a few awkward characters, a Java hexagraph can be used for absolutely any Basic Multilingual Plane character we might happen to need (including printable ASCII characters).

The previous records, 17 by @Poke, and 16 by @Poke and me, were based on taking relatively normal-looking Java programs and simply trying to hexagraph every character in them: your character set is then based on which nybbles occur in the codepoints you're using. If a nybble occurs in two different codepoints, it typically saves character set entries to include that nybble in the character set, so you can construct the codepoint with it. One minor improvement for this entry is that if a nybble only occurs in a single codepoint, we may as well include that codepoint in our character set directly: the resulting programs will end up slightly shorter.

Of the 16 nybbles, this entry manages to omit 2 entirely: 5, and 8. 4, 9, and f are also omitted; each is only needed to write a single character (t = U+0074, i = U+0069, and ? = U+003F respectively), and including that character directly leads to shorter and "more readable" programs. One final saving is available from a/1: we don't need a as a nybble to write any character, we do need to be able to produce U+0061, a's codepoint, but we don't need 1 for any other codepoint. So a and 1 are redundant with each other: we need at least one of them, but don't need both; and omitting a/1, 5, and 8 from our base set of 18 characters \u0123456789abcdef gives us our final character set.

Of course, this means that we have to avoid many more missing characters than in the other entries. In particular, we can no longer create the boilerplate for a main method (which must have a parameter of type String; S = U+0053 contains the forbidden nybble 5). So we're going to need a radically different way of running a Java program.

Java as an interpreter

Java is normally a compiled language; a typical workflow is to use the compiler javac to compile your Java source files into one or more .class files, and then the JVM java to run those source files, and take the output of java as the output of the program. None of your code actually runs at compile time, so the output of javac is typically regarded as uninteresting.

Nonetheless, javac does contain some nontrivial functionality; Java is, after all, a fairly complex language. We can take a single Boolean of output from the compiler javac by checking to see if there are compile errors, looking at its exit code: if the program has errors, that will produce a different output from if the program doesn't have errors. Of course, Java being a compiled language, an erroring program might not seem particularly useful from a Turing-completeness point of view: if it has errors, it won't actually run, so how could it be Turing-complete? However, it turns out that type-checking Java programs is in of itself a Turing-complete operation; all we need to be able to do is to be able to compile programs from some Turing-complete language into Java's type system, in such a way that, in order to determine whether the resulting program is valid Java or not, the type-checker will have no choice but to run the program we compiled.

The Subtyping Machine

The Subtyping Machine is an esoteric programming language that was "back-derived" (by Radu Grigore in 2017) from Java's type system, looking at the algorithm that Java actually uses to determine whether an expression has the correct type or not. Here's an example I wrote of what this sort of program looks like:

interface xx {}
interface A<x> {}
interface B<x> {}
interface d<x> extends
  A<s<? super X<? super B<? super s<? super X<? super d<x>>>>>>>,
  B<x>, xx {}
interface X<x> extends xx {}
interface s<x> extends xx {}

class x {
  d<? super X<? super d<? super X<? super d<? super X<? super s<xx>>>>>>> xc;
  A<? super s<? super X<? super d<xx>>>> xd = xc;
}

The bulk of the program is basically just a lot of interfaces extending each other with contravariant generic type parameters. If you have A<x> extends B<…<? super x>>, and you're trying to see whether an expression starting A<…> can be stored in a variable of type B<…>, what ends up happening is that the first type ends up getting potentially much more complicated as the generic parameter is expanded, and then the resulted B<…> wrappers cancel, but (because the types are contravariant) the two parameters basically swap roles within the type-checking algorithm. The result is a type-checking problem that could potentially be more complex than the problem we started with; the operation effectively boils down to popping two stacks and then pushing onto one of them based on the value popped. You have to push onto the two stacks alternately, but that isn't a major issue, so we effectively end up with a two-stack machine, and two stacks are enough for Turing-completeness. Full details of how the language operates are in the link at the start of this section.

Minimizing the character set of The Subtyping Machine

Now that we have a Turing-complete operation that can be run by java, thus avoiding the need for the public static void main(String[] a) boilerplate that's required for the benefit of javac (but not java), the final step is to reduce its character set as far as possible.

There are some characters that are absolutely necessary. To use this technique, we need to be able to declare interfaces (interface … {}) and contravariant type parameters (<? super …>), which already ties up many of our nybbles. The main problem I encountered in this solution was in trying to avoid the nybble 8, most notably used by ( = U+0028 and x = U+0078. (1/a end up not being used for anything important, e.g. they're merged in @Poke's answer just as they are here; and 5 turns out to be used only for e=U+0065 and u=U+0075, but fortunately both those characters are needed for other reasons, e as nybble and u because it's part of the \u hexagraph introducer, so we never need to write them as hexagraphs. Unlike in the previous record-holder, c is unavoidable because we need it for <=U+003c, pretty much unavoidable for any type-system-based approach.)

Avoiding parentheses is a little annoying, but not that hard; in fact, I did it in the example program above. The reason they'd be helpful is that once we declare a bunch of interfaces extending each other, we actually need to cause the type checker to type-check something; Radu Grigore's original program did this by defining a function. The approach I used above works by defining two variables and assigning one to the other, which will also force the type-checker to be involved; fortunately, neither ==U+003d nor ;=U+003b uses a forbidden nybble.

Avoiding x is harder; despite being pretty rare as letters go, it's needed to spell extends, the keyword Java normally uses to introduce a subtyping relationship. That might at first seem impossible to avoid, but we do have an alternative; when a class extends an interface, Java uses the keyword implements instead, which despite being longer doesn't contain any problematic characters. So as long as we can divide our program into classes and interfaces, with the only hardcoded subtyping relationships being between a class and an interface, we can make the program work. (We also have to use the class keyword, but that contains only letters we already have: interface implements.) There are several possible approaches that work, but one simple approach is to ensure that classes and interfaces always alternate within the two types being compared; that means that at any point in time, we're always comparing a class with an interface (and because we unwrap both stacks one level at a time and the direction of a comparison is reversed with every step, we're always checking to see whether a class implements an interface rather than the other way round, which is impossible in Java).

My compiler from The Subtyping Machine to compile-time Java proves the Turing-completeness of this 15-character subset of Java by being capable of compiling to it; use the -jj option and it'll output in this subset, rather than in more readable Java (by doing things like choosing a class/interface split that avoids the use of the extends keyword – in a marginally more sophisticated way than is described above – and changing variable names to only use the letters that exist in the character set, and of course hexagraphing any character that needs to be).

I was hoping to produce a more complex example, but I've spent enough time on this as it is, so I thought I may as well post it. After all, it shaves one character off the best known character set via ridiculous means, and isn't that what this question is all about?

\$\endgroup\$
4
\$\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\$
  • 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 '17 at 5:16
  • \$\begingroup\$ You can use interface instead of class, which allows you to drop the public. \$\endgroup\$ – corvus_192 Feb 24 '17 at 16:11
  • \$\begingroup\$ Also, replace the [] with ... to save another character. \$\endgroup\$ – corvus_192 Feb 24 '17 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 '17 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\$ – Robert Fraser Sep 21 '17 at 7:12
4
\$\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\$
  • 6
    \$\begingroup\$ Why not just put the space in the list? \$\endgroup\$ – mbomb007 Feb 21 '17 at 21:45
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\$
  • \$\begingroup\$ I don't think you need the ", I tried removing them in your example program. \$\endgroup\$ – Erik the Outgolfer Feb 26 '17 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\$ – AdmBorkBork Feb 27 '17 at 13:53
3
\$\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\$
  • \$\begingroup\$ ≢≢⍬ does not look right. Should it be ≢⍬⍬? \$\endgroup\$ – CalculatorFeline May 30 '17 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 '17 at 20:12
  • \$\begingroup\$ Save a character: ⍎⎕AV[≢],). One-based indexing obviates the need for any "zeroth" character. \$\endgroup\$ – Adám Jun 2 '17 at 14:21
  • \$\begingroup\$ Change any code to an expression consisting of those 8 chars: Try it online! \$\endgroup\$ – Adám Jun 2 '17 at 15:36
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\$

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

Scala, 12 chars

I dont't have a degree in computer science, so I'm not sure if this is valid. Feel free to correct me.

(),:;=>[]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\$
  • \$\begingroup\$ I don't think you need to have a computer science degree to know whether something is Turing-Complete... \$\endgroup\$ – Julian Lachniet Feb 21 '17 at 23:36
  • \$\begingroup\$ @DLosc Right, you'd have to add either a newline or a semicolon. \$\endgroup\$ – corvus_192 Feb 24 '17 at 16:02
2
\$\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\$
2
\$\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
    \$\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 '17 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 '17 at 18:11
  • \$\begingroup\$ () are also only used for convenience. You could write the entire thing using only \/. \$\endgroup\$ – ETHproductions Feb 24 '17 at 18:13
  • \$\begingroup\$ Thanks. I am very new to this language, so I wouldn't know this. \$\endgroup\$ – Comrade SparklePony Feb 24 '17 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\$ – Ørjan Johansen Feb 27 '17 at 2:52
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\$
  • \$\begingroup\$ ASCII or ASKII? \$\endgroup\$ – NoOneIsHere Feb 20 '17 at 17:23
  • \$\begingroup\$ @NoOneIsHere Opps! Thanks for that. \$\endgroup\$ – Christopher Feb 20 '17 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 '17 at 22:25
  • \$\begingroup\$ @Laikoni nice! That will cut this down! \$\endgroup\$ – Christopher Feb 20 '17 at 22:26
  • \$\begingroup\$ This also needs a Turing proof. \$\endgroup\$ – Brian Minton Feb 24 '17 at 13:48
1
\$\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\$
  • 1
    \$\begingroup\$ I'd like to know who downvoted this. \$\endgroup\$ – Esolanging Fruit Feb 21 '17 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 '17 at 1:22
  • 1
    \$\begingroup\$ And yet the Unary answer gets 21 upvotes? \$\endgroup\$ – G B Feb 22 '17 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 '17 at 9:36
  • \$\begingroup\$ @user62131 Then why downvote this answer? \$\endgroup\$ – MilkyWay90 Mar 3 at 3:54
1
\$\begingroup\$

Unlambda, 3 characters

sk`

It's a turing tarpit of course.

\$\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\$
  • \$\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 '17 at 21:21
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\$
1
\$\begingroup\$

Keg, 9 characters

~+-*/:{|}

This subset of Keg was shown to compile to Volatile, which was in turn compiled to the Minsky Machine by TuxCrafting. The lack of output commands does not matter because Turing-completeness does not require output capabilities.

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

HSPAL, 6 characters

012346

The BF interpreter linked in the esolangs article uses only the digits 0-4, plus 6, for all tokens except number literals and label IDs. It uses at most 116 distinct label IDs [the actual number is probably slightly lower, but I don't feel like counting them right now], which can be reassigned to use only the reduced 6-digit alphabet; and the BF instructions can likewise be reassigned to different code points; therefore all other digits can be excluded from the alphabet while leaving the language turing complete.

\$\endgroup\$
0
\$\begingroup\$

Decimal, 7 characters

012345D

These three commands are necessary to be Turing-complete:

  • 3 - I/O
  • 4 - MATH
  • 5 - COND

0, 1 and 2 are used as arguments to the commands. D is like the closing parenthesis for some commands.

How it's Turing-complete:

  • 310 reads a character to the stack (3=I/O, 1=from input, 2=to stack)
  • The first four arguments to command 4 MATH are +, -, *, / (1, 2, 3, 4). For example, calling 41D takes DSI and DSI-1, pops them, and pushes the result of adding them together.
  • Command 5 COND is a conditional. Jumps to the next COND if the DSI value is falsy.
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think you need 3. I/O isn't required for turing completeness \$\endgroup\$ – 12Me21 Feb 8 at 17:27
0
\$\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\$
-3
\$\begingroup\$

Binary Lambda Calculus, 2 characters (with specified encoding).

http://www.ioccc.org/2012/tromp/hint.html

The programming "word" size is two bits long. All possible symbols are used. However the program is passed as a string in which only the low bit of each symbol is significant. Therefore the only symbols we need are 0 and 1.

\$\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.