Abstract Rewriting Challenge (Cops)

Question

This is a somewhat proof-golf-like cops-and-robbers challenge. This is the cops' thread; the robbers' thread is here.

Cops

Your task is to define an abstract rewriting system in which the reachability of one word from another is difficult to determine. You will prepare the following things:

1. A set of symbols, called the alphabet. (You may use any Unicode characters for these, but please don't use whitespace, or symbols that are hard to distinguish from each other.)

2. A source string composed of symbols from your alphabet.

3. A target string composed of symbols from your alphabet.

4. A set of rewrite rules using characters from your alphabet. (See below for the definition of a rewrite rule.)

5. A proof showing whether your source string can be converted into your target string by successive application of your rewrite rules. This proof might consist of an actual sequence of rewrite steps, or a mathematical proof that such a sequence must exist, or a mathematical proof that such a sequence does not exist.

You will post the first four of these, keeping the proof secret; the robbers will try to crack your answer by providing their own proof that your target string can or can not be reached from your source string. If your submission is not cracked within two weeks, you may mark it as safe and edit in your proof.

Submissions will be scored according to the number of characters in their rewrite rules and their source and target strings, as detailed below. The winner will be the uncracked submission with the lowest score.

What is a rewrite rule?

A rewrite rule is simply a pair of strings in your alphabet. (Either of these strings may be empty.) An application of a rewrite rule consists of finding a substring that is equal to the first string in the pair, and replacing it with the second.

An example should make this clear:

Suppose alphabet is A, B and C; the source string is "A"; the target string is "C" and the rewrite rules are

A:B
B:BB
B:A
AA:C

then the target string is reachable in the following way:

A
B   (using rule 1)
BB  (using rule 2)
AB  (using rule 3)
AA  (using rule 3)
C   (using rule 4)

Scoring

Your score will be

• the length of your source string,
• plus the length of your target string,
• plus the length of all the strings included in your rewrite rules,
• plus one extra point for each rewrite rule.

If you write your rewrite rules with a colon separator as above, this is just the total length of all the rewrite rules (including the separator), plus the lengths of the source and target strings. A lower score is better. The number of distinct characters in your alphabet will be used to break ties, with fewer being better.

Bounty

I'd like to see answers that really go for low scores. I will award 200 rep to the first answer that scores less than 100 points in this challenge and doesn't get cracked.

Answer 1

326 points - Cracked by jimmy23013

The level is Picokosmos #13 by Aymeric du Peloux (with a trivial modification). I tried to find a tasteful level that could be implemented with "boxes" and "walls" being the same character. For this level it was possible by making the central choke point two columns wide rather than one.

The rules/initial/target strings could be golfed a bit more, but this is just for fun.

Initial string:

___##___####_____##_#_#_##_#_!####______##_#####__####_#_######__###__

Target string:

___##___####_____##_#_#_##_#_#####____!__#_#####__####_#_######__###__

Rules:

_wW:!
_<:<_
Vv_:!
V_:_V
R:>>>>>>>>>>>>>
V#:#V
#w<:w#
>v_:_v
_wX:#
_!:!_
!:wLW_
L:<<<<<<<<<<<<<
#W:W#
!#_:_!#
_w<:w_
#<:<#
!:_VRv
>v#:#v
Uv_:#
_W:W_
_X:X_
>#:#>
#X:X#
U_:_U
Vv#:!URv
#wW:wLX!
>_:_>
!_:_!
_#!:#!_
U#:#U

Answer 2

171 points, cracked by HyperNeutrino

Source: YAAAT

Target: VW626206555675126212043640270477001760465526277571600601

Rules:

T:AAAAAT
T:BBU
U:BU
U:ZW
AB:BCA
CB:BC
AZ:Z
CZ:ZC
YB:Y
YZ:V
V:VD
DCC:CD
DCW:W+
DW:W_
___:0
__+:1
_+_:2
_++:3
+__:4
+_+:5
++_:6
+++:7

Just something obvious to do. The actual sequence of rewrite steps probably won't fit in an SE answer.

Answer 3

33 points, cracked by user71546

A simple one to start off.

Source: xnor
Target: xor
Rewrite rules:

x:xn
no:oon
nr:r
ooooooooooo:

The last rule takes 11 o's to the empty string.

Answer 4

139 points (safe-ish)

I intended this answer to be cracked, and user202729 basically solved it in the comments, but nobody posted an answer in the robbers' thread, so I'm marking it "safe-ish" and including my proof below.

(These things are evidently much easier to make than they are to crack. Nobody has tried to go for a really low score yet though, and there might be more fun to be had at that end of things, if this challenge ever takes off.)

---

Here's a self answer. It's potentially very hard, but should be easy if you work out where it came from.

alphabet: ABCDEⒶⒷⒸⒹⒺⒻ⬛⚪️️←→

source: ←A→

target: ←→

Rules: (whitespace is not significant)

← : ←⬛
→ : ⬛→
A⬛ : ⚪B
A⚪ : ⚪Ⓑ
⬛Ⓐ : E⚪
⚪Ⓐ : Ⓔ⚪
B⬛ : ⚪C
B⚪ : ⚪Ⓒ
Ⓑ⬛ : 
Ⓑ⚪ : ⚪Ⓕ
⬛C : D⚪
⚪C : Ⓓ⚪
Ⓒ⬛ : ⬛B
Ⓒ⚪ : ⬛Ⓑ
D⬛ : ⚪E
D⚪ : ⚪Ⓔ
⬛Ⓓ : C⬛
⚪Ⓓ : Ⓒ⬛
⬛E : A⚪
⚪E : Ⓐ⚪
Ⓔ⬛ : ⬛D
Ⓔ⚪ : ⬛Ⓓ
Ⓕ⬛ : ⚪C
Ⓕ⚪ : ⚪Ⓒ
⬛ : 
⚪ : 
⬛ : 
⚪ : 

---

Here is an ASCII version, in case that unicode doesn't display well for everyone.

---

Proof

This is equivalent to the current best contender for a six state busy beaver. A busy beaver is a Turing machine that halts after a really long time. Because of this, the source string ←A→ can indeed be transformed into the target string ←→, but only after more than 7*10^36534 steps, which would take vastly longer than the age of the universe for any physical implementation.

The Turing machine's tape is represented by the symbols ⬛ (0) and ⚪ (1). The rules

← : ←⬛
→ : ⬛→

mean that the ends of the tape can always be extended with more zeros. If the head of the Turing machine ever gets near one end of the tape we can just apply one of these rules, which allows us to pretend that the tape is infinite, and starts out filled with all zeros. (The symbols → and ← are never created or destroyed, so they're always at the ends of the tape.)

The Turing machine's head is represented with the symbols ABCDEⒶⒷⒸⒹⒺⒻ and . A means the head is in state A and the symbol under the head is a ⬛ (0), whereas Ⓐ means it's in state A and the symbol under it is a ⚪ (1). This is continued for the other states, with the circled letter representing a 1 underneath the head and the uncircled version representing a 0. (There is no symbol F because it happens that the head never ends up in state F with a 1 underneath it.)

The state is the halting state. It has the special rules

⬛ : 
⚪ : 
⬛ : 
⚪ : 

If the halting state is ever reached we can repeatedly apply these rules to "suck in" all of the tape (including any extra zeros that arose from extending the tape more than necessary), leaving us in the state ←→. Therefore the reachability problem boils down to whether the state will ever be reached.

The remaining rules are the transition rules for the Turing machine. For example, the rules

A⬛ : ⚪B
A⚪ : ⚪Ⓑ

can be read as "if the machine is in state A and there is a zero under the head, then write a 1, change to state B and move right." Moving right takes two rules, because the tape cell to the right might contain a ⬛, in which case the machine should go into state B, or the cell might contain a ⚪, in which case it should go into state Ⓑ, since there is a ⚪ underneath it.

Similarly,

⬛Ⓓ : C⬛
⚪Ⓓ : Ⓒ⬛

means "if the machine is in state D and there is a 1 under the head, then write a 0, change to state C and move left."

The Turing machine used was discovered by Pavel Kropitz in 2010. Although it's often mentioned in the context of busy beavers, its actual transition table is a little tricky to track down, but it can be found for example here. It can be written as

    0   1

A   1RB 1LE
B   1RC 1RF
C   1LD 0RB
D   1RE 0LC
E   1LA 0RD
F   1RH 1RC

which can be read as "if the machine is in state A and there is a zero under the head, then write a 1, change to state B and move right," and so on. It should be straightforward, if laborious, to check that each entry of this table corresponds to a pair of rules as described above.

The only exception is the rule 1RH that occurs when the machine is in state F over a 0, because it seemed fairly pointless to make the machine write a 1 and move to the right when it could just halt immediately as soon as it ever enters state F over a 0. So I changed the rule that would have been

Ⓑ⬛ : ⚪F

into

Ⓑ⬛ : 

This is why there is no symbol F in the alphabet. (There are some other 'golfs' I could have made, but I didn't want to obscure it too much.)

That's basically it. The target string is reachable from the source string, but only after a ridiculous number of steps.

One more fun fact: if I had used

←A⚪⚪→

as the starting point instead, then it would take not 7*10^36534 steps to halt, but 10^10^10^10^18705352 steps, which is a very big number indeed.

Answer 5

48 points, cracked by bb94

Alphabet: abc
Source: cbaabaabc
Target: cbacbcabc
Rewrite rules:

ab:ba
bc:cb
ca:ac
ab:cc
bc:aa
ca:bb

Answer 6

287 points, safe

Source: YAAT

Target:

VW644507203420630255035757474755142053542246325217734264734527745236024300376212053464720055350477167345032015327021403167165534313137253235506613164473217702550435776242713

Rules:

T:AAAAAT
T:BBU
U:BU
U:ZW
AB:BCA
CB:BC
AZ:Z
CZ:ZC
YB:Y
YZ:V
V:VD
DCC:CD
DCW:W+
DW:W_
___:0
__+:1
_+_:2
_++:3
+__:4
+_+:5
++_:6
+++:7

I found that openssl is much easier to use than gpg for this purpose.

---

See HyperNeutrino's crack to the weaker version. In this case, The number of Cs is:

22030661124527021657244569669713986649562044939414344827127551659400215941242670121250289039666163853124410625741840610262419007778597078437731811349579211

And the prime factors are:

220040395270643587721928041668579651570457474080109642875632513424514300377757
100120985046540745657156603717368093083538096517411033964934953688222272684423

The first number mod 5 = 2, so it is possible to get the final string.

Answer 7

402 points

Alphabet: abcdefghijklmnopqrstu
Source: abcdoi
Target: ioabcdnnnnnnnnnnnnnnnnnn
Rewrite rules:

ab:ba
ba:ab
ac:ca
ca:ac
ad:da
da:ad
bc:cb
cb:bc
bd:db
db:bd
cd:dc
dc:cd
na:an
nb:bn
nc:cn
nd:dn
nm:mn
nj:jn
aoi:eag
boi:ebg
coi:ecg
doi:edg
ae:ha
be:hb
ce:hc
de:hd
ioa:kam
iob:kbm
ioc:kcm
iod:kdm
ma:aj
mb:bj
mc:cj
md:dj
dg:rdnnnnnnnnnn
cg:qcnnnnn
bg:pbnn
ag:fan
cr:fc
br:fb
ar:fa
bq:fb
aq:fa
ap:fa
er:io
eq:io
ep:io
ef:io
hf:io
kd:dunnnnnnnnnn
kc:ctnnnnn
kb:bsnn
ka:aln
uc:cl
ub:bl
ua:al
tb:bl
ta:al
sa:al
um:oi
tm:oi
sm:oi
lm:oi
lj:oi
:n

The last rule allows you to create as many ns as you need.

Ugly as it seems, it's actually quite nice, one way or another...

Answer 8

1337 Points

Definitely not competitive, and took way too long to create (I hope I made no mistake).

Hint:

try to understand the source string before looking at the rules

Alphabet: ABEILRSTabcdefijlr

Source: SIbbbbbbbdbffacebbfadbdbeecddfaeebddcefaddbdbeeecddaaaaadfaeeebdddcefbbfadbdbdbeeecdddfaeeebdddcefaddbdbeeecddaaaadfaeeebdddcefbfadbdbdbeeecdddfaeeebdddcbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaceefacdffacebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaaceefacdffacebdcecefacE

Target: SE

Rewrite rules:

Ab:bA
bA:Ab
Aa:aA
aA:Aa
Ad:dA
dA:Ad
Ae:eA
eA:Ae
Af:fA
fA:Af
Ac:cA
cA:Ac
IA:AI
AI:IA
Bb:bB
bB:Bb
Ba:aB
aB:Ba
Bd:dB
eB:Be
Be:eB
dB:Bd
Bf:fB
fB:Bf
Bc:cB
cB:Bc
E:BE
S:SB
Ib:AbI
AIa:aI
IdB:dBI
BIe:eIB
AIf:AfI
BIfB:BfiLB
Lb:bL
La:aL
Le:eL
Ld:dL
Lf:fL
Lc:cL
ib:bi
ia:ai
ie:ei
id:di
if:fil
lb:bl
la:al
le:el
ld:dl
lf:fl
lc:cl
icl:ci
icL:cI
Ic:jRc
bj:jb
aj:ja
dj:jd
ej:je
br:rb
ar:ra
dr:rd
er:re
fr:rf
cr:rc
bR:Rb
aR:Ra
dR:Rd
eR:Re
fR:Rf
cR:Rc
cj:jrc
fjr:jf
fjR:If
I:T
TB:T
BT:T
bT:T
aT:T
dT:T
eT:T
fT:T
cT:T
T:

Answer 9

Note that I made some mistakes initially, so the score was changed. Nevertheless, the idea is the same. I hope there are no more mistakes now.

---

154 Points

Alphabet: P.!xABC[{mD<
Source: [x!P.P...P..P.P....P..P.P.....P.P....P......P.P..P...P.P...Pm (61 characters)
Target: {CCCCC< (there are 5 Cs, so 7 characters)

Rules:

P.  →  .PP
!.  →  !
x   →  AxB
x   →  
AB  →  BAC
CB  →  BC
CA  →  AC
[B  →  [
[A  →  {
{A  →  {
!   →  !m
mP  →  PmD
Dm  →  mD
DP  →  PD
!P  →  ?
?P  →  ?
!m  →  <
<m  →  <
C<D →  <

There are 19 rules, total number of characters = 67.

Answer 10

106 points - cracked by HyperNeutrino

Alphabet: ABCDEFGHIJ

Source: FIABCJAGJDEHHID

Target: F

Rewrite Rules:

B:DCIE
A:IFBA
D:EEFJ
C:GFIC
E:HBJG
F:FEBG
G:HFCJ
H:DIGB
I:FCAH
J:BHEA

EJGI:FF
FFF:J
FF:E
EE:D
DDEA:FI
I:F

---

Okay, HyperNeutrino has proved that this is unsolvable. However, there is another solution to this.

---

Take:

I E C D H G J A F B
1 2 3 4 5 6 7 8 9 10

The value of the source is even. The value of the target is odd. If we take each side, total the value, and take the value to mod 2, the values stay the same. Therefore, this cannot be achieved.