Post History

Abstract Rewriting Systems (Cops)

<sup>This is somewhat of a [proof-golf]-like [cops-and-robbers]. This is the cops' thread; the robbers' thread is [here]()</sup>

Sections:
>* Cops
>* Scoring
>* What is a rewrite rule?
>    * An example
>    * An example of impossibility
>* Determining the winner

## Cops

Your task is to create an [abstract rewriting system](https://en.wikipedia.org/wiki/Abstract_rewriting_system) in which the reachability of one word from another should preferably be difficult to determine.

The following things will be prepared beforehand:
>1. A set of symbols, referred to here as the "alphabet". You can use any Unicode symbols for these, with 2 exceptions:
>    * No whitespace.
>    * No 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 the section "What is a rewrite rule?" to see what we are defining a rewrite rule to be.
>5. A proof showing whether or not your source string can be converted into your target string by a successive application of the rewrite rules.
>    * This proof might be an actual sequence of rewrites, or it could be a mathematical proof that such a sequence exists/does not exist.

However, only the first 4 of these things will be posted, keeping the proof a secret. The robbers will try to crack your answer by providing their own proof that the target string can/cannot be reached by the source.

If your submission is not cracked after **3 weeks**, you can mark your answer as safe and edit in your proof.

## Scoring

Submissions will be scored according to the total number of characters in the target and source strings, along with the number of characters in the rewrite rules (including separators).

The winner will be the user with the uncracked submission with the lowest score, although more specifics will be discussed in the section "Determining the winner".

Starting March 1st, 2025 12AM UTC, any answers to the question will be considered to be "non-competing" (See "Determining the winner"), although answers can still be posted after this date.

## What is a rewrite rule?

What this is is simply a pair of strings in your alphabet. Either of - but not both of - these strings can be empty.

### An example

Consider the following alphabet, source and target strings, and rewrite rules: (Score 40)
```
Alphabet:
ABCD

Source string:
A

Target string:
CBBBB

Rewrite rules:
A:CD
AC:BA
B:BBC
BCC:CB
BD:BC
C:AC
CD:DC
```
Then we can reach the target string as follows:
```
A
CD        (Rule 1)
ACD       (Rule 6)
BAD       (Rule 2)
BBCAD     (Rule 3)
BBCCDD    (Rule 1)
BBCDCD    (Rule 7)
BBDCCD    (Rule 7)
BBCCCD    (Rule 5)
BCBCD     (Rule 4)
BCBDC     (Rule 7)
BCBCC     (Rule 5)
BCCB      (Rule 4)
CBB       (Rule 4)
ACBB      (Rule 6)
BABB      (Rule 2)
BCDBB     (Rule 1)
BDCBB     (Rule 7)
BCCBB     (Rule 5)
CBBB      (Rule 4)
ACBBB     (Rule 6)
BABBB     (Rule 2)
BCDBBB    (Rule 1)
BDCBBB    (Rule 7)
BCCBBB    (Rule 5)
CBBBB     (Rule 4)
```
### An example of impossibility

<sup>Source: [MU Puzzle](https://en.wikipedia.org/wiki/MU_puzzle) from Wikipedia</sup>

>Suppose there are symbols `M`, `I`, and `U` which can be combined to produce strings of symbols. The MU puzzle asks one to start with the "axiomatic" string `MI` and transform it into the string `MU` using in each step one of the following transformation rules:
>```
>1. xI → xIU       Add a U to the end of any string ending in I
>2. Mx → Mxx       Double the string after the M
>3. xIIIy → xUy    Replace any III with a U
>4. xUUy → xy      Remove any UU
>```

The reason this is impossible is simple:
<details><summary>Proof of impossibility</summary>

Only rules 2 and 3 directly affect the `I`s. However, we have that there is no way for us to double the amount of `I`s starting from 1 `I` such that the number is divisible by 3. Also, subtracting 3 from the number of `I`, no matter what, does not make it divisible by 3. Therefore this puzzle is impossible mathematically.

</details>

## Determining the winner

The winning answer will be determined by the following criteria:

>1. The answer must have been posted before March 1st, 2025 12AM UTC to qualify as a competing answer.
>2. The answer must be uncracked 3 weeks after posting. (If it was posted Feb. 28, 2025 - the latest date possible to post a competing answer - then it must remain uncracked until March 21, 2025 at the minimum.)
>    * The answer must be marked as "safe" at some point after the 3 weeks are up.
>3. It must have the lowest score out of all the other answers.
>    * If there is a tie, then the number of distinct characters in both alphabets will be considered, with fewer being better.
>    * If there is still a tie, then the older answer will be the winner.

A Top 10 leaderboard will be edited in on March 22, 2025 at the bottom of the post to showcase the Top 10 lowest (uncracked) scores.