The main idea is to build an arbitrary Python expression using
+ (addition or string concat) and
' (chr) and
⍎ (eval) it. So the proof is in two parts: constructing an arbitrary string, and making sure that Python's eval (as opposed to an arbitrary program) is Turing-complete.
eval is Turing-complete
exec, we can't use many syntactic keywords like
while and even
def. But we have
lambda expressions, and it turns out that we can implement untyped lambda calculus. As a minimal example, the following expression is an infinite loop:
(lambda a:a(a))(lambda a:a(a))
To make it more explicit, here are SKI combinators:
S = lambda l:lambda a:lambda m:l(m)(a(m))
K = lambda l:lambda a:l
I = lambda l:l
> 1+'\n is enough to construct an arbitrary string
Now to actual Whispers code. The lines starting with single
> are constant lines, and those with double
>> reference other expressions using line numbers. We will only use 1, 11, 111 for constant lines, and construct the required charcodes using addition. The following sets up three numbers for the string
"123" (charcodes 49, 50, 51):
>> 2+2 // 22
>> 3+3 // 44
>> 1+1 // 2
>> 5+5 // 4
>> 4+6 // 48
>> 7+1 // 49
>> 8+1 // 50
>> 9+1 // 51
Then we apply
' (chr) to each of the charcodes:
>> '8 // "1"
>> '9 // "2"
>> '10 // "3"
Finally, we concat and eval them.
We successfully created the string
"123" and passed it to
eval. Now the only problem is that we used all digits to reference lines. It can be easily circumvented by inserting dummy syntactically valid lines
> 1 so that we can reference meaningful lines with repunits (so the line number
n will be translated to the number containing
n copies of 1):
> 1 // valid line 1
> 1 // from line 2...
> 1 // ...to line 10 are dummy lines
> 11 // valid line 11
> 1 // from line 12...
> 1 // ...to line 110 are dummy lines
>> 11+11 // valid line 111
7 chars is (likely) minimal, at least in v1
I checked the whole source code, and all one-char functions except
⍎ do not have mutable state at all. There are looping constructs like
While, but using it alone requires at least 8 chars
> While1. Therefore, the approach using
⍎ must be minimal (where 7-char solution is already known).
For TC-ness in Python eval, we need at least
lambd :(), which is already 9 chars, and
chr is definitely needed to create them without them in the source code. There is no 1-char solution to create those charcodes, and
+ with string concatenation. Therefore using
1+' as the core chars is the minimal way to build a string that enables TC-ness.
I didn't read all of v2 and v3 source code, but I believe the 7-char solution is likely minimal on those too.