Minimal maximum byte for Turing Completeness

Question

Summary

We already have a challenge for the minimal number of characters for Turing completeness. But what about the minimal maximum byte?

Challenge

For a language of your choice, find a subset of characters that allows your language to be Turing complete with the minimal maximum byte value.

Example

If your language is using the UTF8 code page and Turing complete using only the characters abcd(), these characters have the byte values 97, 98, 99, 100, 40, 41, and the maximum there is d = 100, so your score would be 100.

Scoring

Your score is the maximum byte value of your Turing complete subset, expressed in the code page of your language's interpreter. For most languages this will be either LATIN-1 or UTF8, but if your language uses a different code page (such as Jelly) use that to score instead.

In the unlikely event that you require multibyte characters to be Turing complete, just use the maximum byte in the multibyte sequence to score. For example, if your UTF8 language required Ȧ, this is encoded as the literal byte sequence 200, 166, so it would score 200.

The lowest score wins.

Notes

• The minimum score is 0, the maximum is 255.
• For some languages (cough) this challenge will be trivial to score low on. I urge you to upvote interesting answers over trivial ones.
• Provide an explanation of why your subset is Turing complete.
• Your subset only needs to be Turing complete, it does not need to be able to use every feature of the language.

Answer 1

Python 2 with exit code, 102 (f)

def TM_SIM(TRANSITIONS, STATE, TAPE=[], HEAD_POS=0):
	TAPE += ["X"]
	HEAD_POS += HEAD_POS < 0

	SYMBOL = TAPE[HEAD_POS]
	STATE, NEW_SYMBOL, HEAD_DIRECTION = TRANSITIONS[(STATE, SYMBOL)]
		
	TAPE[HEAD_POS] = NEW_SYMBOL
	HEAD_POS += HEAD_DIRECTION
			
	STATE == "REJECT" < 1/0
	STATE != "ACCEPT" == TM_SIM(TRANSITIONS, STATE, TAPE, HEAD_POS)

Try it online!

This code limits itself to the keyword def for highest character f. The function definition is used for looping via recursion. Python's logical short-circuiting is used for control flow, avoiding the need for a keyword like if, and, or, or while. For example, the recursive call in STATE != "ACCEPT" == TM_SIM(...) does not happen if we're in the accept state -- because the first inequality already fails, Python moves on without evaluating further.

Because none of the usual output method work (print, return, exit, etc), we return via exit code by terminating with or without error. So, this code is limited to decision problems. In practice, large inputs will give a stack overflow ("maximum recursion depth exceeded").

The code shown is a function simulating an arbitrary Turing machine that's given as input, which is of course Turing complete. The TIO shows it tested with a Turing machine that checks palindromes.

We avoid all keywords except the def. Since the only characters bigger than lowercase in letters in byte value are {|}~, it was easy to do without them too. For clarity, the variables in the code have been given readable names, using uppercase since these are smaller than all lowercase letters. We could get rid of these and many other symbols, though this of course wouldn't affect the score.

Answer 2

Haskell, score 61 (=)

Characters used: !#$%&()=

The SKI combinator calculus can be implemented in Haskell with nothing but basic function definition, using !#%& as identifiers. Infix function application $ is used to save on parentheses and strip down one character from both S and fix. Finally, K only takes two arguments and can be more shortly defined as an infix operator.

S combinator: s x y z = x z (y z)

(!)(#)(%)(&)=(#)(&)$(%)(&)

K combinator: k x y = x

(!)#($)=(!)

fix combinator: fix f = f (fix f)

(&)(!)=(!)$(&)(!)

Since Haskell is a strongly typed language, the fixed-point combinator fix is needed in order to make (typed) combinatory logic Turing-complete.

The I combinator is not strictly required since it is extensionally equivalent to SKK, but it can be defined as (*)(!)=(!).

Try it online!

Answer 3

C (gcc), score=61 (=)

$01234567;=

This abuses the linker by forming a machine language program that spans several scalar variables and avoids array characters such as []{}.

The following is an example of a "Hello, World!" "program" that should work on Linux and OSX for x86 and x86_64.

$=01672007152;$$=011000000000;$$$=015733066145;$$$$=015725620054;$$$$$=04131066162;$$$$$$=010060030412;$$$$$$$=02141007620;$$$$$$$$=013100000000;$$$$$$$$$=015224251132;$$$$$$$$$$=026024655401;$$$$$$$$$$$=020063250004;$$$$$$$$$$$$=030304142203;$$$$$$$$$$$$$=037777630536;$$$$$$$$$$$$$$=012625655307;$$$$$$$$$$$$$$$=01134122;$$$$$$$$$$$$$$$$=0503601000;$$$$$$$$$$$$$$$$$=06127257132;$$$$$$$$$$$$$$$$$$=01700330300;$$$$$$$$$$$$$$$$$$$=0141405;

Try it online!

Answer 4

Whitespace, score = 32

Characters: \t\n (chrs 32 9 10)

The only legal chars in the language.

Answer 5

PHP, Score = 82 (R).

Rationale:

Let's start at the end of the ASCII range, and work backwards until we find a character that's required for PHP.

PHP is case-sensitive only for user-defined things (variable names, constants), and is case-insensitive for all other things, so we can ignore the lowercase range.

Other than lowercase characters, the only characters above the uppercase range are:

• 0x7f - unused.
• ~ - used only for bitwise negation, unnecessary for Turing completeness.
• { and } - used for blocks, but PHP has an "alternative syntax" for control structures that doesn't use characters above the uppercase range.
• | - used for boolean OR (|, |=, etc), unnecessary for Turing completeness, and for logical OR (||, ||=, etc), which has an alternate text form OR.
• ` - used only for external command execution, unnecessary for Turing completeness, and anyway there are alternatives (EXEC(), PASSTHRU(), SYSTEM(), etc)
• _ - used in many library function names and all compile-time constants, but not used by any keywords, so, since methods can be called dynamically, we can call methods that contain underscores by replacing them with CHR(95).
• ^ - used only for bitwise XOR, and in regexes, neither required for Turing completeness.
• [ and ] - used for array indexing, which poses a problem, but array_pop and friends can be used instead.
• \ is used for character escapes, unnecessary for Turing completeness, and escaped characters can be generated using CHR() and similar tricks anyway.

This means our max must lie in the uppercase characters.

We could trivially use eval() and chr() to evaluate any string of numbers as PHP code, which would give us a max character of V... but I think we can do better!

If we can do everything brainfsck can, then it'll be Turing complete, so let's write one. I'll replace the [ ] square braces of normal brainfsck with ( ) round braces, just so I can have the brainfsck program inline without using any high characters.

Proof of concept:

<?PHP
// Create function refs, for those which have characters too high.
$FILL = 'ARRA' . CHR(89) . CHR(95) . 'FILL'; // Array_fill to create the tape.
$CHOP = 'ARRA' . CHR(89) . CHR(95) . CHR(83) . 'LICE'; // Array_slice for array indexing.
$POP = 'ARRA' . CHR(89) . CHR(95) . CHR(83) . 'HIF' . CHR(84); // Array_shift for array indexing.
$DEPOP = 'ARRA' . CHR(89) . CHR(95) . CHR(83) . 'PLICE'; // Array_splice for array inserting.

$LEN = CHR(83) . CHR(84) . 'RLEN'; // Strlen
$LOP = CHR(83) . CHR(84) . 'R' . CHR(95) . CHR(83) . 'PLI' . CHR(84); // Str_split

// "Hello world!" - note using round braces instead of square in the brainfsck code.
$IN =  (">+++++++++(<++++++++>-)<.>+++++++(<++++>-)<+.+++++++..+++.>>>++++++++(<++++>-)<.>>>++++++++++(<+++++++++>-)<---.<<<<.+++.------.--------.>>+.>++++++++++.");
$INLEN = $LEN($IN);
$IN = $LOP($IN);

// Init tape with 10 zeros (add more for longer tape).
$A = $FILL(0,10,0);

// Set $AA ptr to first cell of tape.
$AA = 0;

FOR ($I = 0; $I < $INLEN; $I++):
    // Extract element: $CH = $IN[$I].
    $CH = $CHOP($IN, $I);
    $CH = $POP($CH);
    // Increment element at $I.
    //$CH++;
    //$CH = $FN($AA, $I, 1, $CH);
    
    // Only need one of '+' or '-' for TC if memory wraps.
    IF ($CH == '>'):
        $AA++;
    ENDIF;
    IF ($CH == '<'):
        $AA--;
    ENDIF;

    // Only one of '+' or '-' is critical for Turing completeness.
    IF ($CH == '+'):
        // Increment element: $A[$AA]++;
        $ID = $CHOP($A, $AA);
        $ID = $POP($ID);
        $ID++;
        $DEPOP($A, $AA, 1, $ID);
    ENDIF;
    IF ($CH == '-'):
        // Decrement element: $A[$AA]--;
        $ID = $CHOP($A, $AA);
        $ID = $POP($ID);
        $ID--;
        $DEPOP($A, $AA, 1, $ID);
    ENDIF;

    IF ($CH == ')'):
        $ID = $CHOP($A, $AA);
        $ID = $POP($ID);
        IF ($ID):
            FOR ($LOOP = 1; $LOOP > 0; ):
                $CH = $CHOP($IN, --$I);
                $CH = $POP($CH);
                IF ($CH == '('):
                    $LOOP--;
                ENDIF;
                IF ($CH == ')'):
                    $LOOP++;
                ENDIF;
            ENDFOR;
        ENDIF;
    ENDIF;

    // I/O is non-critical for TC.
    IF ($CH == '.' ):
        $ID = $CHOP($A, $AA);
        $ID = $POP($ID);
        ECHO CHR($ID);
    ENDIF;
ENDFOR;

Possible improvements:

I don't see a way to avoid using CHR() for array indexing without using something worse, like backslash, or string manipulation functions that use S.

And I don't see a way to avoid FOR() for looping back without using something worse like GOTO, WHILE, or the {} of a recursive function definition.

If we can get rid of those two keywords, the next highest is the P in <?PHP, which is required, at least in later versions of PHP that deprecate short open tags. However, they have made a commitment that the short echo tag, <?= will always be supported, so that could perhaps be exploited to execute arbitrary PHP. Then there are the O's in ECHO. However, I/O isn't critical for Turing completeness, so we could just remove that. Then there's the N in ENDIF, and the I and F in IF, which could be replaced by the ternary operator, ?:.

But even if there's a way to avoid using any keywords or library functions by name, variables must begin with an alphabetic or underscore character, so I suspect we'll definitely need at least A.

Answer 6

05AB1E, score: 86

+1 .VB

These characters have the codepoints [43,49,32,46,86,66] in the 05AB1E codepage, of which V=86 is the maximum.

My answer for the Fewest (distinct) characters for Turing Completeness challenge in 05AB1E which I posted just yet is: +X.VB. With these 5 bytes, X=88 would have been the maximum. We avoid the X by using 1 and a space instead. After that V=86 is the maximum.
With the remaining 6 bytes we can:

• +: Pops the top two items on the stack, and adds them together
• 1 : Push 1 to the stack
• .V: Pops and evaluates the top string as 05AB1E code
• B: Pops the top two items on the stack, and does base-conversion

I've tried to get rid of V, which would only be possible with .E (execute as Python code - exec). Now we're using .V to evaluate and execute as 05AB1E code, for which we can first create the entire strings with certain single-byte builtins like J (join), « (append), etc. But if we would use .E we can't do that anymore. A potential fix for this is switching from 05AB1E to 05AB1E (legacy). In the legacy version (which is built in Python) we can use + to concatenate characters, which isn't possible in the new version (which is built in Elixir). Unfortunately, the .E builtin is (evaluate as Python code - eval) in the legacy version, and .e is exec. With just eval we unfortunately can't do everything we want, like checking if the input is a prime number. (Maybe we can, but my Python knowledge is too limited for that. If someone knows a piece of Python 3 code which can be wrapped within eval("...") and will check if the input() is a prime number, lmk.) And the e in .e would be even higher than .V, so it's pointless to use that instead.

Try it online:

Here a few example programs using these six bytes:

Try it online: 2+2.
Try it online: Check if the input is a prime number.
Try it online: Print "Hello, World!".
Try it online: Print the infinite Fibonacci sequence.

Answer 7

Lenguage, score = 1 ()

Lenguage only cares about the length of the file, so we can use any character (in this case U+0001).

Yes, I am aware that I can use null bytes, but I wanted to give a fair chance to other people, so I made it 1.

Answer 8

JavaScript (Node.js), score 62 (>)

$=>()

Check the score online!

Untyped lambda calculus again.

I = $=>$
K = $=>$$=>$
S = $=>$$=>$$$=>$($$$)($$($$$))

I think this is optimal, because all built-ins and keywords are banned now.

Answer 9

Brainfuck, Score = 93 (]).

>   Move the pointer to the right.
<   Move the pointer to the left.
+   Increment the memory cell at the pointer.
-   Decrement the memory cell at the pointer.
.   Output the character signified by the cell at the pointer.
,   Input a character and store it in the cell at the pointer.
[   Jump past the matching ] if the cell at the pointer is 0.
]   Jump back to the matching [ if the cell at the pointer is nonzero. 

I/O is not required for Turing completeness, so . and , are optional: a canonical Turing machine leaves its calculated answer on the tape. However, I believe all other commands are required, so the highest codepoint the language uses, ], is required.

There are a number of trivially-similar languages. I'll cover these here as well, unless people feel they are genuinely worthy of separate answers. I have assumed for each language that their commands are case-sensitive unless otherwise stated.

You only need one of the two BF instructions - and + for Turing completeness. And if the tape/memory is limited and wraps around, then we only require one of < and >, too. I've updated the below lists to take these into account.

Identical to BF for our purposes:

ASCII art-, Score = 93 (]).

BFFB, Score = 93 (]) Requires code be a palindrome but uses the same characters as BF.

LolKek, Score = 93 (]).

Pi, Score = 93 (]).

ReverseFuck, Score = 93 (]).

RRF, Score = 93 (]).

BF-, Score = 93 (]).

.

TrivialBrainfuckSubstitutions:

???, Score = 59 (;) 45 (-) Not quite a trivial substitution, but close enough. Omitted ?, ; and . as unnecessary for TC.

Alphuck!, Score = 115 (s).

And then, Score = 122 (z from required preamble).

Anguish, Score = 98 (U+2062) 97 (U+2061). Omitted U+2062 as unnecessary for TC.

ASCII art, Score = 124 (|).

Blub, Score = 117 (u from Blub? Blub!).

BrainFNORD, Score = 115 (s in eris) 112 (p in pineal). Omitted eris and fnord as unnecessary for TC.

btjzxgquartfrqifjlv , Score = 90 (Z of ZXG).

Colonoscopy, Score = 123 (} of }}).

Fluffle Puff, Score = 116 (t) 115 (s of *gasp*).

FuckbeEs, Score = 115 (s).

Fuckfuck, Score = 116 (t of b..t).

GERMAN, Score = 85 (U of ADDITION or SUBTRAKTION).

Headsecks, Score = 7 (U+07).

Integral, Score = 120 (x of the polynomial expressions).

LMBC, Score = 125 (} of n\n\\n\>\<" }*/ continue;).

Morsefuck, Score = 46 (.).

Omam, Score = 46 (y of this ship will carry).

Oof, Score = 111 (o of oooooof).

Ook!, Score = 107 (k of Ook? Ook!).

oOo CODE, Score = 111 (o of OOo).

Pikalang, Score = 117 (u from chu).

POGAACK, Score = 112 (p from poock?).

PPAP++, Score = 86 (V from I HAVE AN APPLE, or I HAVE PINEAPPLE,).

Revolution 9, Score = 121 (y from if you become naked) 118 (v from Revolution 1).

RISBF, Score = 47 (/ of /+)

Roadrunner, Score = 112 (p from MEEp).

Ternary, Score = 50 (2 from 02).

There Once was a Fish Named Fred, Score = 119 (w from was) 114 (r from Fred).

tinyBF, Score = 124 (|).

Unibrain, Score = 48 (0, needs at least 1 alphanumeric).

VerboseFuck, Score = 125 (} of }; [... etc]).

wepmlrio, Score = 119 (w).

Wordfuck, Score = 32 ( space) or 33 (!) depends if chars < 32 are considered words.

ZZZ, Score = 122 (z from z-z).

.

Turing tarpits:

Braincrash, Score = 33 (!).

Placement, Score = 63 (?).

.

Binary:

Binaryfuck, Score = 255 (U+FF) or better???

Brainfoctal, Score = 255 (U+FF) or better???

CompressedFuck, Score = 255 (U+FF) or better???

ShaFuck, Score = 255 (U+FF) or better???

Triplet, Score = 255 (U+FF) or better???

ZeroBF, Score = 255 (U+FF) or better???

Now, arguably, the score could be 49 (1), or 1 (U+01), or 255 (U+FF), or whatever. I pick 255.

These each replace the 8 BF command characters with their 3-bit binary equivalents, to give an octal number from 0 to 8. This converts the program to a binary stream of ones and zeroes, which can be represented as ASCII 1 and 0 characters, or as byte values, or as bit values, or as any base you like, hence the three possible scores.

The reason for my score of 255 for the bit-values version of binary BF programs is that ] typically maps to 111, so three of them in a row gives you a byte of all 1s, or 255.

It could be argued that you COULD write a Turing machine in these languages which never used three ] commands in a row. So my score may be less generous than it need be. You can prove this, if you like! :D Until then, I'm scoring them 255.

Well, in the case of ShaFuck, it's more complicated, but still... I don't have proof that it doesn't require a 0xFF byte somewhere, so I'm giving it a score of 255 until proven otherwise.

Golunar, Score = 59 (9) or better???

So this is an interesting one. It takes a Unary program (well, any of the above "single character" solutions, and converts it to a decimal string. In this way it is much like the other "binary" options, except it's explicitly stated to be a decimal number, one presumes in ascii.

That means that, if it could be proven that any program (or at least a Turing machine program) could be written in Unary that had a length that was describable without any 9s, the score would be able to drop, perhaps even as low as 49 (1).

Replacement by sequences of a single character:

A, Score = 65 (A).

Ecstatic, Score = 33 (!).

Ellipsis, Score = 46 (.) or 38 (U+2026 ellipsis).

Lenguage, Score = 0 (U+00).

MGIFOS, Score = 42 (*).

Unary, Score = 48 (0) or 0 (U+00).

These are really just the binary options above, taken as a number that describes the length of a string made by repeating a single character.

Other weird stuff:

BF-RLE, Score = 93 (]) to 247 (U+F7BFBFBF).

Run-length encoded BF. There are various methods. Base-10 prefix or suffix methods, or indeed any standard base up to 36 gets the same score as regular BF (because ] is above the uppercase range). Base 37 then typically uses the lowercase range, for a score of 97, and each additional base up to base 62 gets one worse. Bases above 62 need additional non-alphanumeric characters, but these can be selected from those below the lowercase range until those run out at base 114 (assuming 8 characters remain reserved for the BF code itself), and they then get worse by one for each base increase to base-128. After that point, UTF-8 can be used to slow the rise of the limit so that it never hits 255 for any base within the limit for UTF-8's ability to represent (some 4 million).

I dunno:

K-on Fuck

( ͡° ͜ʖ ͡°)fuck

These use extended characters I can't be arsed to look up.

Answer 10

Python 3, score 109 (m)

lambd :()

Check the score online!

We can implement untyped lambda calculus using just these chars:

I = lambda a:a
K = lambda a:lambda b:a
S = lambda a:lambda b:lambda d:a(d)(b(d))

With the known bound of m, we can't use any of exec, eval, import, for, while, yield. def is still available, but I doubt it will improve the score because I think making it Turing-complete necessitates the use of return.

Answer 11

J, score 94 (^)

 "#%()*+.0123456789:<=]^

Check the score online!

The winning J answer for least unique chars uses u: (convert charcodes to chars) to construct arbitrary string from integers. I decided to avoid u and find a more proper way for TC-ness.

Assuming ^:_ (repeat until converges) is hard to avoid, I decided to build a translation from FRACTRAN, as it looked easy enough to translate to (number_manipulation)^:_(starting_num).

A FRACTRAN program is defined as a sequence of fractions, and it runs like this: given a program 5/3 3/2 and some starting number n,

• If n is divisible by 3, multiply n by 5/3.
• Otherwise, if n is divisible by 2, multiply n by 3/2.
• (The "otherwise" chain continues for longer programs)
• If n did not change in this iteration, halt. Otherwise, move to the start of the program and continue with the updated value of n.

The if-then-else constructs can be translated to arithmetic:

If a then b else c = (a>0) * b + (a==0) * c
J: (b*(0<a))+c*0=a

The if-part says "n is divisible by a constant m". One would normally use the modulo function | for this, but it's way too high in ASCII, so I devised a way to simulate modulo using base conversion:

n modulo m = convert n into base m, interpret as base 0 and get an integer back
J: 0#.0 m#:n

The then- and else-parts are easy, because they can be simulated using multiply *, divide %, and self ].

So the translation of two-fraction FRACTRAN program 5/3 3/2 looks like this:

(((]%3"0)*5*0=0#.0 3#:])+((((]%2"0)*3*0=0#.0 2#:])+(]*0<0#.0 2#:]))*0<0#.0 3#:]))^:(%0)(starting_value)

I later changed the _ (infinity literal) to (%0) (reciprocal of zero), getting rid of _. Since I can't avoid ^: itself, the score of ^ is optimal in this approach.

Answer 12

Haskell, score 95 (_) 92 (\)

i = (\_A -> _A)
k = (\_A -> \_AA -> _A)
s = (\_A -> \_AA -> \_AAA -> (_A _AAA)(_AA _AAA))

i = (\(!) -> (!))
k = (\(!) -> \(!!) -> (!))
s = (\(!) -> \(!!) -> \(!!!) -> ((!) (!!!))((!!) (!!!)))

Untyped lambda calculus. Annoying that Haskell can't have uppercase variable names, oh well.

-3 thanks to xnor

Try it online!

Answer 13

PHP + -r, score 65 (A)

Explanation

I saw the other PHP answer and felt like it should be possible to reduce that using create_function and again abusing the fact that PHP allows functions to be called in a case-insensitive way.

Provided below is a compiler that should compile enough of a subset of PHP (maybe any PHP? I haven't tested exhaustively) using only $()+.;=A. This relies on the fact that $A=A;$A++;print($A); yields B and that $A=A;$A++;$A++;$A.=A;$A++;$A++;$A++;$A++;$A++;$A++;$A++;print($A); yields CH, any variable that isn't set that is incremented will produce 1 followed by the rest of the natural numbers, and that a function can be called using this string representation of its name (e.g. $A=CHR;$B=$A(95); stores _ in $B).

This process means that first CHR is stored in $A, then the function name CREATE_FUNCTION is stored in $AA (utilising $A(...)) and the body of the function created by CREATE_FUNCTION is also built using $A.

The TIO link below allows you to provide PHP code to be compiled to this subset (and also executes it via eval to confirm it's working).

Try it online!

Answer 14

Julia, Score 63 (?)

we can actually get away with no letters, by abusing the fact that === is assignable for some reason. however, without a way to index or create arrays, this is not enough. What gets us closer is tuple unpacking. this allows us to create a sort of "stack" with our one variable. (===) = (2,(===)) (===) = (3,(===)) one problem is that we need another variable to unpack the argument into. luckily \ is also assignable, so we can use that as a "register" (\,===) = (===) we can then perform some operation on these values and store the result (===) = (7+\==10,===)

(\,===) = (===) we can conditionaly execute code (and drop some parenthesies) ====(\ ? 1 : 0,===)

we can reuse names via shadowing, but this comes at the cost of recursion \ = (\) -> (\) + 3

fortunately, there's another assignable value ^ = (\) -> (\) < 2 ? (\) : ^((\)-1) + ^((\)-2)

functions can go on the stack ====(^,===)

we also have NAND logic via && and ! (curried)
^ = (^) -> (/) -> !((^)&&(/))

the biggest problem is I/O, as we can't call any Core or Base functions like print, but luckily we can use the -E flag or the REPL to print the result

Answer 15

Python 3, score 102 (f)

def():
 []=-1

Bubbler observes:

With the known bound of m, [...] def is still available, but I doubt it will improve the score because I think making it Turing-complete necessitates the use of return.

With awkward and careful use of implicit globals, we can do without return by rolling our own stack! Using it is considerably more difficult, but it can still be used to implement SKI combinator calculus:

STACK = []
def RETURN(A):
 STACK[:] = STACK + [A]
def POP():
 STACK[-1:] = []

def I(A):
 RETURN(A)
def K(A):
 def INNER_K(B):
  RETURN(A)
 RETURN(INNER_K)
def S(A):
 def INNER_S(B):
  def INNER_INNER_S(C):
   A(C)
   R1 = STACK[-1]
   POP()
   B(C)
   R2 = STACK[-1]
   POP()
   R1(R2)
  RETURN(INNER_INNER_S)
 RETURN(INNER_S)

For example, the infinite loop S(I)(I)(S(I)(I)) can be expressed as

S(I)
*STACK, R = STACK
R(I)
*STACK, R = STACK
R(R)

Attempt This Online!

I suspect this is optimal.

Answer 16

Keg, Score = 58

Characters:

0+-*/():

Simply the standard subset of TC chars

Answer 17

Wolfram Language (Mathematica), score 62 (>)

#$&()-./>

Using these characters we can implement the SKI combinators:

i = #&
k = $&/.$->#&
s = (#//$$//(#//$))&/.$$->#&/.$->#&

Try it online!

Answer 18

C (gcc), score: 110 (n)

<space>!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmn

Because of the trigraphs:

??= #
??( [
??/ \
??) ]
??' ^
??< {
??! |
??> }
??- ~ 

and the main function has to be defined so, no matter what, n has to be used. The ubiquitous semicolon (;) is there. And return is easily avoided through use of assignment (=) since gcc will return the last value assigned of the same type as the function return value. Type int is inferred by default for any variable or function definition.

Answer 19

Dreaderef (-1 flag), score 42 (*)

Dreaderef is a ZISC; the program is a description of the initial tape contents. Dreaderef programs are typically written with an assembly-like syntax that is then run through a preprocessor to produce a list of integers, but quotes (") can also be used to embed arbitrary data in the form of ASCII values.

The only restrictions on the contents of string literals are that:

• They can't contain newlines.
• For our purposes, they can't contain numbers greater than 42.
• They can't contain negative numbers.

The first two aren't a problem, but the third is. Dreaderef's only arithmetic operators are addition and multiplication, so we have no way to obtain negative numbers without including them when initializing. Additionally, the instruction pointer is stored in cell -1, and without accessing it we have no way to do control flow. Thus to achieve Turing-completeness we need to include the * byte (which is replaced with an integer from the command-line arguments at initialization time) and stipulate that the user always pass -1 as an argument.

Answer 20

Unary, score = 48 (0)

Unary only cares about number of 0 in the file.

Inspired by the Lenguage answer

Answer 21

Java, score: 117 (u)

0123456789ABCDEF\u

In Java, there are a few ways to create a full program:

// Regular class with main method (Java 1+):
class M{public static void main(String[]a){/*CODE GOES HERE*/}}

// Interface with main method, where we can remove public (Java 8+):
interface M{static void main(String[]a){/*CODE GOES HERE*/}}

// Exploiting a bug with enum (Java 5 or 6):
enum M{A;{/*CODE GOES HERE*/}}

// Creating a Java AWT GUI application with Applet:
class M extends java.applet.Applet{public void paint(java.awt.Graphics x){/*CODE GOES HERE*/}}

// Creating a JavaFX GUI application with Application:
class M extends javafx.application.Application{public void start(Stage stage){/*CODE GOES HERE*/}}

// Any of the above, but with \uHEXA escaped characters - i.e. here is the interface (excluding the comment within the main-method):
\u0069\u006E\u0074\u0065\u0072\u0066\u0061\u0063\u0065\u0020\u004D\u007B\u0073\u0074\u0061\u0074\u0069\u0063\u0020\u0076\u006F\u0069\u0064\u0020\u006D\u0061\u0069\u006E\u0028\u0053\u0074\u0072\u0069\u006E\u0067\u005B\u005D\u0061\u0029\u007B\u007D\u007D

Since all of them contain } (125), except for the last one with unicode escapes where u (117) is the maximum, that is our best score available in Java.

Try it online:

Here a few example programs using these eighteen bytes:

Try it online: 2+2.
Try it online: Check if the program argument is a prime number.
Try it online: Print "Hello, World!".

Answer 22

Batch, score = 84 (T)

Batch is mostly case insensitive, so we don't need any lowercase letters. We need T in SET in order to be able to do any arithmetic. It also conveniently gives us GOTO, which makes arbitrary looping easier. What we don't get:

• U - PAUSE (can use SET/P to a similar effect); PUSHD (can use CD and %CD% to a similar effect)
• X - EXIT (can still GOTO :EOF but that doesn't set the error level)
• Y - TYPE (can still use MORE for small files)
• ^ - Quote single character (can still wrap most special characters in double quotes)
• | - bitwise OR (can be emulated using A+B-(A&B)); logical OR (can be emulated using && and GOTO)
• ~ - bitwise NOT (can be emulated using -1-X); string slicing (not needed for arithmetic); parameter expansion (e.g. extracting the extension or size of a file), which needs lowercase letters anyway.
• Any executables whose names include the letters U..Z.

Answer 23

MMIX, score 160 (STB)

Without some means of memory manipulation, it can't be Turing complete. The lowest-numbered instruction that allows touching memory is STBU, at #A0. (Well, that's not entirely true, there's also CSWAP at #94, but that's useless without being able to touch rP, which requires PUT at #F6.)

There's plenty of other stuff below, like branches from #40 to #5F, plenty of arithmetic, floating-point arithmetic, shifts, conditional sets (and zero-or-set according to condition), and even (just barely) computed jumps!

The only things that aren't accessible are stores of anything longer than a byte (or of unsigned bytes), bitwise operations, MMIX's weird ops (?DIF, MUX, SADD, M[X]OR), immediate wyde operations, special register handling, unconditional 24-bit relative jumps, subroutine linkage, resumption from traps, user trips, saving/loading the register stack, and syncing memory. Even OS traps are available (though they are probably useless, since the traditional positioning for their arguments and results is $255).

Answer 24

Binary Lambda Calculus, Score: 244.

It is known that S and K are enough for lambda calculus (or combinatory logic) to be Turing-complete.

S and K are represented as following bits, respectively:

00000001 01111010 0111010
0000110

They have 23 and 7 bits respectively.

In worst case where you must use maximum octet value, an octet sequence 11110100 (which is 244) appears to your program.

Answer 25

perl -MAcme::Bleach, score = 32

Acme::Bleach takes a program encoded using white space, and runs it after decoding.

Answer 26

Pxem, W: 87.

Characters are: !-.01ACDOVW (but ! can be any others, and O can be anything that works as pop one and discard it).

Here's how to emulate cyclic tag system program (101,001,10) with input 1, for example, in Pxem (??.z ... .a is pseudo-comment; can be erased):

??.z
# input is 1
# then loop begin
.a!1.W??.z

  # exit if empty
  .a.C.C.-.W.D.A??.z
  # append 101 if top is NOT 0
  .a.C0.-.W.V101.VWW.-.A??.z
  # erase top (by printing it)
  .a.O??.z

  # exit if empty
  .a.C.C.-.W.D.A??.z
  # append 001 if top is NOT 0
  .a.C0.-.W.V100.VWW.-.A??.z
  # erase top (by printing it)
  .a.O??.z

  # exit if empty
  .a.C.C.-.W.D.A??.z
  # append 10 if top is NOT 0
  .a.C0.-.W.V10.VWW.-.A??.z
  # erase top (by printing it)
  .a.O??.z

# end of loop  
.a!.A

Try it online!

Answer 27

AAAAAAAAAAAAAA!!!!, Score: 65 (A).

Characters are ! ,A.

Proven as in this.