[Question]
  [
This is a somewhat [proof-golf](/questions/tagged/proof-golf "show questions tagged 'proof-golf'")-like [cops-and-robbers](/questions/tagged/cops-and-robbers "show questions tagged 'cops-and-robbers'") challenge. This is the cops' thread; [the robbers' thread is here.](https://codegolf.stackexchange.com/questions/157095/abstract-rewriting-challenge-robbers)
# Cops
Your task is to define an [abstract rewriting system](https://en.wikipedia.org/wiki/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]
## 326 points - [Cracked](https://codegolf.stackexchange.com/a/158452/21034) 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]
# 171 points, [cracked by HyperNeutrino](https://codegolf.stackexchange.com/a/157170/68942)
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]
## 33 points, [cracked by user71546](https://codegolf.stackexchange.com/a/157104/20260)
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]
# 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](https://gist.github.com/nathanielvirgo/7da0ea7b6f8405f169ec835d5fb29453), 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](https://en.wikipedia.org/wiki/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](http://www.logique.jussieu.fr/~michel/bbc.html). 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]
# 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](https://codegolf.stackexchange.com/a/157170/25180) to the weaker version. In this case, The number of `C`s 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]
# 48 points, [cracked](https://codegolf.stackexchange.com/a/157114/60483) by [bb94](https://codegolf.stackexchange.com/users/14109/bb94)
Alphabet: `abc`  
Source: `cbaabaabc`  
Target: `cbacbcabc`  
```
ab:ba
bc:cb
ca:ac
ab:cc
bc:aa
ca:bb
```
[Answer]
# 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 `n`s as you need.
Ugly as it seems, it's actually quite nice, one way or another...
[Answer]
# 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]
> 
> 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 `C`s, 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]
# 106 points - cracked by [HyperNeutrino](https://codegolf.stackexchange.com/a/157534/68546)
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.
]