10
\$\begingroup\$

This is the robbers' challenge. The cops' one is here.

In Fewest (distinct) characters for Turing Completeness, the goal is to find the minimum number of characters which make a language Turing Complete...in other words, allow it to do any computation possible with any other language. In this challenge, we'll be doing somewhat of the opposite, and finding the minimum number of characters, without which Turing Completeness is impossible.

Task:

Robbers should include an explanation of how Turing Completeness can be achieved without any characters in the cop, or a proof that this is impossible.

Scoring:

Scoring, as per normal robbers' rules, is that whoever cracks the most cops wins.

Chat room: https://chat.stackexchange.com/rooms/136437/smallest-subset-of-characters-required-for-turing-completeness

\$\endgroup\$

13 Answers 13

11
\$\begingroup\$

Python, cracks Felipe Soares

class   X:__class_getitem__=exec
X["print\50'Hello,\40world!')"]

Lack of spaces is no problem because you can use tabs. Calling an arbitrary function without parentheses is tricky but possible.

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

Python, cracks pxeger

__builtins__.__dict__["\x65x\x65c"]("<stuff>")

Attempt This Online!

Replace the <stuff> with code you want to execute, escaping the banned chars.

\$\endgroup\$
2
  • \$\begingroup\$ You can also just say exec("<stuff>"), where can be any letter that NFKC-normalizes to e other than e itself. \$\endgroup\$
    – benrg
    May 21 at 17:54
  • \$\begingroup\$ @benrg True. Oh well, I think this was pxeger's intended solution. \$\endgroup\$
    – emanresu A
    May 21 at 20:27
8
\$\begingroup\$

tinylisp, cracks des54321's answer

(d A (q (
  (y x)
  (v (c (h x)
       (c
        (c (q q) (c y ()))
        (t x))))
)))
(d K (q (
  (x)
  (c (q K1) (c (c (q q) (c x ())) ()))
)))
(d K1 (q (
  (y x)
  x
)))
(d S (q (
  (x)
  (c (q S1) (c (c (q q) (c x ())) ()))
)))
(d S1 (q (
  (y x)
  (c (q S2) (c (c (q q) (c y ())) (c (c (q q) (c x ())) ())))
)))
(d S2 (q (
  (z y x)
  (A (A z y) (A z x))
)))

Try it online! (The three examples are the identity combinator (S K K), the mockingbird combinator (S (S K K) (S K K)), and an infinite loop, so you'll need to halt the program to see the output from the first two.)

This is an interpreter for SK combinator calculus (which is Turing complete), built in tinylisp-without-i.

Usage, and principles behind this

The basic idea is to do control flow via v, which lets us inspect an atom via using it as the name of a function. As is usual in implementations of combinator calculus, we make use of five families of combinators (S and K themselves, plus partially applied versions of them; K can be given one argument to produce K1, S can be given one or two arguments to produce S1 or S2).

In order to be able to use these for control flow with v, we store our combinators in a form that looks like a tinylisp function call but with one argument missing, and the arguments in reverse order:

  • S is stored as (S);
  • K is stored as (K);
  • S applied to one argument x is stored as (S1 (q x));
  • K applied to one argument x is stored as (K1 (q x));
  • S applied to two arguments x and y is stored as (S2 (q y) (q x)).

Our combinator application operator A works by inserting the argument it's being given as the second element of the function it's given, in the form (q arg) (thus producing a complete tinylisp function call), and then evaluating it with v. (This is the reason that the arguments have to be reversed – we can't insert a value at the end of a list of unknown length when we have no workable control flow, but we can insert an element in any specific position relative to the start via using hardcoded chains of h and t.) A can be used directly to write programs (allowing specification of arbitrarily complex input), and is used indirectly in the implementation of S2 (which is what makes loops possible).

To write a complete program, you write S as (q (S)), K as (q (K)), and application of f to x as (A x f) (I decided to consistently reverse arguments everywhere, which is probably less confusing then reversing them only in some places). For example, the implementation of the identity function, which in Lisp syntax would be (S K K), looks like this when used as input to this interpreter:

(A (q (K)) (A (q (K)) (q (S))))

Explanation

Most of this program is just list manipulation, building up lists from templates. The "inside" of most of these is the fragment (c (q q) (c x ())). (c x ()) inserts (c) x as the first element of an empty list (()), thus producing (x). The fragment as a whole inserts (c) a literal q ((q q)) as the first element of that, thus producing (q x). The same technique is then repeated to produce a list whose elements are of the form (q x) and which starts with an appropriate combinator, and this is the only thing done in the implementations of S, S1 and K.

A is very similar – the only differences are that the resulting list is evaluated as tinylisp code (v) rather than simply being returned, and that the list is constructed as the head of the function ((h x)), followed by the argument formatted as (q y), followed by any arguments that may have been curried into the combinator (this is the tail of x, (t x)).

K1 and S2 contain all the actual logic, and are implementations of the K and S combinators, as per the definition of SK combinator calculus; K returns its first argument x and ignores its second argument Y, whereas S returns (A (A z y) (A z x)) (which can simply be written directly in the function body).

\$\endgroup\$
7
\$\begingroup\$

C (nonportable), cracks Pyautogui's answer

const char main[]="\x48\x8d\x35\xf9\xff\xff\xff\xbf\x01\x00\x00\x00\x89\xf8\x89\xfa\x0f\x05\xeb\xf8";

Try it online!

Very platform- and compiler-specific. This worked on old versions of tcc, but not on the current version. On my computer and on TIO, it works on current gcc with the -zexecstack command-line option, but not without. On platforms with no memory protection (e.g. DOS), this should work on pretty much any compiler (although you would of course need to change the contents of the string literal to fit the platform you were running on).

The basic idea is to run arbitrary machine code by misinterpreting a string literal as a function (the "function" given above prints the letter H – its own first byte – infinitely many times, if run on a Linux x86-64 system). In C, type-checking is done only by the compiler, not the linker, so if you place a string literal in one translation unit (i.e. file) and a function call to it in a different translation unit, neither the compiler nor the linker will notice that one unit declared the symbol in question to be a function but the other declared it to be a character array. (Function pointers and character array pointers are the same width on most platforms, which is all the linker cares about, so it'll happily misinterpret one as the other.)

How to call a function without (? We can't write the function call, but luckily there's an implicit call to main at the start of the program, and as a bonus, the implicit call is in a different file (one provided by the C implementation) than our program is, so neither the compiler nor the linker will produce an error (although several compilers have a warning for this sort of thing nowadays). So as long as our string literal is used to initialise a variable named main, it'll get called automatically.

Further reading: @Dennis discussing how to various get C implementations to run a variable as though it were a function.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ As I'm intentionally avoiding reputation, I don't have the reputation to mark the cop as cracked. Could someone do that for me? \$\endgroup\$
    – ais523
    May 20 at 4:19
  • \$\begingroup\$ Incredible crack! I shall do that. I thought that I had ruled out this solution with the { character, but I forgot about string literals! \$\endgroup\$ May 20 at 4:42
  • 1
    \$\begingroup\$ This doesn't work on newer Linux systems. More modern Linux kernels only apply -zexecstack to the actual stack, instead of having it set the READ_IMPLIES_EXEC process personality. See How to get c code to execute hex machine code?. (The reason it used to not require -zexecstack is that older ld versions linked the .rodata section into the same ELF segment as .text. Newer ld avoids that, to minimize Spectre / ROP gadget surface area by not having any bytes in executable pages that don't need to be.) \$\endgroup\$ May 20 at 13:20
  • 1
    \$\begingroup\$ For modern GCC/ld/kernel, one way that works is to add __attribute__((section(".text"))) to the source before the array. as outputs "Warning: ignoring changed section attributes for .text", probably because GCC used a .section .text directive without the usual attributes that make it executable. Since as ignores it, we end up with this symbol in an executable .text section, with your custom machine code, so that Just Works without -zexecstack. It also works with tcc, with no warning; it seems it supports that attribute. \$\endgroup\$ May 20 at 13:34
7
\$\begingroup\$

R, cracks Dominic van Essen

autoload -> `%aut%`
'%>%' %aut% 'magrittr'
'1+1' %>% str2expression %>% eval

Replace '1+1' with arbitrary expressions, using unicode characters as necessary.

Unfortunately was not able to run on TIO due to needing R version >=3.6 for str2expression. Does work on rdrr.io.

This uses -> which is not banned unlike <- and = to create an infix version of autoload, which is used to give me magrittr pipes, which can then be used to evaluate arbitrary strings.

\$\endgroup\$
3
  • \$\begingroup\$ Well done. Using the -> assignment operator to define infix function was exactly the trick that I had in mind. I still can't think of a way to ban (=<>, so possibly that's an impossible-to-crack 'sort-of-cop'... \$\endgroup\$ May 20 at 14:08
  • \$\begingroup\$ Thanks! Were you thinking of a different infix function? \$\endgroup\$
    – Cong Chen
    May 20 at 14:09
  • 1
    \$\begingroup\$ The exact solution that I had in mind worked on TIO, so I may be able to adjust it and re-post another cop... \$\endgroup\$ May 20 at 14:20
6
\$\begingroup\$

Batch script, cracks Yousername

Conditional control flow is still possible using goto instructions with variables, like this:

set /a cond = 1+1
goto tag%cond%
:tag1
echo foo
goto end
:tag2
echo bar
goto end
:end

Where the set /a instruction allows you to set a variable to the result of an expression, and this variable can then be used as part of a label for a goto instruction.

This allows arbitrary flow control, and therefore should make Batch scripts Turing complete without if statements

\$\endgroup\$
6
\$\begingroup\$

Haskell, cracks Unrelated String's second answer

The basic idea is to define a function a that makes it possible to write a[x][y] instead of (x y). Here's the definition, and an example of using it:

a[x][y]=head[x]y
main=a[putStrLn][a[reverse]["codegolf"]]

Try it online!

This works around the bans on horizontal whitespace and on parentheses; function arguments are now separated by ][ rather than whitespace, and because each argument is surrounded by square brackets, there's no need for any further grouping characters. Haskell uses currying for functions that take multiple arguments, meaning that a can handle these too (f x y becomes a[a[f][x]][y]), and we don't need a special case for them.

It's also possible to define functions using similar syntax, including defining functions by cases (e.g. f[0]=1 and on the next line f[1]=3); these don't need a to call because they have the square brackets built in, but otherwise work the same way (the square brackets still handle the grouping).

This means that most of the core functionality of Haskell is available – we can call most of the built-in functions, and define our own, including conditionals. That's a Turing-complete subset (loops via recursion and conditionals via functions-defined-by-cases are available, in addition to complex data structures), so the ban on whitespace and parentheses doesn't really hurt at all, and { and $ aren't required to make this subset work either.

Explanation

head[x] trivially evaluates to x – it's taking the first element of a 1-element list. The advantage over using x directly is that it ends with a non-identifier character, meaning that we can put a letter directly after it without needing to use whitespace.

a[x][y]= is a pattern match, used to define a function a; it defines the function only in the case where it's given two single-element lists as arguments, and defines x and y to be their arguments. As such, if we call a as a[x][y], then the x and y in the definition of a will be the same as the x and y at the call site. (It would be possible to give further definitions to cover the cases where x and y aren't single-element lists, but this isn't necessary to make the answer work.)

\$\endgroup\$
6
\$\begingroup\$

C# (Visual C# Compiler), cracks Not A Chair's answer

Brainfuck interpreter, updated to crack the third cop (.=;). Input by command line arguments; I couldn't figure out how to do output without ., but IO is not necessary for Turing-completeness. Maybe it's possible to do it by using something from the namespace System.Linq.Expressions.

namespace System {
namespace Collections {
namespace Generic {
	class MyList : Dictionary<int, byte>
	{
		public MyList(string s, string inp)
		{
			if(0 is var pc) {}
			if(0 is var i) {}
			if(0 is var inp_i) {}
		 	if(TryAdd(i, 0) is int) {}
			try { // to exit cleanly at end of program
			while(true)
			{
				if((s[pc] ^ '+') < 1) if(Set(i,(byte)-~this[i]) is int) {}
				if((s[pc] ^ '-') < 1) if(Set(i,(byte)~-this[i]) is int) {}
				if((s[pc] ^ '>') < 1)
				{
					if(i++ < 0) {}
					if(TryAdd(i, 0) is int) {}
				}
				if((s[pc] ^ '<') < 1)
				{
					if(i-- < 0) {}
					if(TryAdd(i, 0) is int) {}
				}
				//if((s[pc] ^ 46) < 1 && Console.Write((char)this[i]) is int) {} // uncomment for output
				if((s[pc] ^ ',') < 1)
				{
					try
					{
						if(Set(i, (byte)inp[inp_i++]) is int) {}
					} catch { }
				}
				if((s[pc] ^ '[') < 1 && this[i] < 1)
				{
					if(1 is var bal) {}
					if(pc++ > 0) {}
					while(bal > 0)
					{
						if((s[pc] ^ '[') < 1 && bal++ < 0) {}
						if((s[pc] ^ ']') < 1 && bal-- < 0) {}
						if(pc++ > 0) {}
					}
					if(pc-- < 0) {}
				}
				if((s[pc] ^ ']') < 1 && this[i] > 0)
				{
					if(1 is var bal) {}
					if(pc-- > 0) {}
					while(bal > 0)
					{
						if((s[pc] ^ ']') < 1 && bal++ < 0) {}
						if((s[pc] ^ '[') < 1 && bal-- < 0) {}
						if(pc-- > 0) {}
					}
				}
				if(pc++ < 0) {}
			}
			} catch {}
		}
		void Set(int i, byte s)
		{
			try { if(Remove(i) is int){} } catch {}
			if(Add(i, s) is int) {}
		}
	}

	class Program {
		static void Main(string[] args) {
			try {
				if(new MyList(args[0], args[1]) is var x) {}
			} catch {
				if(new MyList(args[0], "") is var x) {}
			}

		}
	}
}}}

Try it online!

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

Python, cracks pxeger's other answer

__import__('os').__dict__.pop('syst\x65m')('ls -la')

Attempt This Online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Ooh, escaping to another language. I certainly didn't think of that! \$\endgroup\$
    – pxeger
    May 20 at 6:24
  • 2
    \$\begingroup\$ You could use __builtins__.__dict__['exec'] instead of os.__dict__['system'], the pop is the interesting part. \$\endgroup\$ May 20 at 6:27
  • 1
    \$\begingroup\$ But the possibility of using system or popen or etc. makes it much harder to block \$\endgroup\$
    – pxeger
    May 20 at 6:32
  • \$\begingroup\$ Ah, this is way simpler than my solution, although I'm proud of it... import pdb; p = pdb.Pdb(skip='*'); p.run('anything'); \$\endgroup\$ Jun 5 at 17:53
4
\$\begingroup\$

Cracks Unrelated String's Haskell answer

main=fix{--}id

Attempt This Online!

You can do function application by inserting an empty block comment between the function and its argument. Here I made a loop just to demonstrate.

\$\endgroup\$
1
  • \$\begingroup\$ This is not how I thought a crack might go--maybe it's a bit better! \$\endgroup\$ May 20 at 11:17
4
\$\begingroup\$

Headass, cracks E by thejonymyster

This is Turing complete because it can simulate a Minsky machine with two registers.

r1 and r2 will be used as the two registers of the Minsky machine. r3 will store the state.

The program has the following structure: initialisation { state handlers ;}:;

Each non-halting state, with one exception, has a positive state number and a state handler of the form >>+state number) core : (the superscript denotes repetition). >> sets r0 to 0, then the +s increase it to the state number, and the ) checks if that equals the current state. If it does, the core executes, and then the : jumps to after the first ;. Otherwise, the ) jumps to after the :, continuing execution into the next state handler.

The exception is the last non-halting state, which omits the :, so that a mismatch instead jumps to the : outside the loop, ending the execution.

The core of a state handler has these four possibilities:

  • Increment r1 and change to state s: D+^>>+s(
  • Increment r2 and change to state s: >>]+[+s(
  • If r1 is zero, change to state s; otherwise decrement it and change to state t: >>+s(D^+s>)D-^>>+t(
  • If r2 is zero, change to state s; otherwise decrement it and change to state t: >>+s(<]>)>>]-[+t(

For both of the decrement cases, the state handler for state s must come after the decrementing one; otherwise, the program will incorrectly stop. This can be ensured by rearranging the state handlers or, if necessary, inserting extra states in between.

Finally, the initialisation is D>>+a^>>+b[+s( to set r1 to a, r2 to b, and the state (r3) to s.

\$\endgroup\$
1
  • \$\begingroup\$ Lol i was literally working on this. I'll link this in the cop after work, GG \$\endgroup\$ May 24 at 13:35
4
\$\begingroup\$

LOLCODE, cracks Pyautogui's answer

So it turns out that in LOLCODE, you can use a variable as a loop variable even if it hasn't been declared, and then assign to it and otherwise treat it as a normal variable while you're still inside the loop:

HAI 1.2
IM IN YR ROUTER UPPIN YR HAX WILE DIFFRINT HAX AN 8388607
HAX R DIFF OF HAX AN PRODUKT OF HAX AN -1
IM OUTTA YR ROUTER
KTHXBYE

Try it online! (Adds a VISIBLE HAX to show what's happening in the program; this can't be included in the crack itself due to VISIBLE containing an S.)

This means that it's fairly easy to work around the inability to use S for variable declaration, at least for integer variables; simply create a lot of nested loops that declare all the variables you need, then run your entire program on the first iteration of those loops. (You can break out of the loops via setting all the variables to known values other than 0, and using those known values as the sentinels which terminate the loops.)

Other uses of S, and how to work around them:

  • SUM: instead of adding, multiply the right-hand side by -1 and subtract (as shown in the code sample above)
  • SMALLR: multiply by sides by -1, use BIGGR then multiply the result by -1
  • QUOSHUNT: represent every number as a pair of numbers, a numerator and a denominator, effectively treating it as a rational; to multiply, multiply the numerators and denominators; to divide, multiply one number's numberator by the other's denominator and vice versa; addition, subtraction and comparison can be done by multiplying each number's numerator and denominator by the other's denominator first; if the rounding behaviour of integer division is required, you can subtract the numerator modulo the denominator from the denominator; if a crash on division by zero is required, you can manually check for the denominator being zero and exit the program manually via setting all the variables to values that will cause it to drop out of loops
  • BOTH SAEM: replace with NOT DIFFRINT
  • VISIBLE: there's no replacement for this, but I/O is not needed for Turing completeness
  • IF U SAY SO: there's no direct replacement for this, so you have to write the program without using functions
  • SMOOSH: there's no direct replacement for this, so you have to write the program without using strings other than string literals

The S in SMOOSH almost leads to a difficult philosophical problem: is LOLCODE Turing-complete without functions or calculated strings? The issue is that the stock LOLCODE interpreter has limits on the size of integers, and on the length of strings, but only the former is mentioned in the specification. If you consider both limits to be implementation details that don't block Turing-completeness, then the language is Turing-complete – you can use bignum integers to implement, e.g., Blindfolded Arithmetic. If you consider integers to be limited size but strings to be unlimited size, then the language is not Turing-complete without S due to the inability to store arbitrary amounts of data – there's no way but SMOOSH to create new strings. Fortunately, the problem was probably resolved in advance by the cop question itself (which specifies that "actual 'Turing Completeness'" is not required when running into "things like maximum sizes for pointers" – the issue of maximum integer sizes seems to be comparable, although we might need a clarification from the OP to make sure), so I hope that this is a valid crack.

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

Nim, cracks Pyautogui's answer

proc main =
  asm ".intel_syntax noprefix\nlea rdi, [rip+xyz]\ncall system\nxor edi, edi\ncall exit\nxyz\x3a\n.asciz \"ls -la /\"\n.att_syntax prefix"

main()

I don't know Nim, but you didn't block assembly statements. This crack may need to be modified depending on the system and compiler parameters (this assumes the C backend and a Unix-like x86-64 system). Of course, it is possible to perform arbitrary computation in assembly without using the shell.

Attempt This Online!

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