Abstract Rewriting Systems (Cops)

^{This is somewhat of a [proof-golf]-like [cops-and-robbers]. This is the cops' thread; the robbers' thread is here}

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 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

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:

I:IU
I:IIII
III:U
UU:

The reason this is impossible is simple:

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.

posted 27 days ago

CC BY-SA 4.0

5d ago

CrSb0001‭

11 reputation 4 1 2 5