131
\$\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\$
25
  • 98
    \$\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\$ Feb 20 '17 at 15:35
  • 8
    \$\begingroup\$ @MartinEnder I'd be especially interested to see answers in languages like Java or C. \$\endgroup\$ Feb 20 '17 at 15:41
  • 11
    \$\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
  • 27
    \$\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

64 Answers 64

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

ARM assembler (gas), 14 chars

Newline and space


 1bdlrstu:[],

With this, we have more than enough options for Turing completeness, including:

lbl:                  // label
ldrb r1,[r11]         // r1 = *(u8*)r11;
ldrsb sb,[lr]         // sb = *(s8*)lr;
ldr r1,[r11],1        // r1 = *(u32*)r11; r11 += 1
strbls sl,[r11,1]     // if (ls) ((u8*)r11)[1] = sl;
str r1,[r11],11       // *(u32*)r11 = r1; r11 += 11;
strb sl,[lr,r1]       // ((u8*)lr)[r1] = sl;
l:                    // another label
subs sb,r1,1          // sb = r1 - 1; set flags
rsb r1,111            // r1 = 111 - r1;
lsls sl,r1,1          // sl = r1 << 1; set flags
lsr lr,r1,1           // lr = r1 >> 1;
lsrlslsls:            // Moar labels
sublt sb,sl,r1,lsr 11 // if (lt) sb = sl - (r1 >> 11)
tst r1,r1             // flags = r1 & r1;
blt lbl               // if ((s32)x < (s32)y) goto lbl;
bls l                 // if (x <= y) goto l;
b lbl                 // goto lbl;

We have five registers: r1, sb (old name for r9, may be reserved), sl (old name for r10), lr, and r11. We only need two though: a pointer and an accumulator.

We have arithmetic with sub(s), lsl(s), lsr(s), and rsb(s). Technically we only need subs r1,1 to generate any possible value, but the others are a very helpful bonus.

We have control flow with labels mixed with b, blt and bls (unconditional branch, branch if less than, branch if unsigned lower or same), as well as conditional instructions. To compare, we have tst and the flag updating with the arithmetic instructions.

We have unbounded memory storage, given that one of the registers points to a mutable tape and we have unlimited RAM. I use r11 as an example. We can move this pointer forward with postincrement in ldrb/strb (or with a bunch of subtraction), and backward with sub. Being RISC, we need to have variants of ldr and str to load and store from memory, something the other ARM answer didn't address (pun intended).

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

Actually, 4 chars

'u+≡

We construct strings with 'u+, and then we use to eval them. The Actually command uses python eval, which was already proven turing complete in the Whispers v1 answer.

If you have a length 1 string and you increment it with u, you get the next char in the Actually codepage. We can make length 1 strings with '. The problem is, we can't create a space. We only have increment. However, at the very end of the actually codepage is a non-breaking space. And Python is fine with the non-breaking space.

Here's the I combinator:

''uu'+uuuuuuuuuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuu+'≡uuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+'+uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu+''u+

Try it online!

\$\endgroup\$
-2
\$\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\$
1 2
3

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.