Abstract Rewriting Challenge (Robbers)

Question

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

Robbers

The cops will post abstract rewriting systems. Your task is to crack their submissions by proving that the target string either can or can not be reached from the source string by applying their rewrite rules. (You can do this either by posting a sequence of rewrite rules that starts with the source string and ends with the target, or by proving mathematically that this does, or does not, exist.)

See the cops' thread for details and definitions.

Answer 1

jimmy23013

Let's work backwards for this one. We first turn the digits into their binary representations. We go from VW626206555675126212043640270477001760465526277571600601 to VW++__+_++__+____++_+_++_++_+++_++++_+__+_+_++__+___+_+____+___++++_+______+_+++___+__++++++________++++++____+__++_+_++_+_+_++__+_+++++++_++++__+++_______++______+. Next, we keep applying the inverse of DCW:W+ and DW:W_ until we clear all symbols. Our result is now VDCDCDDDCDDCDCDDDCDDDDDCDCDDCDDCDCDDCDCDDCDCDCDDCDCDCDCDDCDDDCDDCDDCDCDDDCDDDDCDDCDDDDDCDDDDCDCDCDCDDCDDDDDDDCDDCDCDCDDDDCDDDCDCDCDCDCDCDDDDDDDDDCDCDCDCDCDCDDDDDCDDDCDCDDCDDCDCDDCDDCDDCDCDDDCDDCDCDCDCDCDCDCDDCDCDCDCDDDCDCDCDDDDDDDDCDCDDDDDDDCW. We now want to make this string match VD+C+W; that is, we want to move all of the Ds to the left of all of the Cs. This can be done by reversing DCC:CD. We do this by repeating the following algorithm:

1. Find the first D that is to the right of a block of Cs.
2. Move the D to the left of that block.
3. Double the number of Cs.

Through some math, we can determine that we will end up with 123 Ds and 4638704741628490670592103344196019722536654143873 Cs (you were right about this not fitting in an SE answer... I doubt this would fit if stored as states of all of the atoms in the Earth combined :P).

If we keep applying the reverse of V:VD, we can get rid of all of the Ds now, so we get VCCC.......CCCW. We convert the V back into YZ. Now we have YZCCC.......CCCW.

We want to be able to get rid of all of the Cs and have it in the form YAAA...AAABBB...BBBZW. Fortunately, this can be done by the following method. Firstly, we inverse-apply YB:Y 587912508217580921743211 times to get YBBB.......BBBZCCC.......CCCW. Then, we repeat the following sequence of steps (where [?*] means any number of ?, not necessarily greater than zero):

1. Inverse-apply CZ:ZC 587912508217580921743211 times to get Y[A*]BBB.......BBBCCC.......CCCZCCC.......CCCW
2. Inverse-apply CB:BC many times to get Y[A*]BCBCBC.......BCBCBCZCCC.......CCCW
3. Inverse-apply AZ:Z and AB:BCA many times to get Y[A*]ABBB.......BBBZCCC.......CCCW

Through induction, we see that we can move the BZ combination all the way to the end (except before the W) and then the number of As is 1/587912508217580921743211 of the number of Cs, leaving us with 7890127658096618386747843 As. We now have YAAA.......AAABBB.......BBBZW. Convert the ZW back to a U, then inverse-apply U:BU many times to keep only 2 Bs and then convert the BBU to a T, and you now have YAAA.......AAAT. Then, you can inverse-apply T:AAAAAT many times to get YAAAT because the number of As was 3 larger than a multiple of 5.

Thanks for the challenge!

Answer 2

boboquack

For a given string, take all the letters (a = 0, b = 1, c = 2), sum them up and take the modulo 3. Then none of the rewrite rules change that value. The source string has a value of 1, and the target has a value of 2. Therefore, no combination of rules will transform the source string to the target string.

Answer 3

feersum

This is a sokoban puzzle. The starting position is:

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

The ending position is:

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

It can be solved using the following key sequence:

←←→↓↓←↑←←←←←←↓↓→↑←↑↑↑←←↓→↑→↓↓→→→→→→↓→↑↑↓↓←↓←↑→↑←←←←↑←←↓→→→→→↓→→↑↑→↑↑←↓←←↓↓→↑←↑→→↑→→↓←↓←←↓↓→↑←←←←←←←↑↑←←↓→→↓→↓↓←↑←↑→↑↑←←↓→↑→↓↓←↓→↑→→→→→→↓↓←↑→↑←←←←←←→→→→→→↑↑←↓→↓←↑↑→→↑→→↓←↓←→↑↑←↓←↓↑→→↓←↑←←↓↓↓→→↑↑↓↓←←↑↑→↓↑↑→↑→→↓←↓←↓←←↑↑→→↑→↓←↓↓←←←←←↑←←↓→→→→→←←←←←↑↑←←↓→→↓↓←↑→→→→

Here is a bash program that converts the key sequence to sed commands and applies them. The sed commands contains only replacing commands using the rewrite rules defined in the cop's answer, and labelling and branching commands that doesn't modify the string. It confirms that you can get the target string using only the rewrite rules.

s="___##___####_____##_#_#_##_#_!####______##_#####__####_#_######__###__"
input=

while
    printf '\n%80s\n' "$s"|fold -w14
    read -n 1
    [ "$REPLY" = $'\e' ]
do
    read -n 2
    case "$REPLY" in
    [A)
        s="$(sed '
s:!:wLW_:
        :a
s:L:<<<<<<<<<<<<<:
s:#w<:w#:
s:_w<:w_:
s:_<:<_:
s:#<:<#:
s:#wW:wLX!:
s:_W:W_:
s:#W:W#:
s:_wW:!:
s:_X:X_:
s:#X:X#:
s:_wX:#:
        ta' <<<"$s")";;
    [B)
        s="$(sed '
s:!:_VRv:
        :a
s:R:>>>>>>>>>>>>>:
s:>v#:#v:
s:>v_:_v:
s:>_:_>:
s:>#:#>:
s:Vv#:!URv:
s:U_:_U:
s:U#:#U:
s:Uv_:#:
s:V_:_V:
s:V#:#V:
s:Vv_:!:
        ta' <<<"$s")";;
    [C)
        s="$(sed '
s:!#_:_!#:
        te
s:!_:_!:
        :e' <<<"$s")";;
    [D)
        s="$(sed '
s:_#!:#!_:
        te
s:_!:!_:
        :e' <<<"$s")";;
    esac
    input="$input${REPLY:1}"
done

echo "$input"

Try it online!

Try it online (with escape code removed)!

For up and down, !:wLW_ or !:_VRv is applied for once correspondingly, and the relevant rules are applied repeatedly until the ! appeared again. For right, one of !#_:_!# and !_:_! is applied. For left, one of _#!:#!_ and _!:!_ is applied.

See the output in the links for the position after each move.

Answer 4

xnor

Rule 1 x:xn Rule 2 no:oon Rule 3 nr:r Rule 4 ooooooooooo:

We use [X,Y] to indicate a run of Y Xs

Starting from xn[o,A]r,

1. Applying Rule 2 once we have x[o,2]n[o,A-1]r.
2. Applying Rule 2 once more we have x[o,4]n[o,A-2]r
3. Applying until the os between n and r becomes 0, we have x[o,2*A]nr.
4. Applying Rule 3 once we have x[o,2*A]r.
5. Applying Rule 1 once we have xn[o,2*A]r.

So, we have an algorithm to generate from xn[o,A]r to xn[o,2*A]r.

Starting from xnor = xn[o,1]r, repeating 10 times the algorithm -- except in the 10th loop we stop at Step 4, having x[o,1024]r.

Applying Rule 4, this clears 1023 = 11 * 93 os, leaving xor.

Answer 5

VortexYT

There is no way of eliminating Fs without creating/using other characters; thus, we must use I:F as the last step to get to the target. No rule gives a single I without other unwanted characters thus you can't get to the target string.

Equivalently, if you try to map backwards from the source, you can only get from F to I before you have no more options.