Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Challenges

Abstract Rewriting Systems (Cops)

+0
−0

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

Source: MU Puzzle from Wikipedia

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:

Proof of impossibility

Only rules 2 and 3 directly affect the Is. However, we have that there is no way for us to double the amount of Is 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.

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.

History
Why does this post require attention from curators or moderators?
You might want to add some details to your flag.
Why should this post be closed?

0 comment threads

0 answers

Sign up to answer this question »